Я немного "сжульничал" и не стал располагать машины Тьюринга по порядку их действительных номеров. Если бы я так сделал, то получился бы список, начало которого выглядело бы слишком скучным, поскольку все машины при значениях n меньших 11 не дают ничего, кроме , а для n = 11 мы имеем просто нули. Дабы сделать начало этой таблицы более интересным, я предположил, что мы использовали некую гораздо более эффективную систему кодирования. Фактически, я просто присвоил ячейкам более или менее произвольные значения, только чтобы дать вам общее представление о том, как может выглядеть эта таблица.
На самом деле нам не требуется, чтобы эта таблица была построена путем вычислений, скажем, с помощью некоторого алгоритма. (На самом деле, как мы увидим далее, такого алгоритма и не существует.) Достаточно просто представить себе, что каким-то образом истинный список попал в наше распоряжение, возможно, с помощью Бога! Если бы мы попытались получить эту таблицу с помощью вычислений, то именно символы вызвали бы затруднения, поскольку мы не могли бы с уверенностью сказать, когда в той или иной ячейке должен быть помещен символ - ведь соответствующие вычисления никогда не заканчиваются!
Тем не менее искомую таблицу можно, построить с помощью вычислительной процедуры, если использовать нашу гипотетическую машину Н, поскольку она могла бы определить, где на самом деле появляются значения . Однако вместо этого мы используем машину Н для того, чтобы избавиться от появления значений в таблице, заменив их во всех случаях нулями. Это достигается за счет вычисления значения Н(n ; m ), предваряющего действие Tn на m , после чего мы позволим Tn производить соответствующие действия, только если H(n ; m ) = 1 (т. е. только тогда, когда вычисление Tn(m) приводит к определенному результату), и будем просто записывать в соответствующую ячейку 0 при Н(n ; m ) = 0 (т. е. если Tn(m) = ). Мы можем записать эту новую процедуру, представляющую собой последовательное действие Н(n ; m) и T(m), как
Tn(m) х Н(n; m ).
(Здесь я использую общепринятую в математике договоренность о последовательности выполнения действий, согласно которой операция, записанная справа, должна выполняться первой. Обратите внимание, что в этом случае можно символически записать х 0 = 0.)
Теперь таблица принимает следующий вид:
Заметьте, что, исходя из предположения существования машины Н, мы получаем ряды таблицы, состоящие из вычислимых последовательностей. (Под "вычислимой последовательностью" я понимаю бесконечную последовательность, элементы могут быть найдены один за другим посредством некоего алгоритма; это означает, что существует некоторая машина Тьюринга, которая, будучи применена поочередно к натуральным числам m = 0, 1, 2, 3, 4, 5…, производит члены рассматриваемой последовательности.) Обратите внимание на следующие два факта относительно этой таблицы. Во-первых, любая вычислимая последовательность натуральных чисел должна появиться где-то (может быть, далеко не сразу) среди рядов таблицы. Это свойство выполнялось уже и для исходной таблицы, содержавшей значения . Мы просто добавили несколько рядов, чтобы заменить "фиктивные" машины Тьюринга (т. е. такие, которые приводят к хотя бы в одном случае). Во-вторых, считая, что машина Тьюринга H существует, мы получили таблицу вычислительным путем (т. е. с помощью некоторого определенного алгоритма), а именно, посредством процедуры Tn(m) х Н(n ; m ). Иными словами, существует некая машина Тьюринга Q, применение которой к паре чисел (n, m ) дает значение соответствующей ячейки таблицы. Для этой машины числа n и m на ленте можно кодировать таким же образом, как и для H, т. е. мы имеем
Q(n ; m ) = Tn(m ) х H(n ; m ).
Воспользуемся теперь разновидностью остроумного и мощного приема, так называемого диагонального процесса Георга Кантора. (Мы познакомимся с оригинальным вариантом этого метода в следующей главе.) Рассмотрим значения в ячейках, расположенных на главной диагонали таблицы - диагональные элементы (матрицы), - выделенные жирным шрифтом:
Эти элементы образуют некоторую последовательность 0,0,1,2,1,0, 3,7,1…., к каждому члену которой мы теперь прибавим единицу:
1, 1, 2, 3, 2, 1, 4, 8, 2…
Это, безусловно, механическая процедура, и, поскольку наша таблица была получена путем вычислений, мы получим новую вычислимую последовательность 1 + Q(n ; m ), т. е.
1 + Tn(n) х H(n ; n )
(с учетом того, что для диагональных элементов n = m). Но наша таблица содержит в себе все вычислимые последовательности, поэтому она должна содержать также и новую последовательность. Однако это невозможно! Ведь наша новая последовательность отличается от первого ряда первым элементом, от второго - вторым, от третьего - третьим, и т. д. Налицо явное противоречие, которое и устанавливает справедливость доказываемого нами утверждения о том, что машина Тьюринга H на самом деле не существует! Иными словами, не существует универсального алгоритма для решения вопроса об остановке произвольной машины Тьюринга.
Можно построить доказательство и по-другому. Для этого заметим, что из предположения о существовании H следует и существование машины Тьюринга с номером k, реализующей алгоритм (диагональный процесс!) 1 + Q(n ; n ), т. е. можно записать
1 + Tn(n ) х H(n ; n ) = Tk(n ).
Но если мы подставим в это выражение n = k, то получится
1 + Tk(k ) x H(k ; k ) = Tk(n).
Мы приходим к противоречию, потому что если Tk(k) останавливается, то мы имеем невыполнимое равенство
1 + Tk(k ) = Tk(k )
(поскольку Н(k ; k ) = 1), тогда как в случае безостановочного действия Tk(k ) (т. е. когда Н(k; k ) = 0) мы получаем не менее абсурдное соотношение
1 + 0 = .