ГЕДЕЛИЗИРУЮЩАЯ МАШИНА ТЬЮРИНГА В ЯВНОМ ВИДЕ

Допустим, что у нас имеется некая алгоритмическая про­цедура А, которая, как нам известно, корректно устанавливает незавершаемость тех или иных вычислений. Мы получим вполне явную процедуру для построения на основе процедуры А кон­кретного вычисления С, для которого А оказывается неадекват­ной; при этом мы сможем убедиться, что вычисление С действи­тельно не завершается. Приняв это явное выражение для С, мы сможем определить степень его сложности и сравнить ее со сложностью процедуры А, чего требуют аргументы §2.6 (возра­жение Q8) и §3.20.

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

Машина Тьюринга имеет конечное число внутренних состо­яний, но производит все операции на бесконечной ленте. Эта лен­та представляет собой линейную последовательность «ячеек», причем каждая ячейка может быть маркированной или пустой, а общее количество отметок на ленте — величина конечная. Обо­значим каждую маркированную ячейку символом 1, а каждую пустую ячейку — 0. В машине Тьюринга имеется также считы­вающее устройство, которое поочередно рассматривает отметки и, в явной зависимости от внутреннего состояния машины Тью­ринга и характера рассматриваемой в данный момент отметки, определяет дальнейшие действия машины по следующим трем пунктам: (i) следует ли изменить рассматриваемую в данный мо­мент отметку; (ii) каким будет новое внутреннее состояние ма­шины; (iii) должно ли устройство сдвинуться по ленте на один шаг вправо (обозначим это действие через R) или влево (обозна­чим через L), или же на один шаг вправо с остановкой машины (STOP). Когда машина, в конце концов, остановится, на лен­те слева от считывающего устройства будет представлен в виде последовательности символов 0 и 1 ответ на выполненное ею вычисление. Изначально лента должна быть абсолютно чистой, за исключением отметок, описывающих исходные данные (в виде конечной строки символов 1 и 0), над которыми машина и бу­дет выполнять свои операции. Считывающее устройство в начале работы располагается слева от всех отметок.

При представлении на ленте натуральных чисел (будь то входные или выходные данные) иногда удобнее использовать так называемую расширенную двоичную запись, согласно которой число, в сущности, записывается в обычной двоичной системе счисления, только двоичный знак «1» представляется символа­ми 10, а двоичный знак «0» — символом 0. Таким образом, мы получаем следующую схему перевода десятичных чисел в расши­ренные двоичные:

0 <-> 0
1 <-> 10
2 <-> 100
3 <-> 1010
4 <-> 1000
5 <-> 10010
6 <-> 10100
7 <-> 101010
8 <-> 10000
9 <-> 100010
10 <-> 100100
11 <-> 1001010
12 <-> 101000
13 <-> 1010010
14 <-> 1010100
15 <-> 10101010
16 <-> 100000
17 <-> 1000010
и т.д.

 

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

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

R <-> 110

L <-> 1110

STOP <->11110.

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

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

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

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

Получаемая в результате последовательность символов О и 1 представляет собой самую обыкновенную (т. е. нерасширен­ную) двоичную запись номера машины Тьюринга п для дан­ной машины (см. главу 2 НРК). Мы называем ее n-й машиной Тьюринга и обозначаем Т = Т_n. Каждый такой двоичный номер (с добавлением в конце последовательности 110) есть после­довательность символов 0 и 1, в которой нигде не встречается более четырех 1 подряд. Номер n, не удовлетворяющий данному условию, определяет «фиктивную машину Тьюринга», которая прекратит работать, как только встретит «команду», содержа­щую более четырех 1. Такую машину «Тn» мы будем называть некорректно определенной. Ее работа с какой угодно лен­той является по определению незавершающейся. Аналогично, если действующая машина Тьюринга встретит команду перехода в состояние, определенное числом, большим всех тех чисел, для которых были явно заданы возможные последующие действия, то она также «зависнет»: такую машину мы будем полагать «фик­тивной», а ее работу — незавершающейся. (Всех этих неудобств можно без особого труда избежать с помощью тех или иных технических средств, однако реальной необходимости в этом нет; CM.§2.6,Q4).

Для того чтобы понять, как на основе заданного алгоритма А построить явное незавершающееся вычисление, факт незавершаемости которого посредством алгоритма А установить невоз­можно, необходимо предположить, что алгоритм А задан в виде машины Тьюринга. Эта машина работает с лентой, на которой кодируются два натуральных числа p и q. Мы полагаем, что если завершается вычисление А(р, q), то вычисление, производимое машиной Т_р с числом q, не завершается вовсе. Вспомним, что если машина Т_р определена некорректно, то ее работа с числом q не завершается, каким бы это самое q ни было. В случае тако­го «запрещенного» р исход вычисления А(р, q) может, согласно исходным допущениям, быть каким угодно. Соответственно, нас будут интересовать исключительно те числа р, для которых ма­шина T_p определена корректно. Таким образом, в записанном на ленте двоичном выражении числа р пяти символов 1 подряд содержаться не может. Значит, для обозначения на ленте начала и конца числа р мы вполне можем воспользоваться последова­тельностью 11111.

То же самое, очевидно, необходимо сделать и для числа q, причем оно вовсе не обязательно должно быть числом того же типа, что и р. Здесь перед нами возникает техническая проблема, связанная с чрезвычайной громоздкостью машинных предписа­ний в том виде, в каком они представлены в НРК. Удобным ре­шением этой проблемы может стать запись чисел р и q в пяте­ричной системе счисления. (В этой системе запись «10» озна­чает число пять, «100» — двадцать пять, «44» — двадцать четыре и т.д.) Однако вместо пятеричных цифр 0, 1, 2, 3 и 4 я воспользуюсь соответствующими последовательностями симво­лов на ленте 0, 10, 110, 1110 и 11110. Таким образом, мы будем записывать

0 как 0

1 “ 10

2 “ 110

3 “ 1110

4 “ 11110

5 “ 100

6 “ 1010

7 “ 10110

8 “ 101110

9 “ 1011110

10 “ 1100

11 “ 11010

12 “ 110110

13 “ 1101110

14 “ 11011110

15 “ 11100

16 “ 111010

… …

25 “ 1000

26 “ 10010

и т.д.

Под «Ср» здесь будет пониматься вычисление, выполняемое корректно определенной машиной Тьюринга Т_г, где г есть число, обыкновенное двоичное выражение которого (с добавлением в конце последовательности символов 110) в точности совпадает с числом р в нашей пятеричной записи. Число q, над которым производится вычисление С_р, также необходимо представлять в пятеричном выражении. Вычисление же А(р, q) задается в виде машины Тьюринга, выполняющей действие с лентой, на которой кодируется пара чисел р, q. Запись на ленте будет выглядеть следующим образом:

...00111110p111110q11111000...,

где p и q суть вышеописанные пятеричные выражения чисел, соответственно, р и q.

Требуется отыскать такие числа р и д, для которых не за­вершается не только вычисление С_р (q), но и вычисление А(р, д). Процедура из § 2.5 позволяет сделать это посредством отыскания такого числа k, при котором вычисление Ck, производимое с чис­лом п, в точности совпадает с вычислением А(п, п) при любом п, и подстановки р — q = k. Для того чтобы проделать это же в явном виде, отыщем машинное предписание К (— Ck), действие которого на последовательность символов на ленте