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

Допустим, что у нас имеется некая алгоритмическая про­цедура А, которая, как нам известно, корректно устанавливает незавершаемость тех или иных вычислений. Мы получим вполне явную процедуру для построения на основе процедуры А кон­кретного вычисления С, для которого А оказывается неадекват­ной; при этом мы сможем убедиться, что вычисление С действи­тельно не завершается. Приняв это явное выражение для С, мы сможем определить степень его сложности и сравнить ее со сложностью процедуры А, чего требуют аргументы §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) может, согласно исходным допущениям, быть каким угодно. Соответственно, нас будут интересовать исключительно те числа р, для которых ма­шина Tp определена корректно. Таким образом, в записанном на ленте двоичном выражении числа р пяти символов 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» представлена команда, которую мы рассмотрели выше). (В частности, первые две команды из списка примут в данном случае следующий вид: 01->N1R, N0->(N+4)0R.)

o1->01R, 00->40R, 01->01R, 10-> 21R, 11->X, 20->31R, 21->o0R, 30->551R,
31->o0R, 40->40R, 41->51R, 50->40R, 51->61R, 60->40R, 61->71R, 70->40R,
71->81R, 80->40R, 81->91R, 90->100R, 91->o0R, 100->111R, 101->o0R, 110->121R,
111->120R, 120->131R, 121->130R, 130->141R, 131->140R, 140->151R, 141->10R, 150->00R,
151->o0R, 160->170L, 161->161L, 170->170L, 171->181L, 180->170L, 181->191L, 190->170L,
191->201L, 200->170L, 201->211L, 210->170L, 211->221L, 220->220L, 221->231L, 230->220L,
231->241L, 240->220L, 241->251L, 250->220L, 251->261L, 260->220L, 261->271L, 270->321R,
271->281L, 280->330R, 281->291L, 290->330R, 291->301L, 300->330R, 301->311L, 310->330R,
311->110R, 320->340L, 321->321R, 330->350R, 331->331R, 340->360R, 341->340R, 350->371R,
351->350R, 360->360R, 361->381R, 370->370R, 371->391R, 380->360R, 381->401R, 390->370R,
391->411R, 400->360R, 401->421R, 410->370R, 411->431R, 420->360R, 421->441R, 430->370R,
431->451R, 440->360R, 441->461R, 450->370R, 451->471R, 460->480R, 461->461R, 470->490R,
471->471R, 480->480R, 481->490R, 490->481R, 491->501R, 500->481R, 501->511R, 510->481R,
511->521R, 520->481R, 521->531R, 530->541R, 531->531R, 540->160L, 541->o0R, 550->531R.

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

А = Та и K = Tk,(=Ck).

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

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

к < а + 527 + 210 Iog2 (N + 55).

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

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

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

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

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

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

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

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

А-операцию

KK.

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

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

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

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

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