Получаемая в результате последовательность символов 0 и 1 представляет собой самую обыкновенную (т.е. нерасширенную) двоичную запись номера машины Тьюринга n для данной машины (см. главу 2 НРК). Мы называем ее n-й машиной Тьюринга и обозначаем T = T_n. Каждый такой двоичный номер (с добавлением в конце последовательности 110) есть последовательность символов 0 и 1, в которой нигде не встречается более четырех 1 подряд. Номер n, не удовлетворяющий данному условию, определяет «фиктивную машину Тьюринга», которая прекратит работать, как только встретит «команду», содержащую более четырех 1. Такую машину «T_n» мы будем называть некорректно определенной. Ее работа с какой угодно лентой является по определению незавершающейся. Аналогично, если действующая машина Тьюринга встретит команду перехода в состояние, определенное числом, большим всех тех чисел, для которых были явно заданы возможные последующие действия, то она также «зависнет»: такую машину мы будем полагать «фиктивной», а ее работу — незавершающейся. (Всех этих неудобств можно без особого труда избежать с помощью тех или иных технических средств, однако реальной необходимости в этом нет; см. §2.6, Q4).

Для того чтобы понять, как на основе заданного алгоритма A построить явное незавершающееся вычисление, факт незавершаемости которого посредством алгоритма A установить невозможно, необходимо предположить, что алгоритм A задан в виде машины Тьюринга. Эта машина работает с лентой, на которой кодируются два натуральных числа p и q. Мы полагаем, что если завершается вычисление A(p, q), то вычисление, производимое машиной T_p с числом q, не завершается вовсе. Вспомним, что если машина T_p определена некорректно, то ее работа с числом q не завершается, каким бы это самое q ни было. В случае такого «запрещенного» p исход вычисления A (p, q) может, согласно исходным допущениям, быть каким угодно. Соответственно, нас будут интересовать исключительно те числа p, для которых машина T_p определена корректно. Таким образом, в записанном на ленте двоичном выражении числа p пяти символов 1 подряд содержаться не может. Значит, для обозначения на ленте начала и конца числа p мы вполне можем воспользоваться последовательностью 11111.

То же самое, очевидно, необходимо сделать и для числа q, причем оно вовсе не обязательно должно быть числом того же типа, что и p. Здесь перед нами возникает техническая проблема, связанная с чрезвычайной громоздкостью машинных предписаний в том виде, в каком они представлены в НРК. Удобным решением этой проблемы может стать запись чисел p и q в пятеричной системе счисления. (В этой системе запись «10» означает число пять, «100» — двадцать пять, «44» — двадцать четыре и т.д.) Однако вместо пятеричных цифр 0, 1, 2, 3 и 4 я воспользуюсь соответствующими последовательностями символов на ленте 0,10,110,1110 и 11110. Таким образом, мы будем записывать

Под «C_p» здесь будет пониматься вычисление, выполняемое корректно определенной машиной Тьюринга T_r, где r есть число, обыкновенное двоичное выражение которого (с добавлением в конце последовательности символов 110) в точности совпадает с числом p в нашей пятеричной записи. Число q, над которым производится вычисление C_p, также необходимо представлять в пятеричном выражении. Вычисление же A (p, q) задается в виде машины Тьюринга, выполняющей действие с лентой, на которой кодируется пара чисел p, q. Запись на ленте будет выглядеть следующим образом:

где p и q суть вышеописанные пятеричные выражения чисел, соответственно, p и q.

Требуется отыскать такие числа p и q, для которых не завершается не только вычисление C_p(q), но и вычисление A(p, q). Процедура из §2.5 позволяет сделать это посредством отыскания такого числа k, при котором вычисление C_k, производимое с числом n, в точности совпадает с вычислением A (n, n) при любом n, и подстановки p = q = k. Для того чтобы проделать это же в явном виде, отыщем машинное предписание K(= C_k), действие которого на последовательность символов на ленте

(где n есть пятеричная запись числа n) в точности совпадает с действием алгоритма A на последовательность