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

o1->01R,        00->40R,         01->01R,        10-> 21R,       11->X,             20->31R,        21->o0R,        30->551R, 31->o0R,        40->40R,         41->51R,        50->40R,        51->61R,         60->40R,        61->71R,         70->40R, 71->81R,        80->40R,         81->91R,        90->100R,      91->o0R,        100->111R,    101->o0R,      110->121R, 111->120R,    120->131R,     121->130R,    130->141R,    131->140R,     140->151R,    141->10R,       150->00R, 151->o0R,      160->170L,     161->161L,    170->170L,     171->181L,     180->170L,     181->191L,     190->170L, 191->201L,     200->170L,     201->211L,    210->170L,     211->221L,     220->220L,     221->231L,     230->220L, 231->241L,     240->220L,     241->251L,    250->220L,     251->261L,     260->220L,     261->271L,     270->321R, 271->281L,     280->330R,     281->291L,    290->330R,    291->301L,     300->330R,    301->311L,     310->330R, 311->110R,    320->340L,     321->321R,    330->350R,    331->331R,     340->360R,    341->340R,     350->371R, 351->350R,    360->360R,     361->381R,    370->370R,    371->391R,     380->360R,    381->401R,     390->370R, 391->411R,    400->360R,     401->421R,    410->370R,    411->431R,     420->360R,    421->441R,     430->370R, 431->451R,    440->360R,     441->461R,    450->370R,    451->471R,     460->480R,    461->461R,     470->490R, 471->471R,    480->480R,     481->490R,    490->481R,    491->501R,     500->481R,    501->511R,     510->481R, 511->521R,    520->481R,     521->531R,    530->541R,    531->531R,     540->160L,     541->o0R,      550->531R.

Теперь мы готовы точно определить предельную длину пред­писания К, получаемого путем вышеприведенного построения, как функцию от длины алгоритма А. Сравним эту «длину» со «степенью сложности», определенной в § 2.6 (в конце коммента­рия к возражению Q8). Для некоторой конкретной машины Тью­ринга Т_т (например, той, что выполняет вычисление А) эта ве­личина равна количеству знаков в двоичном представлении чис­ла т. Для некоторого конкретного машинного действия Т_т(п) (например, выполнения предписания К) эта величина равна ко­личеству двоичных цифр в большем из чисел тип. Обозначим через а и к количество двоичных цифр в а и ' k' соответственно, где

А = Т_а    и    K = T_k,(=C_k).

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

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

к < а + 527 + 210 Iog₂ (N + 55).

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

к < а - 15 + 210 Iog₂ (a + 336).

Затем найдем степень сложности г? конкретного вычисле­ния Ck (k), получаемого посредством этой процедуры. Вспомним, что степень сложности машины Т_т (п) определяется как коли­чество двоичных цифр в большем из двух чисел т, п. В данной ситуации Ck = Tk, так что число двоичных цифр в числе «т» этого вычисления равно к. Для того, чтобы определить, сколько двоичных цифр содержит число «п» этого вычисления, рассмот­рим ленту, содержащую вычисление Ck (k). Эта лента начинается с последовательности символов 111110, за которой следует двоичное выражение числа k', и завершается последовательно­стью 11011111. В соответствии с предложенным в НРК соглашением всю эту последовательность (без последней циф­ры) следует читать как двоичное число; эта операция дает нам номер «п», который присваивается ленте машины, выполняющей вычисление Т_т (п). То есть число двоичных цифр в данном кон­кретном номере «п» равно к + 13, и, следовательно, число к + 13 совпадает также со степенью сложности г/ вычисления Ck (k), .благодаря чему мы можем записать г)  =  к + 13  <  а — 2 4-+ 210 Iog₂ (а + 336), или проще:

?7<a + 2101og₂(a-l-336).

Детали вышеприведенного рассуждения специфичны для данного конкретного предложенного еще в НРК способа кодиро­вания машин Тьюринга, и при использовании какого-либо иного кодирования они также будут несколько иными. Основная же идея очень проста. Более того, прими мы формализм Х-исчисления, вся операция оказалась бы, в некотором смысле, почти тривиальной. (Достаточно обстоятельное описание Л-исчисления Черча можно найти в НРК., конец главы 2; см. также [52].) Пред­положим, например, что алгоритм А определяется некоторым А-оператором А, выполняющим действие над другими оператора­ми Р и Q, что выражается в виде операции (АР) Q. Оператором Р здесь представлено вычисление С_р, а оператором Q — число q. Далее, оператор А должен удовлетворять известному требова­нию, согласно которому для любых Р и Q должно быть истинным следующее утверждение:

Если завершается операция (АР) Q, то операция PQ не завершается.

Мы без труда можем составить такую операцию Л-исчисления, которая не завершается, однако этот факт невозможно устано­вить посредством оператора А. Например, положим

К = Ах.[(Ах)х], т.е. KY = (AY)Y для любого оператора Y. Затем рассмотрим

А-операцию

KK.

Очевидно, что эта операция не завершается, поскольку КК = = (АК) К, а завершение последней операции означало бы, что операция КК не завершается по причине принятой нами приро­ды оператора А. Более того, оператор А не способен установить этот факт, потому что операция (АК) К не завершается. Если мы полагаем, что оператор А обладает требуемым свойством, то мы также должны предположить, что операция КК не завершает­ся.

Отметим, что данная процедура дает значительную эконо­мию. Если записать операцию КК в виде

КК = Ау.(уу)(Ах.[(Ах)х]),

то становится ясно, что число символов в записи операции КК всего на 16 больше аналогичного числа символов для алгорит­ма А (если пренебречь точками, которые в любом случае избы­точны)!

Строго говоря, это не совсем законно, поскольку в выраже­нии для оператора А может также появиться и символ «х», и с этим нам придется что-то делать. Можно усмотреть сложность и в том, что генерируемое такой процедурой незавершающееся вычисление нельзя считать операцией над натуральными числами (поскольку вторая К в записи КК «числом» не является). Вообще говоря, А-исчисление не вполне подходит для работы с явными численными операциями, и зачастую бывает довольно сложно понять, каким образом ту или иную заданную алгоритмическую процедуру, применяемую к натуральным числам, можно выра­зить в виде операции А-исчисления. По этим и подобным при­чинам обсуждение с привлечением машин Тьюринга имеет, как нам представляется, более непосредственное отношение к теме нашего исследования и достигает требуемого результата более наглядным путем.

3 О невычислимости в математическом мышлении

3.1. Гёдель и Тьюринг

В главе 2 была предпринята попытка продемонстрировать мощь и строгий характер аргументации в пользу утверждения (обозначенного буквой ^), суть которого заключается в том, что математическое понимание не может являться результатом при­менения какого-либо осмысленно осознаваемого и полностью достоверного алгоритма (или, что то же самое, алгоритмов; см. возражение Q1). В приводимых рассуждениях, однако, ни словом не упомянуто еще об одной возможности, существенно более се­рьезной и ничуть не противоречащей утверждению <£, а имен­но: убежденность математика в истинности своих выводов может оказаться результатом применения им некоего неизвестного и неосознаваемого алгоритма, или же, возможно, математик при­меняет какой-то вполне постижимый алгоритм, однако при этом не может знать наверняка (или хотя бы искренне верить), что вы­воды его являются целиком и полностью результатом применения этого самого алгоритма. Ниже я покажу, что, хотя подобные до­пущения и вполне приемлемы с логической точки зрения, вряд ли их можно счесть хоть сколько-нибудь правдоподобными.

Прежде всего следует указать на то, что тщательно вы­страивая последовательности умозаключений (вполне, заметим, осознанных) с целью установления той или иной математиче­ской истины, математики вовсе не считают, что они лишь слепо следуют неким неосознаваемым правилам, будучи при этом не

'Здесь я предполагаю, что если процедура А вообще завершается, то это свидетельствует об успешном установлении факта незавершаемости С (n). Если же Л «застревает» по какой-либо иной, нежели достижение «успеха», причине, то это означает, что в данном случае процедура А корректно завершиться не может. См. далее по тексту возражения Q3 и Q4, а также Приложение А, с. 191.

Собственно, точно такой же результат достигается посредством процедуры, выполняемой универсальной машиной Тьюринга над парой чисел д, п; см. При­ложение А и НРК, с. 51-57.

Термин «алгоритмизм», который (по своей сути) прекрасно подходит для обозначения «точки зрения i/» в моей классификации, был предложен Хао Ва­ном [376].

Приведение к абсурду (лат.), доказательство от противного. — Прим. перев.

Чтобы подчеркнуть, что я принимаю это обстоятельство во внимание, я от­сылаю читателя к Приложению А, где представлена явная вычислительная про­цедура (выполненная в соответствии с правилами, подробно описанными в НРК, глава 2) для получения операции Ck (К) машины Тьюринга посредством алгорит­ма А. Здесь предполагается, что алгоритм А задан в виде машины Тьюринга Т_а, определение же вычисления С_я (п) кодируется как операция машины Т„ над числом q, а затем над числом п.