Питер Эткинз - Десять великих идей науки. Как устроен наш мир.

001:если вы обнаруживаете на ленте 1 и находитесь в состоянии 1, замените 1 на 0, смените ваше внутреннее состояние на состояние 2 и передвиньтесь на один шаг вправо.

Подобным же образом, код 010 может означать:

010:если вы обнаруживаете на ленте 0 и находитесь в состоянии 2, передвиньтесь на один шаг влево; а если вы считываете 1, то замените 1 на 0 и передвиньтесь на один шаг вправо.

Программная часть ленты может выглядеть как …001010…, если эти две инструкции надо выполнить последовательно. Мы будем называть универсальную машину Тьюринга tu . Заметим, что, в то время как индивидуальная машина Тьюринга считывает только данные, универсальная машина сначала считывает программу, чтобы подготовить себя, а затем уж считывает данные. Так, если мы хотим, чтобы она имитировала t 10 , мы считываем программу 10, то есть множество инструкций, настраивающих машину на работу в режиме t 10 , а затем скармливаем ей данные. Если данные состоят из числа 3, мы будем ожидать от этого совместного процесса ответ 42 и запишем tu(10,3) = 42 , где первое число в скобках является номером машины Тьюринга, которую мы хотели имитировать, а второе число представляет данные.

Предположим теперь, что существует машина Тьюринга, которая может взять программу любой другой машины Тьюринга, например t 23 , и любое множество данных, и решить, остановится или нет эта комбинация, чтобы напечатать ответ. Мы назовем эту особую машину Тьюринга th (h здесь от английского глагола «halt» — останавливаться). Если th получает остановку для частной комбинации программы и данных, например t 23 и 3, она напечатает 1 и остановится; если она определяет, что комбинация не приводит к остановке, например t 22 и 17, th напечатает 0 и остановится. Успех Тьюринга выразился в доказательстве того, что th не включена в список всех возможных машин Тьюринга и поэтому не существует. Чтобы проделать это, он использовал аргументы, очень похожие на «диагональные» аргументы, которыми пользовался Кантор для доказательства того, что иррациональные числа несчетны. Вы можете свободно перейти к следующему подразделу, если хотите пропустить вывод этого результата.

Эти аргументы таковы. Предположим, что мы задаем входные данные 0, 1, 2, … и машины Тьюринга t 0, t 1 , t 2 , … и составляем таблицу, верхним левым фрагментом которой является следующая:

Когда вычисления не останавливаются, мы записываем символ □. Таблица содержит все возможные вычислимые числа (числа, которые могут быть вычислены машиной Тьюринга до произвольного числа разрядов), поскольку она содержит в своих последовательных рядах все возможные машины Тьюринга, а в последовательных колонках все возможные входы.

Теперь мы делаем второй шаг. На этот раз мы рассортируем результаты с помощью машины th , которая настроена так, что выдает 0, если решает, что соответствующие вычисления не остановятся, и не выдает никаких данных, если решает, что вычисления остановятся. Она также делает себе пометку, чтобы запомнить, где она заменила □ на 0, так как не хочет, чтобы машина, программа которой имитируется, была снова втянута в бесконечные вычисления. Например, когда мы загружаем в машину th число 4, а затем число 2, она, в соответствии с программой t 4 и данными 2, инспектирует ленту, производит некоторого рода вычисления, решает, что вычисление t 4(2) не остановится, если мы будем его выполнять, и поэтому ставит 0 в соответствующую ячейку таблицы и делает себе пометку, что данное вычисление не остановится. В конце этого этапа вычислений верхний левый фрагмент таблицы выглядит так:

Теперь там, где мы не обнаруживаем 0 , мы производим все вычисления, как мы это делали на первом шаге, и получаем следующий фрагмент таблицы:

Поскольку исходная таблица содержит все возможные вычислимые числа, эта таблица тоже содержит все возможные вычислимые числа: здесь может быть много повторений, но это делу не мешает.

Теперь перейдем к финалу. Давайте возьмем числа на диагонали (они выделены жирным шрифтом) и изменим их, прибавляя 1 (что похоже на доказательство Кантора). Мы получаем последовательность вида 1123…. Это вычислимое число (поскольку последовательность шагов, основанная на th и машине Тьюринга, действует в каждом предполагаемом случае), поэтому машина, которая производит это число, уже должна присутствовать где-то в таблице. Однако ее нет: она отличается от первого ряда (поскольку мы заставили первую цифру измениться), она отличается от второго ряда (поскольку мы заставили вторую цифру измениться), и так далее, для всех рядов в таблице. То есть, с одной стороны, ряд 1123… должен быть представлен, но, с другой стороны, его нет. Это противоречие, поэтому предположение о существовании «остановочной машины» th , которое мы использовали, должно быть ложным. Мы доказали (и это подтверждено более строгим и авторитетным доказательством Тьюринга), что не существует ни одной общей универсальной алгоритмической процедуры, которую можно использовать, чтобы судить, придут ли к концу данные вычисления или нет. Это влечет, в свою очередь, то, что не может существовать никакого общего алгоритма для решения математических задач, и поэтому Entscheidungsproblem не имеет решения.

Теперь я перехожу к высшей точке этой главы, к тому, что называют самым красивым достижением логики двадцатого века, к теореме Гёделя . Австрийский логик Курт Гёдель (1906-1978) родился в Брюнне, Австро-Венгрия (ныне Брно, Республика Чехия), где работал Грегор Мендель, и учился в Венском университете. Хотя он и не был евреем (вопреки утверждению Бертрана Рассела), Гёдель не смог терпимо относиться к нацистским репрессиям и в 1934 г. поехал в США, в 1940 г. эмигрировал туда насовсем и провел оставшуюся часть жизни в Принстоне, где он и Эйнштейн стали большими друзьями. Конечно, в свои последние годы Гёдель внес существенный вклад и в общую теорию относительности, когда обнаружил неожиданное решение уравнений Эйнштейна, позволяющее времени течь в прошлое. По своему облику и образу жизни Гёдель не был человеком, которого можно было считать вполне приемлемым в обществе. Возвратись в Австрию после своей первой поездки в США, он женился на разведенной танцовщице и увез ее в Принстон, где ее не могли хорошо принять из-за преобладавшего в то время снобизма. К концу жизни у него развились классические признаки депрессии и паранойи: он был убежден, что является жертвой тайного общества убийц, что в конце концов привело его к отказу от еды и к ношению лыжной маски, чтобы избежать заражения во время прогулок в опасной и сильно загрязненной, как он считал, атмосфере Принстона. Он скончался, веся лишь 30 кг, от «недоедания и истощения» (вызванных отказом от пищи), явившихся, как гласит заключение о смерти, результатом «душевного расстройства».