где 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.)

Теперь мы готовы точно определить предельную длину предписания K, получаемого путем вышеприведенного построения, как функцию от длины алгоритма A. Сравним эту «длину» со «степенью сложности», определенной в §2.6 (в конце комментария к возражению Q8). Для некоторой конкретной машины Тьюринга T m(например, той, что выполняет вычисление A) эта величина равна количеству знаков в двоичном представлении числа m. Для некоторого конкретного машинного действия T m( n) (например, выполнения предписания K) эта величина равна количеству двоичных цифр в большем из чисел тип. Обозначим через и количество двоичных цифр в aи k'соответственно, где

Поскольку алгоритм Aсодержит, как минимум, 2 N– 1 команд (учитывая, что первую команду мы исключили) и поскольку для каждой команды требуется, по крайней мере, три двоичные цифры, общее число двоичных цифр в номере его машины Тьюринга а непременно должно удовлетворять условию

В вышеприведенном дополнительном списке команд для Kесть 105 мест (справа от стрелок), где к имеющемуся там числу следует прибавить N. Все получаемые при этом числа не превышают N+ 55, а потому их расширенные двоичные представления содержат не более 2 log 2( N+ 55) цифр, в результате чего общее количество двоичных цифр, необходимых для дополнительного определения внутренних состояний, не превышает 210 log 2( N+ 55). Сюда нужно добавить цифры, необходимые для добавочных символов 0, 1, Rи L, что составляет еще 527 цифр (включая одну возможную добавочную «команду-пустышку» и учитывая, что мы можем исключить шесть символов 0по правилу, согласно которому 0 0можно представить в виде 0). Таким образом, для определения предписания Kтребуется больше двоичных цифр, чем для определения алгоритма A, однако разница между этими двумя величинами не превышает 527 + 210 log 2( N+ 55):