Тени разума. В поисках науки о сознании
Шрифт:
1– > 0 1R, 0 0– > 4 0R, 0 1– > 0 1R, 1 0– > 2 1R, 1 1– > X, 2 0– > 3 1R, 2 1– > 0R, 3 0– > 55 1R, 3 1– > 0R, 4 0– > 4 0R, 4 1– > 5 1R, 5 0– > 4 0R, 51 -> 6 1R, 6 0– > 4 0R, 6 1– > 7 1R, 7 0– > 4 0R, 7 1– > 8 1R, 8 0– > 4 0R, 8 1– > 9 1R, 9 0– > 10 0R, 9 1– > 0R, 10 0– > 11 1R, 10 1– > 0R, 11 0– > 12 1R, 11 1– > 12 0R, 12 0– > 13 1R, 12 1– > 13 0R, 13 0– > 14 1R, 13 1– > 14 0R, 14 0– > 15 1R, 14 1– > 1 0R, 15 0– > 0 0R, 15 1– > 0R, 16 0– > 17 0L, 16 1– > 16 1L, 17 0– > 17 0L, 17 1– > 18 1L, 18 0– > 17 0L, 18 1– > 19 1L, 19 0– > 17 0L, 191 -> 20 1L, 20 0– > 17 0L, 20 1– > 21 1L, 21 0– > 17 0L, 21 1– > 22 1L, 22 0– > 22 0L, 22 1– > 23 1L, 23 0– > 22 0L, 23 1– > 24 1L, 24 0– > 22 0L, 24 1– > 25 1L, 25 0– > 22 0L, 251 -> 26 1L, 26 0– > 22 0L, 26 1– > 27 1L, 27 0– > 32 1R, 27 1– > 28 1L, 28 0– > 33 0R, 28 1– > 29 1L, 29 0– > 33 0R, 29 1– > 30 1L, 30 0– > 33 0R, 30 1– > 31 1L, 31 0– > 33 0R, 31 1– > 11 0R, 32 0– > 34 0L, 32 1– > 32 1R, 33 0– > 35 0R, 33 1– > 33 1R, 34 0– > 36 0R, 34 1– > 34 0R, 35 0– > 37 1R, 35 1– > 35 0R, 36 0– > 36 0R, 36 1– > 38 1R, 37 0– > 37 0R, 37 1– > 39 1R, 38 0– > 36 0R, 38 1– > 40 1R, 39 0– > 37 0R, 39 1– > 41 1R, 40 0– > 36 0R, 40 1– > 42 1R, 41 0– > 37 0R, 41 1– > 43 1R, 42 0– > 36 0R, 42 1– > 44 1R, 43 0– > 37 0R, 43 1– > 45 1R, 44 0– > 36 0R, 44 1– > 46 1R, 45 0– > 37 0R, 45 1– > 47 1R, 46 0– > 48 0R, 46 1– > 46 1R, 47 0– > 49 0R, 47 1– > 47 1R, 48 0– > 48 0R, 48 1– > 49 0R, 49 0– > 48 1R, 49 1– > 50 1R, 50 0– > 48 1R, 50 1– > 51 1R, 51 0– > 48 1R, 51 1– > 52 1R, 52 0– > 48 1R, 52 1– > 53 1R, 53 0– > 54 1R, 53 1– > 53 1R, 54 0– > 16 0L, 54 1– > 0R, 55 0– > 53 1R.
Теперь
A = T aи K= T k'(= C k).
Поскольку алгоритм Aсодержит, как минимум, 2 N– 1 команд (учитывая, что первую команду мы исключили) и поскольку для каждой команды требуется, по крайней мере, три двоичные цифры, общее число двоичных цифр в номере его машины Тьюринга а непременно должно удовлетворять условию
>= 6 N– 6.
В вышеприведенном дополнительном списке команд для Kесть 105 мест (справа от стрелок), где к имеющемуся там числу следует прибавить N. Все получаемые при этом числа не превышают N+ 55, а потому их расширенные двоичные представления содержат не более 2 log 2( N+ 55) цифр, в результате чего общее количество двоичных цифр, необходимых для дополнительного определения внутренних состояний, не превышает 210 log 2( N+ 55).
< + 527 + 210 log 2( N+ 55).
Применив полученное выше соотношение >= 6 N– 6, получим (учитывая, что 210 log 26 > 542)
< - 15 + 210 log 2( + 336).
Затем найдем степень сложности конкретного вычисления C k( k), получаемого посредством этой процедуры. Вспомним, что степень сложности машины T m( n) определяется как количество двоичных цифр в большем из двух чисел m, n. В данной ситуации C k= T k, так что число двоичных цифр в числе « m» этого вычисления равно . Для того чтобы определить, сколько двоичных цифр содержит число « n» этого вычисления, рассмотрим ленту, содержащую вычисление C k( k). Эта лента начинается с последовательности символов 111110, за которой следует двоичное выражение числа k', и завершается последовательностью 11011111. В соответствии с предложенным в НРК соглашением всю эту последовательность (без последней цифры) следует читать как двоичное число; эта операция дает нам номер « n», который присваивается ленте машины, выполняющей вычисление T m( n). То есть число двоичных цифр в данном конкретном номере « n» равно + 13, и, следовательно, число + 13 совпадает также со степенью сложности ту вычисления C k( k), благодаря чему мы можем записать = + 13 < — 2 + 210 log 2( + 336), или проще:
< + 210 log 2( + 336).
Детали вышеприведенного рассуждения специфичны для данного конкретного предложенного еще в НРК способа кодирования машин Тьюринга, и при использовании какого-либо иного кодирования они также будут несколько иными. Основная же идея очень проста. Более того, прими мы формализм - исчисления, вся операция оказалась бы, в некотором смысле, почти тривиальной. (Достаточно обстоятельное описание -исчисления Черча можно найти в НРК, конец главы 2; см. также [ 52 ].) Предположим, например, что алгоритм Aопределяется некоторым -оператором A, выполняющим действие над другими операторами Pи Q, что выражается в виде операции ( AP) Q. Оператором Pздесь представлено вычисление C p, а оператором Q— число q. Далее, оператор Aдолжен удовлетворять известному требованию, согласно которому для любых Pи Qдолжно быть истинным следующее утверждение:
Если завершается операция ( AP) Q, то операция PQне завершается.
Мы без труда можем составить такую операцию -исчисления, которая не завершается, однако этот факт невозможно установить посредством оператора A. Например, положим
K = x.[( Ax) x],
т.е. KY= ( AY) Yдля любого оператора Y. Затем рассмотрим -операцию
KK
Очевидно, что эта операция не завершается, поскольку KK= ( AK) K, а завершение последней операции означало бы, что операция KKне завершается по причине принятой нами природы оператора A. Более того, оператор Aне способен установить этот факт, потому что операция ( AK) Kне завершается. Если мы полагаем, что оператор Aобладает требуемым свойством, то мы также должны предположить, что операция KKне завершается.
Отметим, что данная процедура дает значительную экономию. Если записать операцию KKв виде
KK = y.( yy)( x.[( Ax) x]),
то становится ясно, что число символов в записи операции KKвсего на 16 больше аналогичного числа символов для алгоритма A(если пренебречь точками, которые в любом случае избыточны)!
Строго говоря, это не совсем законно, поскольку в выражении для оператора Aможет также появиться и символ « x», и с этим нам придется что-то делать. Можно усмотреть сложность и в том, что генерируемое такой процедурой незавершающееся вычисление нельзя считать операцией над натуральными числами (поскольку вторая Kв записи KK«числом» не является). Вообще говоря, -исчисление не вполне подходит для работы с явными численными операциями, и зачастую бывает довольно сложно понять, каким образом ту или иную заданную алгоритмическую процедуру, применяемую к натуральным числам, можно выразить в виде операции -исчисления. По этим и подобным причинам обсуждение с привлечением машин Тьюринга имеет, как нам представляется, более непосредственное отношение к теме нашего исследования и достигает требуемого результата более наглядным путем.