Надо заметить, что наш перечень содержит избыточную информацию. Машина T 12 идентична T 6 , а по действиям обе они аналогичны T 0 , поскольку ни T 6 , ни T 12 никогда не переходят во внутреннее состояние 1. Но нам нет нужды волноваться из-за этой избыточности, равно как из-за изобилия неработоспособных (фиктивных) машин Тьюринга в нашем списке. На самом деле, мы могли бы изменить систему кодирования таким образом, чтобы избавиться от большого числа бесполезных устройств и значительно уменьшить избыточность списка машин. Но все это можно сделать только ценой усложнения нашей примитивной универсальной машины Тьюринга, которая должна расшифровывать вводимую в нее запись и имитировать машину T n , чей номер она считала. Это было бы оправдано, если бы было можно избавиться от всех бесполезных (и повторяющихся) машин. Но это, как мы увидим чуть позднее, невозможно! Поэтому мы оставим нашу систему кодирования без изменений.
Будет удобно интерпретировать ленту с последовательностью меток на ней, например
…0001101110010000…,
как двоичное представление некоторого числа. Вспомним, что нули простираются бесконечно в обе стороны, а вот количество единиц конечно. Кроме того, я буду полагать, что их число отлично от нуля(т. е. что в этой последовательности существует хотя бы одна единица). Мы можем тогда считывать конечную строку символов между первой и последней единицами (включительно), которая в предыдущем случае имеет вид
110111001,
как двоичное представление натурального числа (в десятичной форме это 441). Однако такая процедура даст нам только нечетные числа (их двоичное представление оканчивается на 1), тогда как нам нужна возможность представления всех натуральных чисел. Поэтому мы воспользуемся следующим несложным приемом — будем удалять последнюю единицу (которая принимается просто за маркер, обозначающий конец выражения) и считывать оставшуюся часть как двоичное число [46]. Тогда в последнем примере получим двоичное число
11011100,
которое соответствует десятичному числу 220. Эта процедура имеет то преимущество, что нуль также представляется непустой лентой, а именно:
… 0000001000000….
Рассмотрим, как действует машина Тьюринга T n на некоторую (конечную) строку нулей и единиц на ленте, которая подается в устройство справа. Удобно рассматривать эту строку как двоичное представление некоторого числа, например m , в соответствии с приведенной выше схемой. Предположим, что после определенного числа шагов машина T n в конце концов останавливается (т. е. доходит до команды STOP). Строка двоичных цифр, которые машина выписала к этому моменту на левой части ленты, и будет искомым результатом вычислений. Считывая эту последовательность в соответствии с той же схемой так же как двоичное представление некоторого числа, получим новое число, скажем, р . Тогда мы можем записать соотношение, выражающее тот факт, что результатом действия n-й машины Тьюринга T n на число m является число p , следующим образом:
46
Эта процедура имеет отношение только к методу, который позволяет интерпретировать запись на ленте как натуральное число. Она не изменяет номера наших конкретных машин Тьюринга, таких как EUC и XN + 1.