в расширенные двоичные:

Заметим, что в расширенной двоичной записи символы 1 никогда не встречаются рядом. Таким образом, последовательность из двух или более 1 вполне может послужить сигналом о начале и конце записи натурального числа. То есть для записи всевозможных команд на ленте мы можем использовать последовательности типа 110, 1110, 11110 и т.д.

Отметки на ленте также можно использовать для спецификации конкретных машин Тьюринга. Это необходимо, когда мы рассматриваем работу универсальной машины Тьюринга U. Универсальная машина U работает с лентой, начальная часть которой содержит подробную спецификацию некоторой конкретной машины Тьюринга T, которую универсальной машине предстоит смоделировать. Данные, с которыми должна работать сама машина T, подаются в U вслед за тем участком ленты, который определяет машину T. Для спецификации машины T можно использовать последовательности 110, 1110 и 11110, которые будут обозначать, соответственно, различные команды для считывающего устройства машины T, например: переместиться по ленте на один шаг вправо, на один шаг влево, либо остановиться, сдвинувшись на один шаг вправо:

Каждой такой команде предшествует либо символ 0, либо последовательность 10, что означает, что считывающее устройство должно пометить ленту, соответственно, либо символом 0, либо 1, заменив тот символ, который оно только что считало. Непосредственно перед вышеупомянутыми 0 или 10 располагается расширенное двоичное выражение числа, описывающего следующее внутреннее состояние, в которое должна перейти машина Тьюринга согласно этой самой команде. (Отметим, что внутренние состояния, поскольку количество их конечно, можно обозначать последовательными натуральными числами 0, 1, 2, 3, 4, 5, 6, …, N. При кодировании на ленте для обозначения этих чисел будет использоваться расширенная двоичная запись.)

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

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

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