Тени разума. В поисках науки о сознании

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

α ≥ 6N - 6.

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

κ < α + 527 + 210 log₂(N + 55).

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

κ < α - 15 + 210 log₂(α + 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₂(α + 336), или проще:

η < α + 210 log₂(α + 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 (если пренебречь точками, которые в любом случае избыточны)!