Новый ум короля: О компьютерах, мышлении и законах физики

Пенроуз Роджер

Универсальная машина Тьюринга

Я еще не затрагивал понятия универсальноймашины Тьюринга. Лежащий в ее основе принцип понять нетрудно, хотя детали могут быть сложны. Основная идея состоит в том, чтобы закодировать команды для произвольной машины Тьюринга Тв виде последовательности нулей и единиц, которую можно записать на ленте. Эта запись используется как начальная часть входных данных для некоторой особоймашины Тьюринга U, называемой универсальной, которая затем обрабатывает остальную часть ленты в точности так, как это сделала бы машина Т. Универсальная машина Тьюринга — это универсальный имитатор. Начальная часть ленты дает универсальной машине Uвсю информацию, необходимую для точной имитации любой машины Т!

Чтобы показать, как это может быть реализовано, нам потребуется какая-нибудь система нумерациимашин Тьюринга. Рассмотрим список инструкций, определяющих произвольную машину Тьюринга, например, одну из описанных выше. Мы должны в соответствии с некоторыми четкими правилами представить эти инструкции в виде последовательностей нулей и единиц. Это можно сделать, например, с помощью процедуры

«сокращения», которую мы использовали ранее. Тогда, если мы закодируем символы R, L, STOP , «стрелка» (->) и «запятая», скажем, числами 2, 3, 4, 5 и 6 соответственно, то мы сможем записать их в виде «сокращений» 110, 1110, 11110, 111110 и 1111110. Цифры 0 и 1, кодируемые, соответственно, как 0и 10, могут быть использованы для записи строк этих символов, входящих в таблицу действий машины Тьюринга. Нам не нужны различные обозначения для «жирных» цифр 0и 1и для остальных цифр в таблице, поскольку расположение «жирных» цифр в конце двоичного кода является достаточным отличительным признаком. При этом 110 1, например, будет читаться как двоичное число 1101, представляемое на ленте последовательностью 1010010. в частности, 0 0будет читаться как 00, что без всякой двусмысленности можно закодировать как 0или вовсе опустить. Можно существенно сэкономить, если не кодировать «стрелки» и непосредственно предшествующие им символы, а воспользоваться цифровым упорядочением команд, позволяющим определить, какими должны быть эти символы. Правда, для этого надо убедиться в отсутствии «дырок» в получившемся порядке и добавить, где требуется, «немые» команды. (Например, машина Тьюринга XN +1не имеет команды, соответствующей коду 110 0, поскольку такая комбинация в ходе ее работы никогда не встречается. Следовательно, мы должны ввести в список команд немую команду, скажем 110 0– > 0 0R, которая не вызовет каких бы то ни было изменений в работе машины. Сходным образом мы должны добавить немую команду 10 1– > 0 0Rв список команд машины XN х 2.) Без таких «немых» команд кодирование последующих команд было бы нарушено. Как можно видеть, на самом деле мы не нуждаемся и в запятой в конце каждой команды, поскольку символов Lи Rвполне достаточно для отделения команд друг от друга. Поэтому мы просто будем использовать такую систему кодирования:

0для 0 или 0,

10для 1 или 1,

110для R,

1110для L,

11110для STOP.

В качестве примера выпишем команды для машины Тьюринга XN +1(с дополнительной немой командой 110 0– > 0 0R). Опуская стрелки, цифры, непосредственно предшествующие им, и запятые, получим

Мы можем улучшить полученный результат, если опустим все 0 0и заменим каждые 0 1просто единицей в соответствии с тем, что говорилось ранее. Тогда мы получим строку символов

которая на ленте записывается как последовательность

Есть еще два способа немного сэкономить. Во-первых, всегда можно удалить код 110в начале записи (вместе с бесконечным участком пустой ленты, предшествующим этому коду). Он обозначает последовательность 0 0R, соответствующую начальной команде 0 0– > 0 0R, которую я до сих пор неявно считал общей для всех машин Тьюринга, поскольку она необходима для того, чтобы устройство, начав работу в произвольной точке слева от начала записи на ленте, могло перемещаться вправо до тех пор, пока не встретит первую непустую клетку. Во-вторых, точно так же всегда можно удалить код 110(и неявную бесконечную последовательность нулей, которая, по предположению, следует за ним) в конце записи, поскольку этой кодовой последовательностью должно заканчиваться описание любой машины Тьюринга (во всех случаях список команд заканчивается командой R, Lили STOP ). Получающееся двоичное число— это номер машины Тьюринга, который для XN + 1будет выглядеть так:

В обычной десятичной записи этот номер равен

450813704461563958982113775643437908.

Иногда машину с номером n мы, не вполне точно, будем называть n-ймашиной Тьюринга и обозначать ее T _n . В этом случае XN +1становится

450813704461563958982113775643437908 — й

машиной Тьюринга!

Кажется поразительным факт, что нам надо пробежать так долго вдоль «списка» машин Тьюринга, чтобы найти машину, выполняющую такую тривиальную операцию, как прибавление единицы к натуральному числу (в расширенном двоичном представлении). (Я не думаю, что моя система кодирования была в целом настолько неэффективна, хотя в ней и есть еще возможности для незначительных улучшений.) В действительности, есть машины Тьюринга и с меньшими номерами, которые представляют интерес, например UN +1с двоичным номером

101011010111101010,

который в десятичной записи превращается всего лишь в 177 642. Значит, особенно тривиальная машина UN +1, которая просто дописывает 1единицу в конце последовательности единиц, является 177 642- ймашиной Тьюринга. Интересно,

что «умножение на два» в списке машин Тьюринга попадает где-то между этими двумя машинами, причем и в унарном, и в расширенном двоичном представлении: номер XN х 2равен 10 389 728 107, а номер UN х 2— 1492 923 420 919 872 026 917 547 669.

Наверное, принимая во внимание величины этих номеров, уже не вызовет удивления тот факт, что абсолютное большинство натуральных чисел не соответствует ни одной рабочей машине Тьюринга. Приведем перечень первых тринадцати машин Тьюринга в соответствии с принятой нумерацией:

Из этих машин T ₀ просто перемещается вправо, стирая все, что ей попадается на пути, никогда не останавливаясь и не меняя направления движения. Машина Т ₁ выполняет в сущности ту же операцию, но более громоздким путем, отступая на шаг назад каждый раз, когда она стирает очередную единицу на ленте. Так же как и T ₀ , машина T ₂ двигается вправо, никогда не останавливаясь, но относится к ленте более «почтительно», попросту оставляя всю информацию нетронутой. Эти машины не могут использоваться в качестве машин Тьюринга, поскольку никогда не останавливаются. T ₃ — первая в этом списке «правильная» машина: она скромно прекращает действие после того, как изменяет первую (самую левую) единицу на нуль. T ₄ сталкивается с серьезной проблемой. Найдя первую единицу на ленте, она переходит во внутреннее состояние, которое нигде не описано, и, следовательно, машина не имеет никаких команд для следующего шага. С той же проблемой сталкиваются T ₈, T ₉и T ₁₀ . С T ₇ возникают трудности еще более фундаментального характера. Строка нулей и единиц, которой она представляется, включает последовательность из пяти единиц: 110111110. Интерпретации этой последовательности не существует, поэтому T ₇ намертво застревает сразу же, как только доходит до первой единицы. (Я буду называть T ₇ , равно как и любую другую машину T _n , двоичное расширенное представлений которой содержит более четырех единиц, некорректно определенной .) Машины T ₅, T ₆и T ₁₂ испытывают те же трудности, что и T ₀, T ₁, T ₂: они просто никогда не останавливаются. Все эти машины — T ₀, T ₁, T ₂, T ₅, T ₆, T ₇, T ₈, T ₉, T ₁₀и T ₁₂ — совершенно бесполезные устройства! Только T ₃ и T ₁₁ являются функциональными машинами Тьюринга, да и то не слишком интересными. Причем T ₁₁ даже скромнее, чем T ₃ : натолкнувшись на первую же единицу, она останавливается и вообще ничего не меняет!

Надо заметить, что наш перечень содержит избыточную информацию. Машина T ₁₂ идентична T ₆ , а по действиям обе они аналогичны T ₀ , поскольку ни T ₆ , ни T ₁₂ никогда не переходят во внутреннее состояние 1. Но нам нет нужды волноваться из-за этой избыточности, равно как из-за изобилия неработоспособных (фиктивных) машин Тьюринга в нашем списке. На самом деле, мы могли бы изменить систему кодирования таким образом, чтобы избавиться от большого числа бесполезных устройств и значительно уменьшить избыточность списка машин. Но все это можно сделать только ценой усложнения нашей примитивной универсальной машины Тьюринга, которая должна расшифровывать вводимую в нее запись и имитировать машину T _n , чей номер она считала. Это было бы оправдано, если бы было можно избавиться от всех бесполезных (и повторяющихся) машин. Но это, как мы увидим чуть позднее, невозможно! Поэтому мы оставим нашу систему кодирования без изменений.

Будет удобно интерпретировать ленту с последовательностью меток на ней, например

…0001101110010000…,

как двоичное представление некоторого числа. Вспомним, что нули простираются бесконечно в обе стороны, а вот количество единиц конечно. Кроме того, я буду полагать, что их число отлично от нуля(т. е. что в этой последовательности существует хотя бы одна единица). Мы можем тогда считывать конечную строку символов между первой и последней единицами (включительно), которая в предыдущем случае имеет вид