Роджер Пенроуз - Новый ум короля: О компьютерах, мышлении и законах физики
Наверное, принимая во внимание величины этих номеров, уже не вызовет удивления тот факт, что абсолютное большинство натуральных чисел не соответствует ни одной рабочей машине Тьюринга. Приведем перечень первых тринадцати машин Тьюринга в соответствии с принятой нумерацией:
Из этих машин T0 просто перемещается вправо, стирая все, что ей попадается на пути, никогда не останавливаясь и не меняя направления движения. Машина Т1 выполняет в сущности ту же операцию, но более громоздким путем, отступая на шаг назад каждый раз, когда она стирает очередную единицу на ленте. Так же как и T0, машина T2 двигается вправо, никогда не останавливаясь, но относится к ленте более «почтительно», попросту оставляя всю информацию нетронутой. Эти машины не могут использоваться в качестве машин Тьюринга, поскольку никогда не останавливаются. T3 — первая в этом списке «правильная» машина: она скромно прекращает действие после того, как изменяет первую (самую левую) единицу на нуль. T4 сталкивается с серьезной проблемой. Найдя первую единицу на ленте, она переходит во внутреннее состояние, которое нигде не описано, и, следовательно, машина не имеет никаких команд для следующего шага. С той же проблемой сталкиваются T8 , T9 и T10 . С T7 возникают трудности еще более фундаментального характера. Строка нулей и единиц, которой она представляется, включает последовательность из пяти единиц: 110111110. Интерпретации этой последовательности не существует, поэтому T7 намертво застревает сразу же, как только доходит до первой единицы. (Я буду называть T7 , равно как и любую другую машину Tn, двоичное расширенное представлений которой содержит более четырех единиц, некорректно определенной.) Машины T5, T6 и T12 испытывают те же трудности, что и T0, T1, T2: они просто никогда не останавливаются. Все эти машины — T0, T1 , T2 , T5 , T6 , T7 , T8, T9, T10 и T12 — совершенно бесполезные устройства! Только T3 и T11 являются функциональными машинами Тьюринга, да и то не слишком интересными. Причем T11 даже скромнее, чем T3 : натолкнувшись на первую же единицу, она останавливается и вообще ничего не меняет!
Надо заметить, что наш перечень содержит избыточную информацию. Машина T12 идентична T6, а по действиям обе они аналогичны T0, поскольку ни T6, ни T12 никогда не переходят во внутреннее состояние 1. Но нам нет нужды волноваться из-за этой избыточности, равно как из-за изобилия неработоспособных (фиктивных) машин Тьюринга в нашем списке. На самом деле, мы могли бы изменить систему кодирования таким образом, чтобы избавиться от большого числа бесполезных устройств и значительно уменьшить избыточность списка машин. Но все это можно сделать только ценой усложнения нашей примитивной универсальной машины Тьюринга, которая должна расшифровывать вводимую в нее запись и имитировать машину Tn, чей номер она считала. Это было бы оправдано, если бы было можно избавиться от всех бесполезных (и повторяющихся) машин. Но это, как мы увидим чуть позднее, невозможно! Поэтому мы оставим нашу систему кодирования без изменений.
Будет удобно интерпретировать ленту с последовательностью меток на ней, например
…0001101110010000…,
как двоичное представление некоторого числа. Вспомним, что нули простираются бесконечно в обе стороны, а вот количество единиц конечно. Кроме того, я буду полагать, что их число отлично от нуля (т. е. что в этой последовательности существует хотя бы одна единица). Мы можем тогда считывать конечную строку символов между первой и последней единицами (включительно), которая в предыдущем случае имеет вид
110111001,
как двоичное представление натурального числа (в десятичной форме это 441). Однако такая процедура даст нам только нечетные числа (их двоичное представление оканчивается на 1), тогда как нам нужна возможность представления всех натуральных чисел. Поэтому мы воспользуемся следующим несложным приемом — будем удалять последнюю единицу (которая принимается просто за маркер, обозначающий конец выражения) и считывать оставшуюся часть как двоичное число[46]. Тогда в последнем примере получим двоичное число
11011100,
которое соответствует десятичному числу 220. Эта процедура имеет то преимущество, что нуль также представляется непустой лентой, а именно:
… 0000001000000….
Рассмотрим, как действует машина Тьюринга Tn на некоторую (конечную) строку нулей и единиц на ленте, которая подается в устройство справа. Удобно рассматривать эту строку как двоичное представление некоторого числа, например m, в соответствии с приведенной выше схемой. Предположим, что после определенного числа шагов машина Tn в конце концов останавливается (т. е. доходит до команды STOP). Строка двоичных цифр, которые машина выписала к этому моменту на левой части ленты, и будет искомым результатом вычислений. Считывая эту последовательность в соответствии с той же схемой так же как двоичное представление некоторого числа, получим новое число, скажем, р. Тогда мы можем записать соотношение, выражающее тот факт, что результатом действия n-й машины Тьюринга Tn на число m является число p, следующим образом:
Tn(m)=p .
Взглянем на это соотношение с несколько иной точки зрения. Мы будем считать, что это выражение описывает некоторую специфическую операцию, которая применяется к паре чисел m и n для того, чтобы получить p. (Это означает: для заданных двух чисел n и m мы можем найти значение p, если введем m в n-ю машину Тьюринга.) Эта специфическая операция является полностью алгоритмической. Поэтому она может быть выполнена одной конкретной машиной Тьюринга U; иными словами, U, совершая действие над парой (n, m ), дает в результате p. Поскольку машина U должна производить операцию над обоими числами n и m, чтобы получить ответ, выражаемый одним числом p, то нам нужно придумать способ для записи пары (n, m) на одной ленте. С этой целью предположим, что n записывается в стандартной двоичной форме и заканчивается последовательностью 111110. (Вспомним, что двоичный номер всякой корректно определенной машины Тьюринга, — это последовательность символов, состоящая только из сочетаний вида 0, 10, 110, 1110 и 11110, поэтому он нигде не содержит более четырех единиц подряд. Таким образом, если Tn — корректно определенная машина, то появление последовательности 111110 действительно будет означать конец записи номера n.) Все, что следует за ней, должно быть просто записью числа m на ленте в соответствии с приведенными выше правилами (т. е. двоичное число m и строка 1000… непосредственно за ним). Таким образом, с этой второй частью ленты машина Tn и должна производить предполагаемые действия.
Если в качестве примера мы возьмем n =11 и m =6, то на ленте, вводимой в мащину U, мы будем иметь последовательность
000101111111011010000..
Она образована из следующих составляющих:
… 0000 (пустое начало ленты)
1011 (двоичное представление одиннадцати)
111110 (обозначает окончание числа n )
110 (двоичное представление шести)
10000… (остаток ленты)
То, что машина Тьюринга U должна была бы делать на каждом очередном шагу процедуры, выполняемой Tn над m — это исследовать структуру последовательности цифр в выражении n с тем, чтобы можно было произвести соответствующие изменения цифр числа m (т. е. «ленты» машины Tn ). В принципе, реализация такой машины не вызывает существенных затруднений (хотя и довольно громоздка на практике). Список ее собственных команд должен был бы просто содержать правила для чтения подходящей команды из «списка», закодированного в числе n, на каждом этапе выполнения действий над цифрами, считанными с «ленты», как они фигурируют в числе m. Можно предположить, что при этом совершалось бы значительное количество прыжков взад-вперед по ленте между цифрами, составляющими n и m, и выполнение процедуры было бы чрезвычайно медленным. Тем не менее, список команд подобной машины, несомненно, можно составить, и такая машина называется нами универсальной машиной Тьюринга. Обозначая ее действие на пару чисел (n, m ) через U(n, m ), мы получаем:
