Тени разума. В поисках науки о сознании
Шрифт:
Согласно вышеприведенным предписаниям, в кодированной спецификации машины Тьюринга на ленте пара символов 0 0должна быть представлена последовательностью 00, однако можно поступить более экономно и записать просто 0, что явится ничуть не менее однозначным разделителем двух последовательностей, составленных из более чем одного символа 1 подряд [18] . Машина Тьюринга начинает работу, находясь во внутреннем состоянии 0; считывающее устройство движется по ленте, сохраняя это внутреннее состояние до тех пор, пока не встретит первый символ 1. Это обусловлено допущением, что в набор команд машины Тьюринга всегда входит операция 0 0– > 0 0R. Таким образом, в действительной спецификации машины Тьюринга в виде последовательности 0и 1явного задания этой команды не требуется; вместо этого мы начнем с команды 0 1– > X, где Xобозначает первую нетривиальную операцию запущенной машины, т.е. первый символ 1, встретившийся ей на ленте. Это значит, что начальную последовательность 110(команду -> 0 0R), которая в противном
18
Это означает, что при кодировании машины Тьюринга каждую последовательность … 110011… можно заменить на … 11011… . В спецификации универсальной машины Тьюринга, описанной в НРК (см. примечание 7 после главы 2), имеется пятнадцать мест, где я этого не сделал. Чрезвычайно досадная оплошность с моей стороны, и это после того, как я приложил столько усилий, чтобы добиться (в рамках моих же собственных правил) по возможности наименьшего номера, определяющего эту универсальную машину. Упомянутая простая замена позволяет уменьшить мой номер более чем в 30 000 раз! Я благодарен Стивену Ганхаусу за то, что он указал мне на этот недосмотр, а также за то, что он самостоятельно проверил всю представленную в НРК спецификацию и подтвердил, что она действительноопределяет универсальную машину Тьюринга.
Получаемая в результате последовательность символов 0и 1представляет собой самую обыкновенную (т.е. нерасширенную) двоичную запись номера машины Тьюринга nдля данной машины (см. главу 2 НРК). Мы называем ее n– й машиной Тьюринга и обозначаем T= T n. Каждый такой двоичный номер (с добавлением в конце последовательности 110) есть последовательность символов 0и 1, в которой нигде не встречается более четырех 1подряд. Номер n, не удовлетворяющий данному условию, определяет «фиктивную машину Тьюринга», которая прекратит работать, как только встретит «команду», содержащую более четырех 1. Такую машину « T n» мы будем называть некорректно определенной. Ее работа с какой угодно лентой является по определениюнезавершающейся. Аналогично, если действующая машина Тьюринга встретит команду перехода в состояние, определенное числом, большим всех тех чисел, для которых были явно заданы возможные последующие действия, то она также «зависнет»: такую машину мы будем полагать «фиктивной», а ее работу — незавершающейся. (Всех этих неудобств можно без особого труда избежать с помощью тех или иных технических средств, однако реальной необходимости в этом нет; см. §2.6 , Q4).
Для того чтобы понять, как на основе заданного алгоритма Aпостроить явное незавершающееся вычисление, факт незавершаемости которого посредством алгоритма Aустановить невозможно, необходимо предположить, что алгоритм Aзадан в виде машины Тьюринга. Эта машина работает с лентой, на которой кодируются два натуральных числа pи q. Мы полагаем, что если завершается вычисление A( p, q), то вычисление, производимое машиной T pс числом q, незавершается вовсе. Вспомним, что если машина T pопределена некорректно, то ее работа с числом qне завершается, каким бы это самое qни было. В случае такого «запрещенного» pисход вычисления A( p, q) может, согласно исходным допущениям, быть каким угодно. Соответственно, нас будут интересовать исключительно те числа p, для которых машина T pопределена корректно. Таким образом, в записанном на ленте двоичном выражении числа pпяти символов 1подряд содержаться не может. Значит, для обозначения на ленте начала и конца числа pмы вполне можем воспользоваться последовательностью 11111.
То же самое, очевидно, необходимо сделать и для числа q, причем оно вовсе необязательно должно быть числом того же типа, что и p. Здесь перед нами возникает техническая проблема, связанная с чрезвычайной громоздкостью машинных предписаний в том виде, в каком они представлены в НРК. Удобным решением этой проблемы может стать запись чисел pи 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
14 как 11011110
15 как 11100
16 как 111010
…
25 как 1000
26 как 10010
и т.д.
Под « C p» здесь будет пониматься вычисление, выполняемое корректно определенной машиной Тьюринга T r, где rесть число, обыкновенное двоичное выражение которого (с добавлением в конце последовательности символов 110) в точности совпадает с числом pв нашей пятеричной записи. Число q, над которым производится вычисление C p, также необходимо представлять в пятеричном выражении. Вычисление же A( p, q) задается в виде машины Тьюринга, выполняющей действие с лентой, на которой кодируется пара чисел p, q. Запись на ленте будет выглядеть следующим образом:
… 00111110p111110q11111000…,
где pи qсуть вышеописанные пятеричные выражения чисел, соответственно, pи q.
Требуется отыскать такие числа pи q, для которых не завершается не только вычисление C p( q), но и вычисление A( p, q). Процедура из §2.5 позволяет сделать это посредством отыскания такого числа k, при котором вычисление C k, производимое с числом n, в точности совпадает с вычислением A( n, n) при любом n, и подстановки p= q= k. Для того чтобы проделать это же в явном виде, отыщем машинное предписание K(= C k), действие которого на последовательность символов на ленте
… 00111110n11111000…
(где nесть пятеричная запись числа n) в точности совпадает с действием алгоритма Aна последовательность
… 00111110n111110n11111000…
при любом n. Таким образом, действие предписания Kсводится к тому, чтобы взять число n(записанное в пятеричном выражении) и однократно его скопировать, при этом два n разделяются последовательностью 111110(та же последовательность начинает и завершает всю последовательность отметок на ленте). Следовательно, оно воздействует на получаемую в результате ленту точно так, как на эту же ленту воздействовал бы алгоритм A.
Явную модификацию алгоритма A, дающую такое предписание K, можно произвести следующим образом. Сначала находим в определении Aначальную команду 0 1– > Xи отмечаем для себя, что это в действительности за « X». Мы подставим это выражение вместо « X» в спецификации, представленной ниже. Один технический момент: следует, помимо прочего, положить, чтобы алгоритм Aбыл составлен таким образом, чтобы машина, после активации команды 0 1– > X, никогда больше не перешла во внутреннее состояние 0 алгоритма A. Это требование ни в коей мере не влечет за собой каких-либо существенных ограничений на форму алгоритма [19] . (Нуль можно использовать только в командах-пустышках.)
19
Более того, сам Тьюринг первоначально предполагал вообще останавливатьмашину всякий раз, когда она повторно переходит во внутреннее состояние «0» из любого другого состояния. В этом случае нам не только не понадобилось бы вышеупомянутое ограничение, мы спокойно могли бы обойтись и без команды STOP. Тем самым мы достигли бы существенного упрощения, поскольку последовательность 11110в качестве команды нам была бы уже не нужна, и ее можно было бы использовать как разделитель, что позволило бы избавиться от последовательности 111110. Это значительно сократило бы длину предписания K, и, кроме того, вместо пятеричной системы счисления мы обошлись бы четверичной.
Затем при определении алгоритма Aнеобходимо установить общее число Nвнутренних состояний (включая и состояние 0, т.е. максимальное число внутренних состояний Aбудет равно N– 1). Если в определении Aнет завершающей команды вида ( N– 1) 1– > Y, то в конце следует добавить команду-пустышку ( N– 1) 1– > 0 0R. Наконец, удалим из определения Aкоманду 0 1– > Xи добавим ее к приводимому ниже списку машинных команд, а каждый номер внутреннего состояния, фигурирующий в этом списке, увеличим на N(символом обозначено результирующее внутреннее состояние 0, а символом « X» в записи «1 1– > X» представлена команда, которую мы рассмотрели выше). (В частности, первые две команды из списка примут в данном случае следующий вид: 0 1– > N 1R, N 0– > (N + 4) 0R.)