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

при любом n. Таким образом, действие предписания  Kсводится к тому, чтобы взять число  n(записанное в пятеричном выражении) и однократно его скопировать, при этом два  n разделяются последовательностью 111110(та же последовательность начинает и завершает всю последовательность отметок на ленте). Следовательно, оно воздействует на получаемую в результате ленту точно так, как на эту же ленту воздействовал бы алгоритм A.

Явную модификацию алгоритма A, дающую такое предписание K, можно произвести следующим образом. Сначала находим в определении Aначальную команду 0 1→  Xи отмечаем для себя, что это в действительности за « X». Мы подставим это выражение вместо « X» в спецификации, представленной ниже. Один технический момент: следует, помимо прочего, положить, чтобы алгоритм Aбыл составлен таким образом, чтобы машина, после активации команды 0 1→  X, никогда больше не перешла во внутреннее состояние 0 алгоритма A. Это требование ни в коей мере не влечет за собой каких-либо существенных ограничений на форму алгоритма [19]. (Нуль можно использовать только в командах-пустышках.)

Затем при определении алгоритма  Aнеобходимо установить общее число Nвнутренних состояний (включая и состояние 0, т.е. максимальное число внутренних состояний  Aбудет равно N - 1). Если в определении  Aнет завершающей команды вида ( N - 1) 1→ Y, то в конце следует добавить команду-пустышку ( N - 1) 1→ 0 0R. Наконец, удалим из определения  Aкоманду 0 1→  Xи добавим ее к приводимому ниже списку машинных команд, а каждый номер внутреннего состояния, фигурирующий в этом списке, увеличим на N(символом ∅ обозначено результирующее внутреннее состояние 0, а символом « X» в записи «1 1→ X» представлена команда, которую мы рассмотрели выше). (В частности, первые две команды из списка примут в данном случае следующий вид: 0 1→ N 1R, N 0→ (N + 4) 0R.)