Теперь мы готовы точно определить предельную длину предписания K, получаемого путем вышеприведенного построения, как функцию от длины алгоритма A. Сравним эту «длину» со «степенью сложности», определенной в §2.6(в конце комментария к возражению Q8). Для некоторой конкретной машины Тьюринга T m(например, той, что выполняет вычисление A) эта величина равна количеству знаков в двоичном представлении числа m. Для некоторого конкретного машинного действия T m( n) (например, выполнения предписания K) эта величина равна количеству двоичных цифр в большем из чисел тип. Обозначим через αи κколичество двоичных цифр в aи k'соответственно, где
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). Сюда нужно добавить цифры, необходимые для добавочных символов 0, 1, Rи L, что составляет еще 527 цифр (включая одну возможную добавочную «команду-пустышку» и учитывая, что мы можем исключить шесть символов 0по правилу, согласно которому 0 0можно представить в виде 0). Таким образом, для определения предписания Kтребуется больше двоичных цифр, чем для определения алгоритма A, однако разница между этими двумя величинами не превышает 527 + 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«числом» не является). Вообще говоря, λ-исчисление не вполне подходит для работы с явными численными операциями, и зачастую бывает довольно сложно понять, каким образом ту или иную заданную алгоритмическую процедуру, применяемую к натуральным числам, можно выразить в виде операции λ-исчисления. По этим и подобным причинам обсуждение с привлечением машин Тьюринга имеет, как нам представляется, более непосредственное отношение к теме нашего исследования и достигает требуемого результата более наглядным путем.
3. О невычислимости в математическом мышлении
3.1. Гёдель и Тьюринг
В главе 2была предпринята попытка продемонстрировать мощь и строгий характер аргументации в пользу утверждения (обозначенного буквой G), суть которого заключается в том, что математическое понимание не может являться результатом применения какого-либо осмысленно осознаваемого и полностью достоверного алгоритма (или, что то же самое, алгоритмов; см. возражение Q1). В приводимых рассуждениях, однако, ни словом не упомянуто еще об одной возможности, существенно более серьезной и ничуть не противоречащейутверждению G, а именно: убежденность математика в истинности своих выводов может оказаться результатом применения им некоего неизвестного и неосознаваемого алгоритма, или же, возможно, математик применяет какой-то вполне постижимый алгоритм, однако при этом не может знать наверняка (или хотя бы искренне верить), что выводы его являются целиком и полностью результатом применения этого самого алгоритма. Ниже я покажу, что, хотя подобные допущения и вполне приемлемы с логической точки зрения, вряд ли их можно счесть хоть сколько-нибудь правдоподобными.