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) мы получаем не менее абсурдное соотношение

1 + 0 = .

Вопрос о том, останавливается ли конкретная машина Тьюринга или нет, представляет собой совершенно четко определенную математическую задачу (а ранее мы уже видели, что, наоборот, различные важные математические задачи могут быть сведены к вопросу об остановке машины Тьюринга). Таким образом, доказав, что не существует алгоритма для решения вопроса об остановке машины, Тьюринг показал (также как и Черч, который использовал свой собственный и весьма отличающийся подход), что не может быть и общего алгоритма для решения математических задач. Проблема разрешимости Гильберта не имеет решения !

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