Возникает естественный вопрос: каким образом следует определять, остановится какая-то определенная машина Тьюринга (в которую введены конкретные начальные данные) или нет? Для многих машин Тьюринга ответить на этот вопрос нетрудно, но, как мы видели выше, иногда для ответа может потребоваться решение какой-нибудь до сих пор не решенной математической задачи. Так существует ли некая алгоритмическая процедура для решения общей проблемы — проблемы остановки — полностью механическим путем? Тьюринг показал, что такой процедуры на самом деле нет.

В сущности, его доказательство сводилось к следующему. Предположим, наоборот, что указанный алгоритм существует[53]. Тогда существует и некая машина Тьюринга Н, которая «решает», остановится ли в конце концов n-я машина Тьюринга, действуя на число m. Условимся, что результатом действия машины Н будет лента с номером 0, если n-я машина не останавливается, и с номером 1 в противоположном случае:

Здесь мы могли бы воспользоваться способом кодирования пары (n, m ), использованным ранее для универсальной машины Тьюринга U. Однако это привело бы к проблеме технического характера, поскольку при некоторых n (например, n = 7) T_n  будет определена некорректно, и маркер 111101 будет непригоден для отделения на ленте n от m. Чтобы избежать этой проблемы, будем полагать, что n представлено не в двоичной, а в расширенной двоичной форме, тогда как для m будет по-прежнему использоваться обычная двоичная запись. В этом случае комбинации 110 будет достаточно для разделения n и m. Использование точки с запятой в обозначении Н(n ; m ) в отличие от запятой в обозначении универсальной машины U(n, m ) указывает на это различие в кодировании.

Представим себе теперь бесконечную таблицу, в которую включены окончательные результаты действий всех возможных машин Тьюринга на все возможные (различные) входные данные. В этой таблице N-й ряд представляет собой результаты вычислений n-й машины Тьюринга, полученные при ее работе последовательно с m = 0, 1, 2, 3, 4…:

Я немного «сжульничал» и не стал располагать машины Тьюринга по порядку их действительных номеров. Если бы я так сделал, то получился бы список, начало которого выглядело бы слишком скучным, поскольку все машины при значениях n меньших 11 не дают ничего, кроме ^□, а для n = 11 мы имеем просто нули. Дабы сделать начало этой таблицы более интересным, я предположил, что мы использовали некую гораздо более эффективную систему кодирования. Фактически, я просто присвоил ячейкам более или менее произвольные значения, только чтобы дать вам общее представление о том, как может выглядеть эта таблица.

На самом деле нам не требуется, чтобы эта таблица была построена путем вычислений, скажем, с помощью некоторого алгоритма. (На самом деле, как мы увидим далее, такого алгоритма и не существует.) Достаточно просто представить себе, что каким-то образом истинный список попал в наше распоряжение, возможно, с помощью Бога! Если бы мы попытались получить эту таблицу с помощью вычислений, то именно символы ^□ вызвали бы затруднения, поскольку мы не могли бы с уверенностью сказать, когда в той или иной ячейке должен быть помещен символ ^□ — ведь соответствующие вычисления никогда не заканчиваются!

Тем не менее искомую таблицу можно, построить с помощью вычислительной процедуры, если использовать нашу гипотетическую машину Н, поскольку она могла бы определить, где на самом деле появляются значения ^□. Однако вместо этого мы используем машину Н для того, чтобы избавиться от появления значений ^□ в таблице, заменив их во всех случаях нулями. Это достигается за счет вычисления значения Н(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 ), т. е.