незавершающейся. Аналогично, если действующая машина Тьюринга встретит команду перехода в состояние, определенное числом, большим всех тех чисел, для которых были явно заданы возможные последующие действия, то она также «зависнет»: такую машину мы будем полагать «фиктивной», а ее работу — незавершающейся. (Всех этих неудобств можно без особого труда избежать с помощью тех или иных технических средств, однако реальной необходимости в этом нет; см. §2.6, Q4).
Для того чтобы понять, как на основе заданного алгоритма A построить явное незавершающееся вычисление, факт незавершаемости которого посредством алгоритма A установить невозможно, необходимо предположить, что алгоритм A задан в виде машины Тьюринга. Эта машина работает с лентой, на которой кодируются два натуральных числа p и q. Мы полагаем, что если завершается вычисление A(p, q), то вычисление, производимое машиной Tp с числом q, не завершается вовсе. Вспомним, что если машина Tp определена некорректно, то ее работа с числом q не завершается, каким бы это самое q ни было. В случае такого «запрещенного» p исход вычисления A(p, q) может, согласно исходным допущениям, быть каким угодно. Соответственно, нас будут интересовать исключительно те числа p, для которых машина Tp определена корректно. Таким образом, в записанном на ленте двоичном выражении числа p пяти символов 1 подряд содержаться не может. Значит, для обозначения на ленте начала и конца числа p мы вполне можем воспользоваться последовательностью 11111.
То же самое, очевидно, необходимо сделать и для числа q, причем оно вовсе не обязательно должно быть числом того же типа, что и p. Здесь перед нами возникает техническая проблема, связанная с чрезвычайной громоздкостью машинных предписаний в том виде, в каком они представлены в НРК. Удобным решением этой проблемы может стать запись чисел p и q в пятеричной системе счисления. (В этой системе запись «10» означает число пять, «100» — двадцать пять, «44» — двадцать четыре и т.д.) Однако вместо пятеричных цифр 0, 1, 2, 3 и 4 я воспользуюсь соответствующими последовательностями символов на ленте 0,10,110,1110 и 11110. Таким образом, мы будем записывать
0 как 0
1 как 10
2 как 110
3 как 1110
4 как 11110
5 как 100
6 как 1010
7 как 10110
8 как 101110
9 как 1011110
10 как 1100
11 как 11010
12 как 110110
13 как 1101110
14 как 11011110
15 как 11100
16 как 111010
…
25 как 1000
26 как 10010
и т.д.
Под «Cp» здесь будет пониматься вычисление, выполняемое корректно определенной машиной Тьюринга Tr, где r есть число, обыкновенное двоичное выражение которого (с добавлением в конце последовательности символов 110) в точности совпадает с числом p в нашей пятеричной записи. Число q, над которым производится вычисление Cp, также необходимо представлять в пятеричном выражении. Вычисление же A(p, q) задается в виде машины Тьюринга, выполняющей действие с лентой, на которой кодируется пара чисел p, q. Запись на ленте будет выглядеть следующим образом:
…00111110p111110q11111000…,
где p и q суть вышеописанные пятеричные выражения чисел, соответственно, p и q.
Требуется отыскать такие числа p и q, для которых не завершается не только вычисление Cp(q), но и вычисление A(p, q). Процедура из §2.5 позволяет сделать это посредством отыскания такого числа k, при котором вычисление Ck, производимое с числом n, в точности совпадает с вычислением A(n, n) при любом n, и подстановки p = q = k. Для того чтобы проделать это же в явном виде, отыщем машинное предписание K(= Ck), действие которого на последовательность символов на ленте
…00111110n11111000…
(где n есть пятеричная запись числа n) в точности совпадает с действием алгоритма A на последовательность
…00111110n111110n11111000…
при любом n. Таким образом, действие предписания K сводится к тому, чтобы взять число n (записанное в пятеричном выражении) и однократно его скопировать, при этом два n разделяются последовательностью 111110 (та же последовательность начинает и завершает всю последовательность отметок на ленте). Следовательно, оно воздействует на получаемую в результате ленту точно так, как на эту же ленту воздействовал бы алгоритм A.
Явную модификацию алгоритма A, дающую такое предписание K, можно произвести следующим образом. Сначала находим в определении A начальную команду 01→X и отмечаем для себя, что это в действительности за «X». Мы подставим это выражение вместо «X» в спецификации, представленной ниже. Один технический момент: следует, помимо прочего, положить, чтобы алгоритм A был составлен таким образом, чтобы машина, после активации команды 01→X, никогда больше не перешла во внутреннее состояние 0 алгоритма A. Это требование ни в коей мере не влечет за собой каких-либо существенных ограничений на форму алгоритма[19]. (Нуль можно использовать только в командах-пустышках.)
Затем при определении алгоритма A необходимо установить общее число N внутренних состояний (включая и состояние 0, т.е. максимальное число внутренних состояний A будет равно N - 1). Если в определении A нет завершающей команды вида (N - 1)1→Y, то в конце следует добавить команду-пустышку (N - 1)1→ 00R. Наконец, удалим из определения A команду 01→X и добавим ее к приводимому ниже списку машинных команд, а каждый номер внутреннего состояния, фигурирующий в этом списке, увеличим на N (символом ∅ обозначено результирующее внутреннее состояние 0, а символом «X» в записи «11→X» представлена команда, которую мы рассмотрели выше). (В частности, первые две команды из списка примут в данном случае следующий вид: 01 → N1R, N0→ (N + 4)0R.)
∅1→ 01R, 00→ 40R, 01→ 01R, 10→ 21R, 11→X, 20→ 31R, 21→∅0R, 30→ 551R, 31→∅0R, 40→ 40R, 41→ 51R, 50→ 40R, 51 → 61R, 60→ 40R, 61→ 71R, 70→ 40R, 71→ 81R, 80→ 40R, 81→ 91R, 90→ 100R, 91→∅0R, 100→ 111R, 101→∅0R, 110→ 121R, 111→ 120R, 120→ 131R, 121→ 130R, 130→ 141R, 131→ 140R, 140→ 151R, 141→ 10R, 150→ 00R, 151→∅0R, 160→ 170L, 161→ 161L, 170→ 170L, 171→ 181L, 180→ 170L, 181→ 191L, 190→ 170L, 191 → 201L, 200→ 170L, 201→ 211L, 210→ 170L, 211→ 221L, 220→ 220L, 221→ 231L, 230→ 220L, 231→ 241L, 240→ 220L, 241→ 251L, 250→ 220L, 251 → 261L, 260→ 220L, 261→ 271L, 270→ 321R, 271→ 281L, 280→ 330R, 281→ 291L, 290→ 330R, 291→ 301L, 300→ 330R, 301→ 311L, 310→ 330R, 311→ 110R, 320→ 340L, 321→ 321R, 330→ 350R, 331→ 331R, 340→ 360R, 341→ 340R, 350→ 371R, 351→ 350R, 360→ 360R, 361→ 381R, 370→ 370R, 371→ 391R, 380→ 360R, 381→ 401R, 390→ 370R, 391→ 411R, 400→ 360R, 401→ 421R, 410→ 370R, 411→ 431R, 420→ 360R, 421→ 441R, 430→ 370R, 431→ 451R, 440→ 360R, 441→ 461R, 450→ 370R, 451→ 471R, 460→ 480R, 461→ 461R, 470→ 490R, 471→ 471R, 480→ 480R, 481→ 490R, 490→ 481R, 491→ 501R, 500→ 481R, 501→ 511R, 510→ 481R, 511→ 521R, 520→ 481R, 521→ 531R, 530→ 541R, 531→ 531R, 540→ 160L, 541→∅0R, 550→ 531R.
Теперь мы готовы точно определить предельную длину предписания K, получаемого путем вышеприведенного построения, как функцию от длины алгоритма A. Сравним эту «длину» со «степенью сложности», определенной в §2.6