На самом деле нам не требуется, чтобы эта таблица была построена путем вычислений, скажем, с помощью некоторого алгоритма. (На самом деле, как мы увидим далее, такого алгоритма и не существует.) Достаточно просто представитьсебе, что каким-то образом истинныйсписок попал в наше распоряжение, возможно, с помощью Бога! Если бы мы попытались получить эту таблицу с помощью вычислений, то именно символы □вызвали бы затруднения, поскольку мы не могли бы с уверенностью сказать, когда в той или иной ячейке должен быть помещен символ □— ведь соответствующие вычисления никогда не заканчиваются!
Тем не менее искомую таблицу можно, построить с помощью вычислительной процедуры, если использовать нашу гипотетическую машину Н, поскольку она могла бы определить, где на самом деле появляются значения □. Однако вместо этого мы используем машину Ндля того, чтобы избавитьсяот появления значений □в таблице, заменив их во всех случаях нулями. Это достигается за счет вычисления значения Н( n ; m ), предваряющего действие T n на m , после чего мы позволим T n производить соответствующие действия, только если H( n ; m ) = 1 (т. е. только тогда, когда вычисление T n (m) приводит к определенному результату), и будем просто записывать в соответствующую ячейку 0при Н( n ; m ) = 0 (т. е. если T n ( m ) = □). Мы можем записать эту новую процедуру, представляющую собой последовательное действие Н( n ; m ) и T(m), как
T n (m) х Н( n; m ).
(Здесь я использую общепринятую в математике договоренность о последовательности выполнения действий, согласно которой операция, записанная справа, должна выполняться первой. Обратите внимание, что в этом случае можно символически записать □х 0 = 0.)
Теперь таблица принимает следующий вид:
Заметьте, что, исходя из предположения существования машины Н, мы получаем ряды таблицы, состоящие из вычислимыхпоследовательностей. (Под «вычислимой последовательностью» я понимаю бесконечную последовательность, элементы могут быть найдены один за другим посредством некоего алгоритма; это означает, что существует некоторая машина Тьюринга, которая, будучи применена поочередно к натуральным числам m = 0, 1, 2, 3, 4, 5…, производит члены рассматриваемой последовательности.) Обратите внимание на следующие два факта относительно этой таблицы. Во-первых, любаявычислимая последовательность натуральных чисел должна появиться где-то (может быть, далеко не сразу) среди рядов таблицы. Это свойство выполнялось уже и для исходной таблицы, содержавшей значения □. Мы просто добавилинесколько рядов, чтобы заменить «фиктивные» машины Тьюринга (т. е. такие, которые приводят к □хотя бы в одном случае). Во-вторых, считая, что машина Тьюринга Hсуществует, мы получили таблицу вычислительным путем(т. е. с помощью некоторого определенного алгоритма), а именно, посредством процедуры T n (m) х Н( n ; m ). Иными словами, существует некая машина Тьюринга Q, применение которой к паре чисел ( n , m ) дает значение соответствующей ячейки таблицы. Для этой машины числа n и m на ленте можно кодировать таким же образом, как и для H, т. е. мы имеем
Q( n ; m ) = T n ( 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 + T n ( n ) х H ( n ; n )
(с учетом того, что для диагональных элементов n = m ). Но наша таблица содержит в себе все вычислимые последовательности, поэтому она должна содержать также и новую последовательность. Однако это невозможно! Ведь наша новая последовательность отличается от первого ряда первым элементом, от второго — вторым, от третьего — третьим, и т. д. Налицо явное противоречие, которое и устанавливает справедливость доказываемого нами утверждения о том, что машина Тьюринга Hна самом деле не существует! Иными словами, не существует универсального алгоритма для решения вопроса об остановке произвольной машины Тьюринга.
Можно построить доказательство и по-другому. Для этого заметим, что из предположения о существовании Hследует и существование машины Тьюринга с номером k , реализующей алгоритм (диагональный процесс!) 1 + Q( n ; n ), т. е. можно записать
1 + T n ( n ) х H( n ; n ) = T k ( n ).
Но если мы подставим в это выражение n = k , то получится
1 + T k ( k ) x H( k ; k ) = T k ( n ).
Мы приходим к противоречию, потому что если T k ( k ) останавливается, то мы имеем невыполнимое равенство
1 + T k ( k ) = T k ( k )
(поскольку Н( k ; k ) = 1), тогда как в случае безостановочного действия T k ( k ) (т. е. когда Н( k ; k ) = 0) мы получаем не менее абсурдное соотношение