Конкретная команда, к которой относится данная операция, определяется внутренним состоянием машины перед началом считывания ленты и собственно символами 0или 1, которые наше устройство при следующем шаге считает и, возможно, изменит. Например, частью описания машины T может оказаться команда 23 0– > 17 1R, что означает следующее: «Если машина Tнаходится во внутреннем состоянии 23, а считывающее устройство встречает на ленте символ 0, то его следует заменить символом 1, перейти во внутреннее состояние 17 и переместиться по ленте на один шаг вправо». В этом случае часть «17 1R» данной команды будет кодироваться последовательностью 100001010110. Разбив ее на участки 1000010.10.110, мы видим, что первый из них представляет собой расширенную двоичную запись числа 17, второй кодирует отметку 1на ленте, а третий — команду «переместиться на шаг вправо». А как нам описать предыдущее внутреннее состояние (в данном случае 23) и считываемую в соответствующий момент отметку на ленте (в данном случае 0)? При желании можно задать их так же явно с помощью расширенной двоичной записи. Однако на самом деле в этом нет необходимости, поскольку для этого будет достаточно упорядочить различные команды в виде цифровой последовательности (например, такой: 0 0– >, 0 1– >, 1 0– >, 1 1– >, 2 0– >, 2 1– >, 3 0– >, …).

К этому, в сущности, и сводится все кодирование машин Тьюринга, предложенное в НРК, однако для завершенности картины необходимо добавить еще несколько пунктов. Прежде всего, следует проследить за тем, чтобы каждому внутреннему состоянию, действующему на отметки 0и 1(не забывая, впрочем, о том, что команда для внутреннего состояния с наибольшим номером, действующая на 1, оказывается необходимой не всегда), была сопоставлена какая-либо команда. Если та или иная команда вообще не используется в программе, то необходимо заменить ее «пустышкой». Предположим, например, что в ходе выполнения программы внутреннему состоянию 23 нигде не придется сталкиваться с отметкой 1— соответствующая команда-пустышка в этом случае может иметь следующий вид: 23 1– > 0 0R.

Согласно вышеприведенным предписаниям, в кодированной спецификации машины Тьюринга на ленте пара символов 0 0должна быть представлена последовательностью 00, однако можно поступить более экономно и записать просто 0, что явится ничуть не менее однозначным разделителем двух последовательностей, составленных из более чем одного символа 1 подряд [18] . Машина Тьюринга начинает работу, находясь во внутреннем состоянии 0; считывающее устройство движется по ленте, сохраняя это внутреннее состояние до тех пор, пока не встретит первый символ 1. Это обусловлено допущением, что в набор команд машины Тьюринга всегда входит операция 0 0– > 0 0R. Таким образом, в действительной спецификации машины Тьюринга в виде последовательности 0и 1явного задания этой команды не требуется; вместо этого мы начнем с команды 0 1– > X, где Xобозначает первую нетривиальную операцию запущенной машины, т.е. первый символ 1, встретившийся ей на ленте. Это значит, что начальную последовательность 110(команду -> 0 0R), которая в противном случае непременно присутствовала бы в определяющей машину Тьюринга последовательности, можно спокойно удалить. Более того, в такой спецификации мы будем всегда удалять и завершающую последовательность 110, так как она одинакова для всех машин Тьюринга.

Получаемая в результате последовательность символов 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. Запись на ленте будет выглядеть следующим образом: