Чтобы выполнить эту программу, предположим, что существует универсальная машина Тьюринга, которая является такой машиной Тьюринга, которую можно запрограммировать для имитации любой индивидуальной машины Тьюринга. У этой машины входная лента имеет две секции, одна для программы, а другая для данных. Программная часть может состоять из строки чисел, которые инструктируют головку, как реагировать на то, что она обнаруживает на ленте. Например, код 001 может означать:
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, … и составляем таблицу, верхним левым фрагментом которой является следующая:
Вход 0 1 2 3
Номер матрицы 0 □ □ □ □
1 3 □ 4 1
2 1 1 1 1
3 0 1 □ 2
Когда вычисления не останавливаются, мы записываем символ □. Таблица содержит все возможные вычислимые числа (числа, которые могут быть вычислены машиной Тьюринга до произвольного числа разрядов), поскольку она содержит в своих последовательных рядах все возможные машины Тьюринга, а в последовательных колонках все возможные входы.
Теперь мы делаем второй шаг. На этот раз мы рассортируем результаты с помощью машины th, которая настроена так, что выдает 0, если решает, что соответствующие вычисления не остановятся, и не выдает никаких данных, если решает, что вычисления остановятся. Она также делает себе пометку, чтобы запомнить, где она заменила □ на 0, так как не хочет, чтобы машина, программа которой имитируется, была снова втянута в бесконечные вычисления. Например, когда мы загружаем в машину thчисло 4, а затем число 2, она, в соответствии с программой t 4и данными 2, инспектирует ленту, производит некоторого рода вычисления, решает, что вычисление t 4(2)не остановится, если мы будем его выполнять, и поэтому ставит 0 в соответствующую ячейку таблицы и делает себе пометку, что данное вычисление не остановится. В конце этого этапа вычислений верхний левый фрагмент таблицы выглядит так:
Вход 0 1 2 3
Номер матрицы 0 0 0 0 0
1 0
2 3 0
Теперь там, где мы не обнаруживаем 0, мы производим все вычисления, как мы это делали на первом шаге, и получаем следующий фрагмент таблицы:
Вход 0 1 2 3
Номер матрицы 0 0 0 0 0
1 3
0 4 1
2 1 1
1 1
3 0 1 0
2 Поскольку исходная таблица содержит все возможные вычислимые числа, эта таблица тоже содержит все возможные вычислимые числа: здесь может быть много повторений, но это делу не мешает.
Теперь перейдем к финалу. Давайте возьмем числа на диагонали (они выделены жирным шрифтом) и изменим их, прибавляя 1 (что похоже на доказательство Кантора). Мы получаем последовательность вида 1123…. Это вычислимое число (поскольку последовательность шагов, основанная на thи машине Тьюринга, действует в каждом предполагаемом случае), поэтому машина, которая производит это число, уже должна присутствовать где-то в таблице. Однако ее нет: она отличается от первого ряда (поскольку мы заставили первую цифру измениться), она отличается от второго ряда (поскольку мы заставили вторую цифру измениться), и так далее, для всех рядов в таблице. То есть, с одной стороны, ряд 1123… должен быть представлен, но, с другой стороны, его нет. Это противоречие, поэтому предположение о существовании «остановочной машины» th, которое мы использовали, должно быть ложным. Мы доказали (и это подтверждено более строгим и авторитетным доказательством Тьюринга), что не существует ни одной общей универсальной алгоритмической процедуры, которую можно использовать, чтобы судить, придут ли к концу данные вычисления или нет. Это влечет, в свою очередь, то, что не может существовать никакого общего алгоритма для решения математических задач, и поэтому Entscheidungsproblemне имеет решения.
Теперь я перехожу к высшей точке этой главы, к тому, что называют самым красивым достижением логики двадцатого века, к теореме Гёделя. Австрийский логик Курт Гёдель (1906-1978) родился в Брюнне, Австро-Венгрия (ныне Брно, Республика Чехия), где работал Грегор Мендель, и учился в Венском университете. Хотя он и не был евреем (вопреки утверждению Бертрана Рассела), Гёдель не смог терпимо относиться к нацистским репрессиям и в 1934 г. поехал в США, в 1940 г. эмигрировал туда насовсем и провел оставшуюся часть жизни в Принстоне, где он и Эйнштейн стали большими друзьями. Конечно, в свои последние годы Гёдель внес существенный вклад и в общую теорию относительности, когда обнаружил неожиданное решение уравнений Эйнштейна, позволяющее времени течь в прошлое. По своему облику и образу жизни Гёдель не был человеком, которого можно было считать вполне приемлемым в обществе. Возвратись в Австрию после своей первой поездки в США, он женился на разведенной танцовщице и увез ее в Принстон, где ее не могли хорошо принять из-за преобладавшего в то время снобизма. К концу жизни у него развились классические признаки депрессии и паранойи: он был убежден, что является жертвой тайного общества убийц, что в конце концов привело его к отказу от еды и к ношению лыжной маски, чтобы избежать заражения во время прогулок в опасной и сильно загрязненной, как он считал, атмосфере Принстона. Он скончался, веся лишь 30 кг, от «недоедания и истощения» (вызванных отказом от пищи), явившихся, как гласит заключение о смерти, результатом «душевного расстройства».
