Файл: Пеноуз Роджер. Тени разума. В поисках науки о сознании.doc

Приложение а: геделизирующая машина тьюринга в явном виде

Допустим, что у нас имеется некая алгоритмическая про­цедура А, которая, как нам известно, корректно устанавливает незавершаемость тех или иных вычислений. Мы получим вполне явную процедуру для построения на основе процедуры А кон­кретного вычисления С, для которого А оказывается неадекват­ной; при этом мы сможем убедиться, что вычисление С действи­тельно не завершается. Приняв это явное выражение для С, мы сможем определить степень его сложности и сравнить ее со сложностью процедуры А, чего требуют аргументы §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), действие которого на последовательность символов на ленте

...00111110n11111000...

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

...00111110n111110 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.)