Новый ум короля: О компьютерах, мышлении и законах физики

Здесь мы могли бы воспользоваться способом кодирования пары ( 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).