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

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