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