Геделизирующая машина Тьюринга в явном виде

Допустим, что у нас имеется некая алгоритмическая про­цедура А, которая, как нам известно, корректно устанавливает незавершаемость тех или иных вычислений. Мы получим вполне явную процедуру для построения на основе процедуры А кон­кретного вычисления С, для которого А оказывается неадекват­ной; при этом мы сможем убедиться, что вычисление С действи­тельно не завершается. Приняв это явное выражение для С, мы сможем определить степень его сложности и сравнить ее со сложностью процедуры А, чего требуют аргументы §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 и переместиться по ленте на один шаг вправо». В этом случае часть «17 1 R» данной команды будет кодироваться по­следовательностью 100001010110. Разбив ее на участ­ки 1000010.10.110, мы видим, что первый из них представляет собой расширенную двоичную запись числа 17, второй кодирует отметку 1 на ленте, а третий — команду «пе­реместиться на шаг вправо». А как нам описать предыдущее внутреннее состояние (в данном случае 23) и считываемую в со­ответствующий момент отметку на ленте (в данном случае 0)? При желании можно задать их так же явно с помощью расши­ренной двоичной записи. Однако, в действительности, в этом нет необходимости, поскольку для этого будет достаточно упорядо­чить различные команды в виде цифровой последовательности (например, такой: 00 ->, Ol ->, 10 ->, 11 ->, 20 ->, 21 ->, 30->,...).

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

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

N11111000...

(где П есть пятеричная запись числа п) в точности совпадает с действием алгоритма А на последовательность

N111110 n11111000...

при любом п. Таким образом, действие предписания К сводится к тому, чтобы взять число п (записанное в пятеричном выраже­нии) и однократно его скопировать, при этом два П разделяют­ся последовательностью 111110 (та же последовательность начинает и завершает всю последовательность отметок на лен­те). Следовательно, оно воздействует на получаемую в результате ленту точно так, как на эту же ленту воздействовал бы алго­ритм А.

Явную модификацию алгоритма А, дающую такое предпи­сание К, можно произвести следующим образом. Сначала на­ходим в определении А начальную команду Ol —> X и отмечаем для себя, что это в действительности за «X». Мы подставим это выражение вместо «X» в спецификации, представленной ниже. Один технический момент: следует, помимо прочего, положить, чтобы алгоритм А был составлен таким образом, чтобы машина, после активации команды Ol —* X, никогда больше не перешла во внутреннее состояние 0 алгоритма А. Это требование ни в коей мере не влечет за собой каких-либо существенных ограни­чений на форму алгоритма. (Ноль можно использовать только в командах-пустышках.)

Затем при определении алгоритма А необходимо устано­вить общее число N внутренних состояний (включая и состоя­ние 0, т. е. максимальное число внутренних состояний А будет равно N — 1). Если в определении А нет завершающей коман­ды вида (N — 1)1 —> Y, то в конце следует добавить команду-пустышку (N — 1)1 —» OUR. Наконец, удалим из определения А команду Ol —* X и добавим ее к приводимому ниже списку ма­шинных команд, а каждый номер внутреннего состояния, фигури­рующий в этом списке, увеличим на N (символом 0 обозначено результирующее внутреннее состояние 0, а символом «X» в за­писи «11 -> X» представлена команда, которую мы рассмотрели выше). (В частности, первые две команды из списка примут в данном случае следующий вид: 0 1 ->N 1 R, N 0 ->(N+4) 0 R.)

o 1 ->0 1 R, 0 0 ->4 0 R, 0 1 ->0 1 R, 1 0 -> 2 1 R, 1 1 ->X, 2 0 ->3 1 R, 2 1 ->o 0 R, 3 0 ->55 1 R,
3 1 ->o 0 R, 4 0 ->4 0 R, 4 1 ->5 1 R, 5 0 ->4 0 R, 5 1 ->6 1 R, 6 0 ->4 0 R, 6 1 ->7 1 R, 7 0 ->4 0 R,
7 1 ->8 1 R, 8 0 ->4 0 R, 8 1 ->9 1 R, 9 0 ->10 0 R, 9 1 ->o 0 R, 10 0 ->11 1 R, 10 1 ->o 0 R, 11 0 ->12 1 R,
11 1 ->12 0 R, 12 0 ->13 1 R, 12 1 ->13 0 R, 13 0 ->14 1 R, 13 1 ->14 0 R, 14 0 ->15 1 R, 14 1 ->1 0 R, 15 0 ->0 0 R,
15 1 ->o 0 R, 16 0 ->17 0 L, 16 1 ->16 1 L, 17 0 ->17 0 L, 17 1 ->18 1 L, 18 0 ->17 0 L, 18 1 ->19 1 L, 19 0 ->17 0 L,
19 1 ->20 1 L, 20 0 ->17 0 L, 20 1 ->21 1 L, 21 0 ->17 0 L, 21 1 ->22 1 L, 22 0 ->22 0 L, 22 1 ->23 1 L, 23 0 ->22 0 L,
23 1 ->24 1 L, 24 0 ->22 0 L, 24 1 ->25 1 L, 25 0 ->22 0 L, 25 1 ->26 1 L, 26 0 ->22 0 L, 26 1 ->27 1 L, 27 0 ->32 1 R,
27 1 ->28 1 L, 28 0 ->33 0 R, 28 1 ->29 1 L, 29 0 ->33 0 R, 29 1 ->30 1 L, 30 0 ->33 0 R, 30 1 ->31 1 L, 31 0 ->33 0 R,
31 1 ->11 0 R, 32 0 ->34 0 L, 32 1 ->32 1 R, 33 0 ->35 0 R, 33 1 ->33 1 R, 34 0 ->36 0 R, 34 1 ->34 0 R, 35 0 ->37 1 R,
35 1 ->35 0 R, 36 0 ->36 0 R, 36 1 ->38 1 R, 37 0 ->37 0 R, 37 1 ->39 1 R, 38 0 ->36 0 R, 38 1 ->40 1 R, 39 0 ->37 0 R,
39 1 ->41 1 R, 40 0 ->36 0 R, 40 1 ->42 1 R, 41 0 ->37 0 R, 41 1 ->43 1 R, 42 0 ->36 0 R, 42 1 ->44 1 R, 43 0 ->37 0 R,
43 1 ->45 1 R, 44 0 ->36 0 R, 44 1 ->46 1 R, 45 0 ->37 0 R, 45 1 ->47 1 R, 46 0 ->48 0 R, 46 1 ->46 1 R, 47 0 ->49 0 R,
47 1 ->47 1 R, 48 0 ->48 0 R, 48 1 ->49 0 R, 49 0 ->48 1 R, 49 1 ->50 1 R, 50 0 ->48 1 R, 50 1 ->51 1 R, 51 0 ->48 1 R,
51 1 ->52 1 R, 52 0 ->48 1 R, 52 1 ->53 1 R, 53 0 ->54 1 R, 53 1 ->53 1 R, 54 0 ->16 0 L, 54 1 ->o 0 R, 55 0 ->53 1 R.

Теперь мы готовы точно определить предельную длину пред­писания К, получаемого путем вышеприведенного построения, как функцию от длины алгоритма А. Сравним эту «длину» со «степенью сложности», определенной в § 2.6 (в конце коммента­рия к возражению Q8). Для некоторой конкретной машины Тью­ринга Т_т (например, той, что выполняет вычисление А) эта ве­личина равна количеству знаков в двоичном представлении чис­ла т. Для некоторого конкретного машинного действия Т_т(п) (например, выполнения предписания К) эта величина равна ко­личеству двоичных цифр в большем из чисел тип. Обозначим через а и к количество двоичных цифр в а и ' k' соответственно, где

А = Т_а и K = T_k,(=C_k).

Поскольку алгоритм А содержит, как минимум, 2N — 1 команд (учитывая, что первую команду мы исключили) и поскольку для каждой команды требуется, по крайней мере, три двоичные циф­ры, общее число двоичных цифр в номере его машины Тьюринга а непременно должно удовлетворять условию

В вышеприведенном дополнительном списке команд для К есть 105 мест (справа от стрелок), где к имеющемуся там числу сле­дует прибавить N. Все получаемые при этом числа не превыша­ют N + 55, а потому их расширенные двоичные представления содержат не более 2 Iog₂ (N + 55) цифр, в результате чего общее количество двоичных цифр, необходимых для дополнительного определения внутренних состояний, не превышает 210 Iog₂ (N + + 55). Сюда нужно добавить цифры, необходимые для добавоч­ных символов 0, 1, R и L, что составляет еще 527 цифр (включая одну возможную добавочную «команду-пустышку» и, учитывая, что мы можем исключить шесть символов 0 по правилу, согласно которому 00 можно представить в виде 0). Таким образом, для определения предписания К требуется больше двоичных цифр, чем для определения алгоритма А, однако разница между этими двумя величинами не превышает 527 + 210 Iog₂ (N -f 55):

к < а + 527 + 210 Iog₂ (N + 55).

Применив полученное выше соотношение , получим (учитывая, что 210 Iog₂ 6 > 542)

к < а - 15 + 210 Iog₂ (a + 336).

Затем найдем степень сложности г? конкретного вычисле­ния Ck (k), получаемого посредством этой процедуры. Вспомним, что степень сложности машины Т_т (п) определяется как коли­чество двоичных цифр в большем из двух чисел т, п. В данной ситуации Ck = Tk, так что число двоичных цифр в числе «т» этого вычисления равно к. Для того, чтобы определить, сколько двоичных цифр содержит число «п» этого вычисления, рассмот­рим ленту, содержащую вычисление Ck (k). Эта лента начинается с последовательности символов 111110, за которой следует двоичное выражение числа k', и завершается последовательно­стью 11011111. В соответствии с предложенным в НРК соглашением всю эту последовательность (без последней циф­ры) следует читать как двоичное число; эта операция дает нам номер «п», который присваивается ленте машины, выполняющей вычисление Т_т (п). То есть число двоичных цифр в данном кон­кретном номере «п» равно к + 13, и, следовательно, число к + 13 совпадает также со степенью сложности г/ вычисления Ck (k),. благодаря чему мы можем записать г) = к + 13 < а — 2 4-+ 210 Iog₂ (а + 336), или проще:

?7<a + 2101og₂(a-l-336).

Детали вышеприведенного рассуждения специфичны для данного конкретного предложенного еще в НРК способа кодиро­вания машин Тьюринга, и при использовании какого-либо иного кодирования они также будут несколько иными. Основная же идея очень проста. Более того, прими мы формализм Х-исчисления, вся операция оказалась бы, в некотором смысле, почти тривиальной. (Достаточно обстоятельное описание Л-исчисления Черча можно найти в НРК., конец главы 2; см. также [52].) Пред­положим, например, что алгоритм А определяется некоторым А-оператором А, выполняющим действие над другими оператора­ми Р и Q, что выражается в виде операции (АР) Q. Оператором Р здесь представлено вычисление С_р, а оператором Q — число q. Далее, оператор А должен удовлетворять известному требова­нию, согласно которому для любых Р и Q должно быть истинным следующее утверждение:

Если завершается операция (АР) Q, то операция PQ не завершается.

Мы без труда можем составить такую операцию Л-исчисления, которая не завершается, однако этот факт невозможно устано­вить посредством оператора А. Например, положим

К = Ах.[(Ах)х], т.е. KY = (AY)Y для любого оператора Y. Затем рассмотрим

А-операцию

KK.

Очевидно, что эта операция не завершается, поскольку КК = = (АК) К, а завершение последней операции означало бы, что операция КК не завершается по причине принятой нами приро­ды оператора А. Более того, оператор А не способен установить этот факт, потому что операция (АК) К не завершается. Если мы полагаем, что оператор А обладает требуемым свойством, то мы также должны предположить, что операция КК не завершает­ся.

Отметим, что данная процедура дает значительную эконо­мию. Если записать операцию КК в виде

КК = Ау.(уу)(Ах.[(Ах)х]),

то становится ясно, что число символов в записи операции КК всего на 16 больше аналогичного числа символов для алгорит­ма А (если пренебречь точками, которые в любом случае избы­точны)!

Строго говоря, это не совсем законно, поскольку в выраже­нии для оператора А может также появиться и символ «х», и с этим нам придется что-то делать. Можно усмотреть сложность и в том, что генерируемое такой процедурой незавершающееся вычисление нельзя считать операцией над натуральными числами (поскольку вторая К в записи КК «числом» не является). Вообще говоря, А-исчисление не вполне подходит для работы с явными численными операциями, и зачастую бывает довольно сложно понять, каким образом ту или иную заданную алгоритмическую процедуру, применяемую к натуральным числам, можно выра­зить в виде операции А-исчисления. По этим и подобным при­чинам обсуждение с привлечением машин Тьюринга имеет, как нам представляется, более непосредственное отношение к теме нашего исследования и достигает требуемого результата более наглядным путем.