Формальные системы и алгоритмическое доказательство

 

В предложенной мною формулировке доказательства Гёделя—Тьюринга (см. §2.5) говорится только о «вычислениях» и ни словом не упоминается о «формальных системах». Тем не менее, между этими двумя концепциями существует очень тесная связь. Одним из существенных свойств формальной системы является непременная необходимость существования алгоритмической (т.е. «вычислительной») процедуры F, предназначенной для проверки правильности применения правил этой системы. Если, в соответствии с правилами системы F , некое высказывание является ИСТИННЫМ, то вычисление F этот факт установит. (Для достижения этого результата вычисление F, возможно, «просмотрит» все возможные последовательности строк символов, принадлежащих «алфавиту» системы F , и успешно завершится, обнаружив заключительной строкой искомое высказывание P; при этом любые сочетания строк символов являются, согласно правилам системы F , допустимыми.)

Напротив, располагая некоторой заданной вычислительной процедурой E, предназначенной для установления истинности определенных математических утверждений, мы можем построить формальную систему E , которая эффективно выражает как ИСТИННЫЕ все те истины, что можно получить с помощью процедуры E. Имеется, впрочем, и небольшая оговорка: как правило, формальная система должна содержать стандартные логические операции, однако заданная процедура E может оказаться недостаточно обширной, чтобы непосредственно включить и их. Если сама заданная процедура E не содержит этих элементарных логических операций, то при построении системы E уместно будет присоединить их к E с тем, чтобы ИСТИННЫМИ положениями системы E оказались не только утверждения, получаемые непосредственно из процедуры E, но и утверждения, являющиеся элементарными логическими следствиями утверждений, получаемых непосредственно из E. При таком построении система E не будет строго эквивалентна процедуре E, но вместо этого приобретет несколько большую мощность.

(Среди таких логических операций могут, к примеру, оказаться следующие: «если P & amp; Q, то P »; «если P и P ⇒ Q, то Q »; «если ∀ x [P (x )], то P (n )»; «если ~ ∀ x [P (x )], то ∃ x [~ P (x )]» и т.п. Символы «& amp; », «⇒ », «∀ », «∃ », «~» означают здесь, соответственно, «и», «следует», «для всех [натуральных чисел]», «существует [натуральное число]», «не»; в этот ряд можно включить и некоторые другие аналогичные символы.)

Поставив перед собой задачу построить на основе процедуры E формальную систему E , мы можем начать с некоторой в высшей степени фундаментальной (и, со всей очевидностью, непротиворечивой) формальной системы L , в рамках которой выражаются лишь вышеупомянутые простейшие правила логического вывода, — например, с так называемого исчисления предикатов (см. [223]), которое только на это и способно, — и построить систему E посредством присоединения к системе L процедуры E в виде дополнительных аксиом и правил процедуры для L , переведя тем самым всякое высказывание P, получаемое из процедуры E, в разряд ИСТИННЫХ. Это, впрочем, вовсе не обязательно окажется легко достижимым на практике. Если процедура E задается всего лишь в виде спецификации машины Тьюринга, то нам, возможно, придется присоединить к системе L (как часть ее алфавита и правил процедуры) все необходимые обозначения и операции машины Тьюринга, прежде чем мы сможем присоединить саму процедуру Е в качестве, по сути, дополнительной аксиомы. (См. окончание §2.8; подробности в [223].)

Собственно говоря, в нашем случае не имеет большого значения, содержит ли система E , которую мы таким образом строим, ИСТИННЫЕ предположения, отличные от тех, что можно получить непосредственно из процедуры E (да и примитивные логические правила системы L вовсе не обязательно должны являться частью заданной процедуры E ). В §2.5 мы рассматривали гипотетический алгоритм A, который по определению включал в себя все процедуры (известные или познаваемые), которыми располагают математики для установления факта незавершаемости вычислений. Любому подобному алгоритму неизбежно придется, помимо всего прочего, включать в себя и все основные операции простого логического вывода. Поэтому в дальнейшем я буду подразумевать, что все эти вещи в алгоритме A изначально присутствуют.

Следовательно, как процедуры для установления математических истин, алгоритмы (т. е. вычислительные процессы) и формальные системы для нужд моего доказательства, в сущности, эквивалентны. Таким образом, несмотря на то, что представленное в §2.5 доказательство было сформулировано исключительно для вычислений, оно сгодится и для общих формальных систем. В том доказательстве, если помните, речь шла о совокупности всех вычислениях (действий машины Тьюринга) Cq (n ). Следовательно, для того чтобы оно оказалось во всех отношениях применимо к формальной системе F , эта система должна быть достаточно обширной для того, чтобы включать в себя действия всех машин Тьюринга. Алгоритмическую процедуру A, предназначенную для установления факта незавершаемости некоторых вычислений, мы можем теперь добавить к правилам системы F с тем, чтобы вычисления, предположения о незавершающемся характере которых устанавливаются в рамках F как ИСТИННЫЕ, были бы тождественны всем тем вычислениям, незавершаемость которых определяется с помощью процедуры A.

Как же первоначальное кенигсбергское доказательство Гёделя связано с тем, что я представил в §2.5? Не будем углубляться в детали, укажем лишь на наиболее существенные моменты. В роли формальной системы F из исходной теоремы Гёделя выступает наша алгоритмическая процедура A:

 

алгоритм A ↔ правила системы F.

 

Роль же представленного Гёделем в Кенигсберге предположения G ( F ), которое в действительности утверждает непротиворечивость системы F , играет полученное в §2.5 конкретное предположение «вычисление Ck (k ) не завершается», недоказуемое посредством процедуры A, но интуитивно представляющееся истинным, коль скоро процедуру А мы полагаем обоснованной:

 

утверждение «вычисление Ck (k ) не завершается» ↔ утверждение «система F непротиворечива».

 

Возможно, такая замена позволит лучше понять, каким образом убежденность в обоснованности процедуры — такой, например, как A — может привести к другой процедуре, с исходной никак не связанной, но в обоснованности которой мы также должны быть убеждены, поскольку если мы полагаем процедуры некоторой формальной системы F обоснованными — т.е. процедурами, с помощью которых мы получаем одни лишь действительные математические истины, полностью исключив ложные утверждения (иными словами, если некое предположение P выводится из такой процедуры как ИСТИННОЕ, то это значит, что оно и в самом деле должно быть истинным ), — то мы должны также уверовать и в ω -непротиворечивость системы F. Если под «ИСТИННЫМ» понимать «истинное», а под «ЛОЖНЫМ» — «ложное» (как оно, собственно, и есть в рамках любой обоснованной формальной системы F ), то безусловно истинно следующее утверждение:

 

не все предположения P (0), P (1), P (2), P (3), P (4), … могут быть ИСТИННЫМИ, если утверждение «предположение P (n ) справедливо для всех натуральных чисел n » ЛОЖНО,

 

что в точности совпадает с условием ω -непротиворечивости.

Однако убежденность в ω -непротиворечивости формальной системы F может происходить не только из убежденности в обоснованности этой системы, но и из убежденности в ее обыкновенной непротиворечивости. Поскольку если под «ИСТИННЫМ» понимать «истинное», а под «ЛОЖНЫМ» — «ложное», то, несомненно, выполняется условие

 

«ни одно предположение P не может быть одновременно и ИСТИННЫМ, и ЛОЖНЫМ»,

 

в точности совпадающее с условием непротиворечивости. Вообще говоря, во многих случаях различия между непротиворечивостью и ω -непротиворечивостью практически отсутствуют. Для упрощения дальнейших рассуждений этой главы я, в общем случае, не стану разделять эти два типа непротиворечивости и буду обычно говорить просто о «непротиворечивости». Суть доказательства Гёделя и Россера сводится к тому, что установление факта непротиворечивости формальной системы (достаточно обширной) превышает возможности этой самой формальной системы. Первоначальный (кенигсбергский) вариант теоремы Гёделя опирался только на ω -непротиворечивость, однако следующий, более известный, вывод был связан уже исключительно с непротиворечивостью обыкновенной.

Сущность гёделевского доказательства в нашем случае состоит в том, что оно показывает, как выйти за рамки любого заданного набора вычислительных правил, полагаемых обоснованными, и получить некое дополнительное правило, в исходном наборе отсутствующее, но которое также должно полагать обоснованным, — т.е. правило, утверждающее непротиворечивость исходных правил. Важно уяснить следующий существенный момент:

 

убежденность в обоснованности равносильна убежденности в непротиворечивости.

 

Мы имеем право применять правила формальной системы F и полагать, что выводимые из нее результаты действительно истинны, только в том случае, если мы также полагаем, что эта формальная система непротиворечива. (Например, если бы система F не была непротиворечивой, то мы могли бы вывести, как ИСТИННОЕ, утверждение «1 = 2», которое истинным, разумеется, не является! ) Таким образом, если мы уверены, что применение правил некоторой формальной системы F действительно эквивалентно математическому рассуждению, то следует быть готовым принять и рассуждение, выходящее за рамки системы F , какой бы эта система F ни была.

 

2.10. Возможные формальные возражения против G (продолжение)

 

Продолжим рассмотрение различных математических возражений, высказываемых время от времени в отношении моей трактовки доказательства Гёделя—Тьюринга. Многие из них тесно связаны друг с другом, однако я полагаю, что в любом случае их будет полезно разъяснить по отдельности.

 

Q10. Абсолютна ли математическая истина? Как мы уже видели, существуют различные мнения относительно абсолютной истинности утверждений о бесконечных множествах. Можем ли мы доверять доказательствам, опирающимся на какую-то расплывчатую концепцию «математической истины», а не на, скажем, четко определенное понятие формальной ИСТИНЫ?

 

Что касается формальной системы F , описывающей общую теорию множеств, то, действительно, не всегда ясно, можно ли вообще говорить о каком-то абсолютном смысле, в котором то или иное утверждение о множествах является либо «истинным», либо «ложным», — вследствие чего под сомнение может попасть и само понятие «обоснованности» формальной системы, подобной F. В качестве поясняющего примера приведем один известный результат, полученный Гёделем (1940) и Коэном (1966). Они показали, что определенные математические утверждения (так называемые континуум-гипотеза Кантора и аксиома выбора ) никак не зависят от теоретико-множественных аксиом системы Цермело—Френкеля — стандартной формальной системы, обозначаемой здесь через ZF. (Аксиома выбора гласит, что для любой совокупности непустых множеств существует еще одно множество, которое содержит ровно один элемент из каждого множества совокупности29. Согласно же континуум-гипотезе Кантора, количество подмножеств натуральных чисел — равное количеству вещественных чисел — представляет собой вторую по величине бесконечность после множества собственно натуральных чисел30. Читателю нет нужды вникать в скрытый смысл этих утверждений прямо сейчас. Равно как нет нужды и мне углубляться в подробное изложение аксиом и правил процедуры системы ZF. ) Некоторые математики убеждены в том, что система ZF охватывает все методы математического рассуждения, необходимые для обычной математики. Некоторые даже утверждают, будто приемлемым математическим доказательством можно считать только такое доказательство, какое можно, в принципе, сформулировать и доказать в рамках системы ZF. (См. комментарий к возражению Q14 , где дается оценка применимости к таким субъектам гёделевского доказательства.) Иными словами, эти математики настаивают на том, что ИСТИННЫМИ, ЛОЖНЫМИ и НЕРАЗРЕШИМЫМИ в рамках системы ZF математическими утверждениями можно считать только те утверждения, истинность, ложность и неразрешимость которых, в принципе, устанавливается математическими средствами. Для таких людей аксиома выбора и континуум-гипотеза являются математически неразрешимыми (что, по их мнению, и доказывается выводом Гёделя—Коэна), и они наверняка будут утверждать, что истинность или ложность этих двух математических утверждений суть предметы достаточно условные.

Влияют ли эти кажущиеся неопределенности в отношении абсолютного характера математической истины на выводы, которые мы сделали из доказательства Гёделя—Тьюринга? Никоим образом, так как мы имеем здесь дело с классом математических проблем гораздо более ограниченной природы, нежели те, что, подобно аксиоме выбора и континуум-гипотезе, относятся к неконструктивно-бесконечным множествам. В данном случае нас занимают лишь утверждения вида

 

«такое-то вычисление никогда не завершается»,

 

причем рассматриваемые вычисления можно задать совершенно точно через действия машины Тьюринга. Такие утверждения в логике называются Π 1-высказываниями (или, точнее, Π 10- высказываниями). В пределах формальной системы F утверждение G ( F ) является Π 1-высказыванием, а вот Ω ( F ) таковым не является (см. §2.8). По всей видимости, не существует каких-либо разумных доводов против того, что истинный/ложный характер любого Π 1-высказывания есть предмет абсолютный и никак не зависит от избранного нами мнения относительно предположений, касающихся неконструктивно-бесконечных множеств — таких, например, как аксиома выбора и континуум-гипотеза. (С другой стороны, как мы вскоре убедимся, выбор метода рассуждения, принимаемого нами в качестве инструмента для получения убедительных доказательств Π 1-высказываний, действительно может определяться мнением, которого мы придерживаемся в отношении неконструктивно-бесконечных множеств; см. возражение Q11. ) Очевидно, если не считать крайней позиции, занимаемой отдельными интуиционистами (см. комментарий к Q9 ), единственное здравое возражение по поводу абсолютного характера истинности таких утверждений может быть связано с тем обстоятельством, что некоторые принципиально завершающиеся вычисления могут потребовать для своего выполнения столь непомерно долгого времени, что на практике, вполне возможно, не завершатся, скажем, и за все время жизни Вселенной; может случиться и так, что для записи самого вычисления (пусть и конечного) потребуется так много символов, что физически невозможным окажется составить даже его описание. Впрочем, все эти вопросы были исчерпывающим образом проанализированы выше, в обсуждении возражения Q8 ; там же мы выяснили, что на наш основной вывод G они никоим образом не влияют. Вспомним и о возражении Q9 , рассмотрение которого показало, что интуиционисты в этом случае также не избегают вывода G.

Кроме того, концепция (весьма ограниченная, надо сказать) математической истины, необходимая мне для доказательства Гёделя—Тьюринга, определена, вообще говоря, не менее четко, нежели концепции ИСТИННОГО, ЛОЖНОГО и НЕРАЗРЕШИМОГО для любой формальной системы F. Из сказанного выше (§2.9) нам известно, что существует некий алгоритм F, эквивалентный системе F. Если алгоритму F предстоит обработать некое предположение P (формулируемое на языке системы F ), то выполнение этого алгоритма может быть успешно завершено только в том случае, если предположение P доказуемо в соответствии с правилами системы F , т.е. когда предположение P ИСТИННО. Соответственно, предположение P является ЛОЖНЫМ, если алгоритм F успешно завершается при обработке предположения ~ P, и НЕРАЗРЕШИМЫМ, если не завершается ни одно из упомянутых вычислений. Вопрос о том, является ли математическое утверждение P ИСТИННЫМ, ЛОЖНЫМ или НЕРАЗРЕШИМЫМ, в точности совпадает по своей природе с вопросом о реальной истинности утверждений о завершаемости или незавершаемости вычислений — иными словами, о ложности или истинности определенных Π 1-высказываний — а кроме этого для нашего «гёделевско—тьюринговского» доказательства ничего и не требуется.

 

Q11. Существуют определенные Π 1-высказывания, которые можно доказать с помощью теории бесконечных множеств, однако не известно ни одного доказательства, которое использовало бы стандартные «конечные» методы. Не означает ли это, что даже к таким четко определенным проблемам математики, на деле, подходят субъективно? Различные математики, придерживающиеся в отношении теории множеств разных убеждений, могут применять к оценке математической истинности Π 1-высказываний неэквивалентные критерии.

 

Этот момент может оказаться существенным в том, что касается моих собственных выводов из доказательства Гёделя(—Тьюринга), и я, возможно, уделил ему недостаточно много внимания в кратком изложении, представленном в НРК. Как ни странно, но возражение Q11 , похоже, никого, кроме меня, не обеспокоило — по крайней мере, никто мне на него не указал! В НРК (с. 417, 418), как и здесь, я сформулировал доказательство Гёделя(—Тьюринга) исходя из того, что посредством разума и понимания способны установить все «математики» или «математическое сообщество». Преимущество подобной формулировки, в отличие от рассмотрения вопроса о способности какого-либо конкретного индивидуума к установлению математических истин посредством своего разума и понимания, заключается в том, что первый способ позволяет избежать некоторых возражений, которые нередко выдвигают в отношении той версии доказательства Гёделя, которую предложил Лукас (1961). Самые разные ученые31 указывали, к примеру, на то, что «сам Лукас» никак не мог обладать знанием о своем собственном алгоритме. (Некоторые из них говорили то же самое и о варианте доказательства, предложенном мною32, не обратив, судя по всему, внимания на тот факт, что моя формулировка вовсе не настолько «личностна».) Именно возможность сослаться на способности к рассуждению и пониманию, присущие всем «математикам» вообще или «математическому сообществу», позволяет нам избежать необходимости считаться с предположением о том, что различные индивидуумы могут воспринимать математическую истину по-разному, каждый в соответствии с личным непознаваемым алгоритмом. Значительно сложнее смириться с тем, что результатом выполнения некоего непостижимого алгоритма может оказаться коллективное понимание математического сообщества в целом, нежели с тем, что этот самый алгоритм обусловливает математическое понимание всего лишь какого-то конкретного индивидуума. Суть возражения Q11 как раз и заключается в том, что упомянутое коллективное понимание может оказаться совсем не таким универсальным и безличным, каким счел его я.

Утверждения, о каких говорится в Q11 , действительно, существуют. То есть существуют Π 1-высказывания, единственные известные доказательства которых опираются на то или иное применение теории бесконечных множеств. Такое Π 1-высказывание может быть результатом арифметического кодирования утверждения типа «аксиомы формальной системы F являются непротиворечивыми», где система F подразумевает манипуляции обширными бесконечными множествами, само существование которых может быть сомнительным. Математик, убежденный в реальном существовании некоторого достаточно обширного неконструктивного множества S, придет к выводу, что система F действительно непротиворечива, тогда как другой математик, который полагает, что множества S не существует, вовсе не обязан считать систему F непротиворечивой. Таким образом, даже ограничив рассмотрение одним вполне определенным вопросом о завершении или незавершении работы машины Тьюринга (т.е. ложности или истинности Π 1-высказываний), мы не можем себе позволить не учитывать субъективности убеждений в отношении, скажем, существования некоторого обширного неконструктивно-бесконечного множества S. Если различные математики используют для установления истинности определенных Π 1-высказываний неэквивалентные «персональные алгоритмы», то, по-видимому, с моей стороны несправедливо говорить о просто «математиках» или «математическом сообществе».

Полагаю, что в строгом смысле это действительно может быть несколько несправедливо; и читатель может при желании перефразировать вывод G следующим образом:

 

G * Для установления математической истины ни один отдельно взятый математик не применяет только те алгоритмы, какие он (или она) полагает обоснованными.

 

Представленные мною доводы по-прежнему остаются в силе, однако, мне кажется, некоторые из более поздних утратят значительную часть своей силы, если представить ситуацию в таком виде. Более того, в случае формулировки G * все доказательство уходит в направлении, на мой взгляд, бесперспективном, сосредоточенном, в большей степени, на конкретных механизмах, управляющих действиями конкретных индивидуумов, нежели на принципах, лежащих в основе действий любого из нас. Меня же на данном этапе интересует не столько различия подходов отдельных математиков к той или иной математической проблеме, сколько то общее, что есть между нашим пониманием и нашим математическим восприятием.

Попытаемся разобраться, действительно ли мы вынуждены принять формулировку G *. В самом ли деле суждения математиков настолько субъективны, что они могут принципиально расходиться при установлении истинности какого-то конкретного Π 1-высказывания? (Разумеется, доказательство, устанавливающее истинность Π 1-высказывания, может быть просто-напросто быть слишком громоздким или слишком сложным, чтобы его мог воспроизвести тот или иной математик (см. ниже по тексту возражение Q12 ), т.е. на практике математики вполне могут разойтись во мнениях. Однако в данном случае нас интересует вовсе не это. Мы занимаемся исключительно принципиальными вопросами.) Вообще говоря, математическое доказательство есть вещь не настолько субъективная, как может показаться на основании вышесказанного. Математики могут придерживаться самых разных — и, на их взгляд, неопровержимо истинных — точек зрения по тем или иным фундаментальным вопросам и во всеуслышание объявлять об этом, однако едва дело доходит до доказательств или опровержений каких-либо вполне определенных конкретных Π 1-высказываний, все разногласия тут же куда-то исчезают. Никто не воспримет всерьез доказательство Π 1-высказывания, утверждающего, по сути своей, непротиворечивость некоторой формальной системы F , если математик будет основывать его только лишь на существовании некоего спорного бесконечного множества S. То, что при этом в действительности доказывается, можно сформулировать следующим, куда более приемлемым, образом: «Если множество S существует, то формальная система F является непротиворечивой, и в этом случае данное Π 1-высказывание истинно».

Тем не менее, могут быть и исключения: например, один математик полагает, что некоторое неконструктивно-бесконечное множество S «с очевидностью» существует — или, по крайней мере, что допущение о его существовании никоим образом не приводит к противоречию, — другой же математик никакой очевидности здесь не усматривает. Дискуссии математиков по таким фундаментальным вопросам могут порой принимать поистине неразрешимый характер. При этом обе стороны могут оказаться, в принципе, неспособны сколько-нибудь убедительно изложить свои доказательства, даже в отношении Π 1-высказываний. Возможно, каждому математику и в самом деле присуще некое особое внутреннее восприятие истинности утверждений, связанных с неконструктивно-бесконечными множествами. Конечно же, математики нередко заявляют о том, что их восприятие таких вещей в корне отличается от восприятия коллег. Однако я полагаю, что такие различия, по сути своей, подобны различиям в ожиданиях, которые различные математики могут иметь и в отношении истинности обычных математических высказываний. Эти ожидания суть всего лишь предварительные предположения. До тех пор, пока не представлено убедительного доказательства или опровержения, математики могут спорить друг с другом об ожидаемой или предполагаемой истинности того или иного положения, однако представление такого доказательства одним из математиков убеждает (в принципе) всех. Что до фундаментальных вопросов, то там этих доказательств как раз нет. Возможно, и не будет. Быть может, их нельзя отыскать по той причине, что их просто-напросто нет, а фундаментальные вопросы допускают существование различных, но равно справедливых точек зрения.

Здесь, однако, следует подчеркнуть еще один связанный с Π 1-высказываниями момент. Возможность наличия у математика ошибочной точки зрения — т.е. такой точки зрения, которая вынуждает его делать неверные выводы в отношении истинности тех или иных Π 1-высказываний, — нас в данный момент не интересует. Нет ничего невероятного в том, что математики порой опираются на неверное в фактическом отношении «понимание» — а то и на необоснованные алгоритмы, — только к настоящему обсуждению это никакого отношения не имеет, поскольку согласуется с выводом G. Впрочем, эту ситуацию мы подробно рассмотрим ниже, в §3.4. Следовательно, дело в данном случае заключается не в том, могут ли разные математики придерживаться противоречащих одна другой точек зрения, а скорее в том, может ли одна точка зрения оказаться, в принципе, мощнее другой. Каждая такая точка зрения будет совершенно справедлива в том, что касается установления истинности Π 1-высказываний, однако какая-то из них сможет, в принципе, дать своим последователям возможность установить, что те или иные вычисления не завершаются, тогда как другие, более слабые, точки зрения на это неспособны; то есть одни математики будут обладать существенно большей способностью к пониманию, нежели другие.

Не думаю, что такая возможность представляет собой сколько-нибудь серьезную угрозу для моей первоначальной формулировки G. Хотя в отношении бесконечных множеств математики и вправе придерживаться различных точек зрения, этих самых точек зрения вовсе не так много: по всей видимости, не более пяти. Существенные в этом смысле расхождения могут быть обусловлены лишь утверждениями, подобными аксиоме выбора (о ней говорилось в комментарии к возражению Q10 ), которую одни полагают «очевидной», другие же напрочь отвергают связанную с ней неконструктивность. Любопытно, что эти различные точки зрения на собственно аксиому выбора не приводят непосредственно к тому Π 1-высказыванию, относительно справедливости которого возникают разногласия. Ибо, независимо от своей предполагаемой «истинности» или «ложности», аксиома выбора, как показывает теорема Гёделя—Коэна(см. комментарий к Q10 ), не вступает в противоречие со стандартными аксиомами системы ZF. Могут, однако, существовать и другие спорные аксиомы, соответствующей теоремы для которых нет. Впрочем, обыкновенно, когда речь заходит о принятии или опровержении той или иной теоретико-множественной аксиомы — назовем ее аксиомой Q, — утверждения математиков принимают следующий вид: «Из допущения справедливости аксиомы Q следует, что…». Такое утверждение при всем желании не сможет стать предметом спора между математиками. Аксиома выбора, похоже, является исключением в том смысле, что ее справедливость часто подразумевается без приведения упомянутой оговорки, однако это обстоятельство, по-видимому, никак не противоречит моей общей объективной формулировке вывода G — при условии, что мы ограничимся только Π 1-высказываниями:

 

G ** Для установления истинности Π 1-высказываний математики-люди не применяют заведомо обоснованные алгоритмы,

 

а этого нам в любом случае вполне достаточно.

Есть ли другие спорные аксиомы, которые одни математики считают «очевидными», а другие ставят под сомнение? Думаю, будет огромным преувеличением сказать, что имеется хотя бы десять существенно различных точек зрения на теоретико-множественные допущения, которые в явном виде как допущения не формулируются. Положим, что их не более десяти, и рассмотрим следствия из этого допущения. Это означает, что существует порядка десяти, по сути, различных классов математиков, различаемых по типу рассуждения в отношении бесконечных множеств, который они полагают «очевидно» истинным. Каждого такого математика можно назвать математиком n -го класса, где n изменяется в весьма узком диапазоне — не более десяти значений. (Чем больше номер класса, тем мощнее будет точка зрения принадлежащих к нему математиков.) Вывод G ** принимает в этом случае следующий вид:

 

G *** Для установления истинности Π 1-высказываний математики-люди n-го класса (где п может принимать лишь несколько значений) не применяют только те алгоритмы, какие они полагают обоснованными.

 

Так получается, потому что доказательство Гёделя(—Тьюринга) можно применять к каждому классу отдельно. (Важно понять, что само гёделевское доказательство предметом спора между математиками не является, а потому если для любого математика n -го класса гипотетический алгоритм n-го класса будет познаваемо обоснованным, то доказательство приведет к противоречию.) Таким образом, как и в случае с G, дело вовсе не в существовании какого-то невообразимого количества непознаваемо обоснованных алгоритмов, каждый из которых присущ лишь одному конкретному индивидууму. Мы всего лишь исключаем возможность существования некоторого очень небольшого количества неэквивалентных непознаваемо обоснованных алгоритмов, рассортированных в соответствии с их мощностью и образующих в результате различные «школы мышления». В последующем обсуждении различия между вариантами G *** и G либо G ** не будут иметь особого значения, поэтому для упрощения изложения я не стану в дальнейшем их как-то различать и буду использовать для них всех одно общее обозначение G.

 

Q12. Вне зависимости оттого, насколько различных точек зрения придерживаются математики в принципе, на практике те же математики обладают весьма разными способностями к воспроизведению доказательств, разве не так? Не менее различны и их способности к пониманию, позволяющие им совершать математические открытия.

 

Безусловно, так оно и есть, однако к рассматриваемому вопросу все эти вещи не имеют ну абсолютно никакого отношения. Меня не интересует, какие именно и насколько сложные доказательства математик способен воспроизвести на практике. Еще меньше меня занимает вопрос о том, какие доказательства математик может на практике открыть или какие понимание и вдохновение могут ему в этом способствовать. Здесь мы говорим исключительно о том, доказательства какого типа математики могут, в принципе, воспринимать как обоснованные.

Оговорка «в принципе» используется в наших рассуждениях отнюдь не просто так. Если допустить, что некий математик располагает доказательством или опровержением некоторого Π 1-высказывания, то его разногласия с другими математиками касательно обоснованности данного доказательства разрешимы только в том случае, если у этих самых других математиков хватит времени, терпения, объективности, способностей и решимости с вниманием и пониманием воспроизвести всю — возможно, длинную и хитроумную — цепочку его рассуждений. На практике же математики вполне могут отказаться от всех этих трудов еще до полного разрешения спорных вопросов. Однако подобные проблемы к данному исследованию отношения не имеют. Так как, по всей видимости, существует все же некий вполне определенный смысл, в котором то, что в принципе постижимо для одного математика, оказывается равным образом (если отвлечься на время от возражения Q11 ) постижимо и для другого, — вообще, для любого человека, способного мыслить. Рассуждения бывают весьма громоздкими, а участвующие в них концепции могут показаться чересчур тонкими или туманными, и тем не менее существуют достаточно убедительные основания полагать, что способность к пониманию одного человека не включает в себя ничего такого, что в принципе недоступно другому человеку. Это применимо и к тем случаям, когда для воспроизведения во всех подробностях чисто вычислительной части доказательства может потребоваться помощь компьютера. Возможно, не совсем разумно ожидать, что математик-человек будет лично выполнять все необходимые для такого доказательства вычисления, и все же он, вне всякого сомнения, сможет без особого труда понять и проверить каждый отдельный его этап.

Здесь я говорю исключительно о сложности математического доказательства и ни в коем случае не о возможных существенных и принципиальных вопросах, которые могут вызвать среди математиков разногласия в отношении выбора допустимых методов рассуждения. Разумеется, я встречал математиков, утверждавших, что они в своей практике сталкивались с такими математическими доказательствами, которые были совершенно вне их компетенции: «Я уверен, что, сколько бы я ни старался, мне никогда не понять того-то или такого-то; этот метод рассуждения мне не по зубам». В каждом конкретном случае подобного заявления необходимо индивидуально решать, действительно ли данный метод рассуждения в принципе выходит за рамки системы убеждений этого математика — каковой случай мы рассматривали в комментарии к возражению Q11 , — или он вообще-то смог бы разобраться в принципах, на которых основано это доказательство, если бы только приложил больше сил и затратил больше времени. Как правило, справедливым оказывается последнее. Более того, источником отчаяния нашего математика чаще всего становится туманный стиль изложения или ограниченные лекторские способности «такого-то», а вовсе не то, что какие-то существенные и принципиальные моменты «того-то» действительно выходят за рамки его способностей. Толковое изложение, на первый взгляд, непонятного предмета чудесным образом устраняет все прежние недоразумения.

Чтобы еще раз подчеркнуть, что я имею в виду, скажу следующее: сам я часто посещаю математические семинары, на которых не слежу (а иногда и не пытаюсь следить) за подробностями представляемых доказательств. Наверное, если бы я сел где-нибудь и обстоятельно изучил эти самые доказательства, я и в самом деле смог бы проследить за мыслью автора — хотя, возможно, это удалось бы мне лишь при наличии дополнительной литературы или устных пояснений, которые восполнили бы возможные пробелы в моем образовании или же в материалах самого семинара. Я знаю, что в действительности я этого делать не стану. У меня почти наверняка не окажется на это ни времени, ни достаточного количества внимания, ни, впрочем, особого желания. Но при этом я вполне могу принять представленный на семинаре результат на веру по всевозможным «несущественным» причинам — например, потому что полученный результат правдоподобно «выглядит», или потому что у лектора надежная репутация, или потому что другие слушатели, которых я считаю более сведущими в таких делах, нежели я сам, этот результат оспаривать не стали. Конечно, я могу ошибиться во всех своих умозаключениях, а результат вполне может оказаться ложным — либо истинным, но никоим образом не следующим из представленного доказательства. Все эти тонкости никак не влияют на ту принципиальную позицию, которую я здесь представляю. Результат может оказаться истинным и адекватно доказанным, и в таком случае я, в принципе, могу проследить за ходом всего доказательства — или же ошибочным, в каковом случае, как уже упоминалось, он нас в данном контексте не интересует (см. §3.2 и §3.4). Возможные исключения могут составить лишь те случаи, когда представляемый материал касается каких-либо спорных аспектов теории бесконечных множеств или опирается на какой-то необычный метод рассуждения, который может быть признан сомнительным в соответствии с теми или иными математическими воззрениями (что, само по себе, может заинтриговать меня до такой степени, что я впоследствии действительно попытаюсь это доказательство повторить). Как раз такие исключительные ситуации мы обсуждали выше, в комментарии к возражению Q11.

Что касается подобных соображений относительно природы математической точки зрения, на практике многие математики могут и не иметь четкого представления о том, каких именно фундаментальных принципов они в действительности придерживаются. Однако, как уже было сказано выше, в комментарии к Q11 , если математик, у которого нет определенной позиции в отношении того, следует ли принимать, скажем, некую «аксиому Q », желает проявить осмотрительность, то ничто не мешает ему изложить требующие принятия аксиомы Q результаты в следующем виде: «Из принятия аксиомы Q следует, что…». Разумеется, математики, несмотря на всю их пресловутую педантичность, проявляют в подобных вопросах должную осмотрительность далеко не всегда. Нельзя отрицать и того, что время от времени им удается допускать и вовсе очевидные ошибки. И все же все эти ошибки — если они допущены по недосмотру, а не следуют из тех или иных непоколебимых принципов — являются исправимыми. (Как упоминалось ранее, возможность действительного применения математиками в качестве основы для своих решений необоснованного алгоритма будет подробно рассмотрена в §3.2 и §3.4. Поскольку эта возможность не противоречит выводу G, она не является предметом настоящего обсуждения.) В данном случае нас не занимают исправимые ошибки, так как к вопросу о принципиальной достижимости тех или иных результатов они никакого отношения не имеют. А. вот возможные неопределенности в действительных взглядах математиков, безусловно, требуют дальнейшего обсуждения, которое и приводится ниже.

 

Q13. У математиков нет абсолютно определенных убеждений относительно обоснованности или непротиворечивости используемых ими формальных систем — как нет и однозначного ответа на вопрос о том, «пользователями» каких именно формальных систем они себя полагают. Не подвергаются ли их убеждения постепенному размыванию по мере того, как формальные системы все более удаляются от области феноменов, доступных непосредственному интуитивному или экспериментальному восприятию?

 

И правда, нечасто встретишь математика, способного похвалиться прочно устоявшимися и непоколебимо непротиворечивыми убеждениями, когда речь заходит об основах предмета. Кроме того, по мере накопления опыта математик вполне может изменить свои взгляды относительно того, что считать неопровержимо истинным, если он вообще склонен считать неопровержимо истинным что бы то ни было. Можно ли, например, быть совершенно и полностью уверенным в том, что число 1 отлично от числа 2? Если говорить о некоей абсолютной человеческой уверенности, то не совсем ясно, можно ли подобное понятие как-то однозначно определить. Однако какую-то точку опоры все же выбрать необходимо. Вполне приемлемой точкой опоры может стать принятие в качестве неопровержимо истинной некоторой системы убеждений и принципов, от которой уже можно двигаться в своих рассуждениях дальше. Разумеется, нельзя забывать и о том, что многие математики вовсе не имеют определенного мнения относительно того, что именно можно считать неопровержимо истинным. Таких математиков я попросил бы какую-никакую опору для себя все же выбрать и просто быть готовыми при необходимости впоследствии ее сменить. Как показывает доказательство Гёделя, какую бы позицию математик в этом случае ни занял, ее все равно невозможно полностью уместить в рамки правил любой постижимой формальной системы (а если и возможно, то этот факт невозможно однозначно установить). И дело даже не в том, что та или иная конкретная позиция постоянно изменяется; система убеждений, полностью охватываемая рамками любой (достаточно обширной) формальной системы F , неизбежно должна также простирается и за пределы доступной F области. Любая позиция, среди неопровержимых убеждений которой имеется и убеждение в обоснованности системы F , должна также включать в себя и убежденность в истинности гёделевского предположения[15]G ( F ). Убежденность в истинности G ( F ) не представляет собой изменения позиции; эта убежденность уже подразумевается неявно в исходной позиции, допускающей принятие истинности формальной системы F , пусть даже поначалу это и не очевидно.

Безусловно, всегда существует возможность того, что в выводы, получаемые математиком на основании исходных посылок какой-либо конкретной точки зрения, закрадется ошибка. Одна только возможность возникновения такой ошибки — даже если в действительности никакой ошибки допущено не было — может привести к уменьшению степени убежденности, которую математик питает в отношении своих выводов. Однако такое «постепенное размывание» нас, вообще говоря, не занимает. Подобно действительным ошибкам, оно «исправимо». Более того, если доказательство было проведено действительно корректно, то чем дольше его изучаешь, тем, как правило, более убедительными представляются полученные в нем выводы. «Постепенное размывание» математик может испытать на практике, но не в принципе, что возвращает нас к обсуждению возражения Q12.

Таким образом, вопрос перед нами встает здесь следующий: имеет ли место постепенное размывание в принципе, т.е. может ли математик счесть, скажем, обоснованность некоторой формальной системы F неопровержимой, тогда как в обоснованности более сильной системы F * он будет лишь «практически уверен». Этот вопрос не представляется мне сколько-нибудь серьезным, коль скоро, какой бы ни была система F , мы вправе настаивать, чтобы она включала в себя обычные логические правила и арифметические операции. Упомянутый выше математик, который верит в обоснованность системы F , должен также верить в ее непротиворечивость, а следовательно, и в истинность гёделевского высказывания G ( F ). Таким образом, одни только выводы из формальной системы F не могут охватывать всей совокупности математических убеждений математика, какой бы эта система ни была.

Однако следует ли считать высказывание G ( F ) неопровержимо истинным всякий раз, когда мы признаем неопровержимо обоснованной формальную систему F ? Полагаю, утвердительный ответ на этот вопрос не должен вызывать никаких сомнений; и это тем более так, если придерживаться в отношении воспроизведения математического доказательства той «принципиальной» позиции, которой мы придерживались до сих пор. Единственная возникающая в этой связи реальная проблема касается деталей фактического кодирования утверждения «система F непротиворечива» в форме арифметического утверждения (Π 1-высказывания). Сама по себе базовая идея неопровержимо очевидна: если система F является обоснованной, то она, безусловно, непротиворечива. (Так как если бы она не была непротиворечивой, то среди ее утверждений присутствовало бы утверждение «1 = 2», т.е. система была бы необоснованной.) Что касается деталей этого самого кодирования, то здесь нам вновь предстоит иметь дело с различием между «принципиальным» и «практическим» уровнями. Не составит особого труда убедиться в том, что такое кодирование в принципе возможно (хотя сам процесс убеждения может занять некоторое время), однако убедиться в корректном выполнении того или иного конкретного действительного кодирования — дело совсем другое. Детали кодирования, как правило, бывают в известной степени произвольными и в разных изложениях могут весьма значительно отличаться. Возможно, где-то закрадется незначительная ошибка или просто опечатка, которая, в формальном смысле, должна бы сделать недействительным данное конкретное предназначенное для выражения «G ( F )» теоретико-числовое предположение, однако в действительности этого не происходит.

Надеюсь, читатель понимает, что возможность возникновения таких ошибок не существенна, когда речь заходит о том, что мы подразумеваем здесь под принятием предположения G ( F ) в качестве неопровержимой истины. Я, разумеется, говорю о действительном предположении G ( F ), а не о возможном случайном предположении, непреднамеренно сформулированном благодаря опечатке или незначительной ошибке. В этой связи мне вспоминается одна история о великом американском физике Ричарде Фейнмане. Фейнман, по-видимому, объяснял одному из студентов какое-то понятие, но оговорился. Когда студент выразил недоумение, Фейнман вспылил: «Не слушайте, что я говорю; слушайте, что я имею в виду! »[16].

Один из возможных способов такого явного кодирования состоит в использовании представленных еще в НРК спецификаций машин Тьюринга и точном воспроизведении доказательства гёделевского типа, описанного в §2.5 (пример такого кодирования приводится в Приложении А). Впрочем, даже и в этом случае об абсолютной «явности» говорить нельзя, поскольку нам понадобится еще и каким-то явным образом закодировать правила формальной системы F в системе обозначений действий машин Тьюринга; обозначим такой код, скажем, через T F - (Код T F должен удовлетворять определенному свойству: если некоторому высказыванию P, выводимому в рамках системы F , ставится в соответствие некоторое число р, то необходимо, скажем, чтобы равенство T F (p) = 1 выполнялось всякий раз, когда высказывание P является теоремой системы F , в противном же случае вычисление T F (p) не должно завершаться вовсе.) Безусловно, все это открывает широкий простор для формальных ошибок. Помимо возможных трудностей, связанных с практическим построением кода T F на основе системы F и отысканием числа p на основе высказывания P, отсутствует ясность и в отношении другого вопроса: а не ошибся ли я сам где-нибудь в спецификациях машин Тьюринга, — иными словами, можем ли мы быть полностью уверены в корректности приведенного в Приложении А этой книги кода, если вдруг решим использовать для отыскания вычисления Ck (k ) именно это определение? Лично я думаю, что ошибок там нет, однако в собственной непогрешимости я уверен куда как меньше, нежели в первоначальных построениях Гёделя (пусть и более сложных). Впрочем, всякому дочитавшему до этого места, смею надеяться, уже ясно, что возможные ошибки подобного рода существенной роли здесь не играют. Помните, что говорил Фейнман?

Что же касается собственно моих спецификаций, следует упомянуть еще один формальный момент. Представленный мною в §2.5 вариант доказательства Гёделя(—Тьюринга) опирается не на непротиворечивость системы F , а на обоснованность алгоритма A, и являет собой критерий для установления незавершаемости вычислений (т.е. истинности Π 1-высказываний). Этот вариант подходит нам ничуть не хуже любых других, поскольку известно, что из обоснованности алгоритма A следует истинность утверждения о незавершаемости вычисления Ck (k ), каковое явное утверждение (тоже Π 1-высказывание) мы имеем полное право использовать вместо высказывания G ( F ). Более того, как отмечалось выше (см. §2.8), доказательство, вообще говоря, зависит не от непротиворечивости формальной системы F , а от ее ω -непротиворечивости. Из обоснованности системы F очевидно следует ее непротиворечивость, равно как и ω -непротиворечивость. Если допустить, что система F обоснованна, то ни Ω ( F ), ни G ( F ) из ее правил (см. §2.8) не следуют, однако оба эти высказывания являются истинными.

Думаю, можно с уверенностью заключить, что какое бы «постепенное размывание» убежденности того или иного математика ни сопровождало переход от убеждения в обоснованности формальной системы F к убеждению в истинности высказывания G ( F ) (или Ω ( F )), оно будет целиком и полностью обусловлено возможностью ошибки в точной формулировке полученного им высказывания «G ( F )». (To же применимо и к высказыванию Ω ( F ).) Все это не имеет непосредственного отношения к настоящему обсуждению — при наличии подлинной (не случайной) формулировки высказывания G ( F ) никакого размывания убежденности происходить не должно. Если формальная система F неопровержимо обоснованна, то ее высказывание G ( F ) столь же неопровержимо истинно. Все формы заключения G (G **, G ***) остаются неизменными при условии, что под «истинностью» подразумевается «неопровержимая истинность».

 

Q14. Нет никаких сомнений в том, что формальная система ZF — или некоторая стандартная ее модификация (обозначим ее через ZF *) —действительно включает в себя все необходимое для серьезной математической деятельности. Почему бы просто не принять эту систему за основу, смириться с недоказуемостью ее непротиворечивости и продолжить свои математические изыскания?

 

Полагаю, такая точка зрения весьма и весьма распространена среди практикующих математиков, особенно тех, кто не слишком углубляется в фундаментальные основы или философию своего предмета. Подобное отношение вполне естественно для людей, главной заботой которых является просто хорошее выполнение серьезной, пусть и математической, работы (хотя в действительности такие люди крайне редко выражают свои результаты в рамках строгих правил формальных систем, подобных ZF ). Согласно этой точке зрения, математика имеет дело лишь с тем, что можно доказать или опровергнуть в рамках некоей конкретной формальной системы — такой, например, как ZF (или какая-либо ее модификация ZF *). С высоты такой позиции математическая деятельность и в самом деле напоминает своего рода «игру». Назовем ее ZF -игрой (или ZF *-игрой), причем играть в эту игру следует в соответствии с правилами, установленными в рамках данной системы. Такой подход характерен для формалиста, подлинный же формалист мыслит исключительно в терминах ИСТИННОГО и ЛОЖНОГО, которые не обязательно совпадают с истинным и ложным в их повседневном смысле. Если формальная система обоснованна, то все, что является истинным, и будет истинным, а все, что ЛОЖНО, будет ложным. Однако наверняка найдутся высказывания, формализуемые в рамках данной системы, которые, будучи истинными, не являются ИСТИННЫМИ, и другие, которые, будучи ложными, не являются ЛОЖНЫМИ, иными словами, в обоих случаях эти высказывания оказываются НЕРАЗРЕШИМЫМИ. Если система ZF непротиворечива, то в ZF -игре гёделевское высказывание[17]G ( ZF ) и его отрицание ~ G ( ZF ) принадлежат, соответственно, к этим двум категориям. (Более того, окажись система ZF противоречивой, то и высказывание G ( ZF ), и его отрицание ~ G ( ZF ) были бы ИСТИННЫМИ и ЛОЖНЫМИ одновременно! )

ZF -игра, судя по всему, представляет собой исключительно разумный подход, позволяющий реализовать большую часть того, что нас интересует в обычной математике. Однако по причинам, которые обозначены выше, я совершенно не в состоянии понять, каким же образом из нее может «произрасти» реальная точка зрения в отношении чьих бы то ни было математических убеждений. Ибо если кто-то считает, что с помощью «практикуемой» им математики он устанавливает исключительно подлинные математические истины — скажем, истинность Π 1-высказываний, — то он должен верить и в то, что используемая им система обоснованна; а если он верит в ее обоснованность, то он должен также верить в ее непротиворечивость, то есть в то, что Π 1-высказывание, утверждающее истинность G ( F ), действительно истинно, несмотря на то, что оно НЕРАЗРЕШИМО. Таким образом, математические убеждения человека должны включать в себя нечто, что в рамках ZF -игры невыводимо. С другой стороны, если человек не верит в обоснованность формальной системы ZF , то он не может верить и в подлинную истинность ИСТИННЫХ результатов, полученных с помощью ZF -игры. В обоих случаях сама по себе ZF -игра не в состоянии снабдить нас удовлетворительной позицией в том, что касается математической истинности. (Это равным образом применимо к любой формальной системе ZF *.)

 

Q15. Выбранная нами формальная система F может и не оказаться непротиворечивой — по крайней мере, мы не можем быть вполне уверены в ее непротиворечивости; по какому же, в таком случае, праву мы утверждаем, что высказывание G ( F ) «очевидно» истинно?

 

Хотя этот вопрос был достаточно исчерпывающе рассмотрен в предыдущих обсуждениях, я полагаю, что суть того рассмотрения полезно будет изложить еще раз, поскольку возражения, подобные Q15 , чаще всего оказываются среди нападок на наше с Лукасом приложение теоремы Гёделя. Суть же в том, что мы вовсе не утверждаем, что высказывание G ( F ) непременно истинно для любой формальной системы F , мы утверждаем лишь, что высказывание G ( F ) настолько же достоверно, насколько достоверна любая другая истина, получаемая применением правил самой системы F. (Вообще говоря, высказывание G ( F ) оказывается более достоверным, нежели утверждения, получаемые действительным применением правил F , так как система F , даже будучи непротиворечивой, не обязательно будет обоснованной! ) Если мы верим в истинность любого утверждения P, выводимого исключительно с помощью правил системы F , то мы должны верить и в истинность G ( F ), по крайней мере, в той же степени, в какой мы верим в истинность P. Таким образом, ни одна постижимая формальная система F — или эквивалентный ей алгоритм F — не может послужить абсолютно полной основой для подлинного математического познания или формирования убеждений. Как отмечалось в комментариях к Q5 и Q6 , наше доказательство построено как reductio ad absurdum: мы выдвигаем предположение, что система F действительно является абсолютной основой для формирования убеждений, а затем показываем, что такое предположение приводит к противоречию, т.е. является неверным.

Мы, конечно же, можем, как в Q14 , выбрать для удобства какую-то конкретную систему F , хотя уверенности в том, что она обоснованна, а потому непротиворечива, это нам не добавит. Впрочем, при наличии действительных сомнений в обоснованности системы F  любой получаемый в рамках F результат P следует формулировать в виде

 

«высказывание P выводимо в рамках системы F »

 

(или, что то же самое, «высказывание P ИСТИННО»), избегая утверждений вида «высказывание P истинно». Такое утверждение в математическом смысле вполне приемлемо и может быть либо действительно истинным, либо действительно ложным. Совершенно законным образом мы можем свести все наши математические высказывания к утверждениям такого рода, однако и в этом случае нам никуда не деться от утверждений об абсолютных математических истинах. При случае мы можем прийти к убеждению, будто мы установили, что какое-то утверждение вышеприведенного вида является в действительности ложным, т.е. получить следующий результат:

 

«высказывание P невыводимо в рамках системы F ».

 

Такие утверждения имеют вид: «такое-то вычисление не завершается» (или, по сути, «будучи примененным к высказыванию P, алгоритм F не завершается»), что в точности совпадает с формой рассматриваемых нами Π 1-высказываний. Вопрос: какие средства мы полагаем допустимыми в процессе получения подобных утверждений? Каковы, наконец, те математические процедуры, в которые мы действительно верим и применяем при установлении математических истин? Такая система убеждений, при условии, что они достаточно разумны, никак не может быть эквивалентна всего лишь убежденности в обоснованности и непротиворечивости формальной системы, какой бы эта формальная система ни была.

 

Q16. Заключение об истинности высказывания G ( F ) для непротиворечивой формальной системы F мы делаем, исходя из допущения, что те символы системы F , которые, как мы полагаем, служат для представления натуральных чисел, действительно представляют натуральные числа. Окажись на их месте другие числа — скажем, некие экзотические «сверхнатуральные» числа, — мы вполне могли бы обнаружить, что высказывание G ( F ) ложно. Откуда мы знаем, что в нашей системе F мы имеем дело с натуральными, а не со «сверхнатуральными» числами?

 

В самом деле, конечного аксиоматического способа убедиться в том, что «числа», о которых идет речь, и есть те самые подразумеваемые натуральные числа, а не какие-то посторонние «сверхнатуральные», не существует33. Однако, в некотором смысле, в этом и состоит вся суть гёделевского рассуждения. Неважно, какую именно схему аксиом формальной системы F мы построим, пытаясь охарактеризовать натуральные числа, — одних лишь правил системы F будет недостаточно, чтобы определить, является ли высказывание G ( F ) действительно истинным или же ложным. Полагая систему F непротиворечивой, мы знаем, что в высказывании G ( F ) подразумевается все же наличие некоего истинного смысла. Это, однако, происходит лишь в том случае, если символы, составляющие в действительности формальное выражение, обозначаемое «G ( F )», имеют подразумеваемые значения. Если эти символы интерпретировать как-либо иначе, то полученная в результате интерпретация «G ( F )» вполне может оказаться ложной.

Для того чтобы разобраться, откуда берутся все эти двусмысленности, рассмотрим новые формальные системы F * и F **, где F * получается путем присоединения к аксиомам системы F высказывания G ( F ), a F ** — путем аналогичного присоединения высказывания ~ G ( F ). Если система F обоснованна, то обе системы F * и F ** непротиворечивы (т.к. высказывание G ( F ) истинно, а ~ G ( F ) из правил системы F ) вывести невозможно. При этом в случае подразумеваемой (или стандартной ) интерпретации символов F из обоснованности системы F следует, что система F * обоснованна, а система F ** — нет. Впрочем, одним из характерных свойств непротиворечивых формальных систем является возможность отыскания так называемых нестандартных реинтерпретаций символов таким образом, что высказывания, которые являются ложными в стандартной интерпретации, оказываются истинными в нестандартной; соответственно, в такой нестандартной интерпретации обоснованными могут быть системы F и F **, а система F * обоснованной не будет. Можно вообразить, что такая реинтерпретация может повлиять на смысл логических символов (таких как «~» и «& amp; », которые в стандартной интерпретации означают, соответственно, «не» и «и»), однако в данном случае нас занимают символы, обозначающие неопределенные числа («x », «y », «z », «x' », «x" » и т.д.), и значения применяемых к ним логических кванторов (∀, ∃ ). В стандартной интерпретации символы «∀ x » и «∃ x » означают, соответственно, «для всех натуральных чисел x » и «существует такое натуральное число x, что»; в не стандартной же интерпретации эти символы могут относится не к натуральным числам, а к числам какого-то иного вида с иными свойствами упорядочения (такие числа действительно можно назвать «сверхнатуральными», или даже «ультранатуральными», как это сделал Хофштадтер [201]).

Дело, однако, в том, что мы-то знаем, что такое на самом деле представляют собой натуральные числа, и для нас не составит никакого труда отличить их от каких-то непонятных сверхнатуральных чисел. Натуральные числа суть самые обыденные вещи, обозначаемые, как правило, символами 0, 1, 2, 3, 4, 5, 6, …. С этой концепцией мы знакомимся еще в детском возрасте и легко отличим ее от надуманной концепции сверхнатурального числа (см. §1.21). Есть что-то таинственное в том, что мы, похоже, и впрямь обладаем каким-то инстинктивным пониманием действительного смысла понятия натурального числа. Все, что мы получаем в этом смысле в детском (или уже взрослом) возрасте, сводится к сравнительно небольшому количеству описаний понятий «нуля», «единицы», «двух», «трех» и т.д. («три апельсина», «один банан» и т.п.), однако при этом, несмотря на всю неадекватность такого описания, мы как-то умудряемся постичь всю концепцию в целом. В некотором платоническом смысле натуральные числа видятся своего рода категориями, обладающими абсолютным концептуальным существованием, от нас никак не зависящим. И все же, несмотря на «человеконезависимость» натуральных чисел, мы оказываемся способны установить интеллектуальную связь с действительной концепцией натуральных чисел, опираясь лишь на неоднозначные и, на первый взгляд, неадекватные описания. С другой стороны, не существует конечного набора аксиом, с помощью которого можно было бы провести четкую границу между множеством натуральных чисел и альтернативным ему множеством так называемых «сверхнатуральных» чисел.

Более того, такое специфическое свойство всей совокупности натуральных чисел, как их бесконечное количество, мы также можем каким-то образом воспринимать непосредственно, тогда как система, действие которой ограничено точными конечными правилами, не способна отличить данную конкретную бесконечность натуральных чисел от других возможных («сверхнатуральных») вариантов. Мы же легко понимаем бесконечность, характеризующую натуральные числа, пусть и обозначаем ее просто точками «…» —

 

«0, 1, 2, 3, 4, 5, 6, …»,

 

либо сокращением «и т.д.» —

 

«нуль, один, два, три и т.д.».

 

Нам не нужно объяснять на языке каких-то точных правил, что именно представляет собой натуральное число. В этом смысле можно считать, что нам повезло, так как такое объяснение дать невозможно. Как только нам приблизительно укажут верное направление, мы тут же обнаруживаем, что уже откуда-то знаем, что это за штука такая — натуральное число!

Возможно, некоторые читатели знакомы с аксиомами Пеано для арифметики натуральных чисел (об арифметике Пеано я уже упоминал в §2.7), и, возможно, теперь эти читатели находятся в некотором недоумении: почему же аксиомы Пеано не дают адекватного определения натуральных чисел. Согласно определению Пеано, мы начинаем ряд натуральных чисел с символа 0 и затем добавляем слева особый «оператор следования», обозначаемый S и осуществляющий простое прибавление единицы к числу, над которым совершается действие, т.е. 1 определяется как S0 , 2 как S1 или SS0 и т.д. В качестве правил мы располагаем следующими утверждениями: если Sa = Sb , то a = b ; и ни при каком x число 0 нельзя записать в виде Sx (последнее утверждение служит для характеристики числа 0 ). Кроме того, имеется «принцип индукции», согласно которому некое свойство чисел (скажем, P ) должно быть истинным в отношении всех чисел n , если оно удовлетворяет двум условиям: (I) если истинно P ( n ), то для всех n истинно также и P ( Sn ); (II) P ( 0 ) истинно. Сложности начинаются, когда дело доходит до логических операций, символы которых ∀ и ∃ в стандартной интерпретации означают, соответственно, «для всех натуральных чисел …» и «существует такое натуральное число …, что». В нестандартной интерпретации смысл этих символов соответствующим образом изменяется, так что они квантифицируют уже не натуральные числа, а «числа» какого-то другого типа. Хотя математические спецификации Пеано, задающие оператор следования S , действительно описывают отношение упорядочения, отличающее натуральные числа от разных прочих «сверхнатуральных» чисел, эти определения невозможно записать в терминах формальных правил, которым удовлетворяют кванторы ∀ и ∃. Для того чтобы передать смысл математических определений Пеано, необходимо перейти к так называемой «логике второго порядка», в которой также вводятся кванторы типа ∀ и ∃, но только теперь они оперируют не над отдельными натуральными числами, а над множествами (бесконечными) натуральных чисел. В «логике первого порядка» арифметики Пеано кванторы оперируют над отдельными числами, и в результате получается формальная система в обычном смысле этого слова. Логика же второго порядка нам формальной системы не дает. В случае строгой формальной системы вопрос о правильности применения правил системы решается чисто механическими (т.е. алгоритмическими) способами — в сущности, именно это свойство формальных систем и послужило причиной их рассмотрения в настоящем контексте. В рамках логики второго порядка упомянутое свойство не работает.

Многие ошибочно полагают (в духе приведенных в возражении Q16 соображений), что из теоремы Гёделя следует существование множества различных арифметик, каждая из которых в равной степени обоснованна. Соответственно, та частная арифметика, которую мы, возможно, по чистой случайности избрали для своих нужд, определяется просто какой-то произвольно взятой формальной системой. В действительности же теорема Гёделя показывает, что ни одна из этих формальных систем (будучи непротиворечивой) не может быть полной; поэтому (как доказывается далее) к ней можно непрерывно добавлять какие угодно новые аксиомы и получать всевозможные альтернативные непротиворечивые системы, которыми при желании можно заменить ту, в рамках которой мы работаем в настоящий момент. Эту ситуацию нередко сравнивают с той, что сложилась некогда с евклидовой геометрией. На протяжении двадцати одного века люди верили, что евклидова геометрия является единственно возможной геометрией. Но когда в восемнадцатом веке сразу несколько великих математиков (таких как Гаусс, Лобачевский и Бойяи) показали, что существуют в равной степени возможные альтернативы общепринятой геометрии, геометрии пришлось отступить с абсолютных позиций на произвольные. Нередко можно услышать, будто Гёдель показал, что арифметика так же представляет собой предмет произвольного выбора, при этом один набор непротиворечивых аксиом оказывается ничуть не хуже любого другого.

Однако подобная интерпретация того, что доказал Гёдель, абсолютно неверна. Согласно Гёделю, само по себе понятие формальной системы аксиом не подходит для передачи даже самых элементарных математических понятий. Когда мы употребляем термин «арифметика» без дальнейших пояснений, мы подразумеваем обычную арифметику, которая работает с обычными натуральными числами 0, 1, 2, 3, 4, … (и, быть может, с их отрицаниями), а вовсе не со «сверхнатуральными» числами, что бы это понятие ни означало. Мы можем, если пожелаем, исследовать свойства формальных систем, и это, конечно же, станет ценным вкладом в процесс математического познания. Однако такое предприятие несколько отличается от исследования обычных свойств обычных натуральных чисел. В некотором отношении данная ситуация весьма напоминает ту, что сложилась в последнее время с геометрией. Изучение неевклидовых геометрий интересно с математической точки зрения, да и сами геометрии имеют ряд важных областей применения (например, в физике, см. НРК, глава 5, особенно рис. 5.1 и 5.2, а также §4.4), но, когда термин «геометрия» используется в обычном языке (в отличие от «жаргона» математиков или физиков-теоретиков), подразумевается, как правило, обычная евклидова геометрия. Однако имеется и разница: то, что логик может назвать «евклидовой геометрией», действительно можно определить (с некоторыми оговорками34) через определенную формальную систему, тогда как обычную «арифметику», как показал Гёдель, определить таким образом нельзя.

Гёдель доказал не то, что математика (в особенности арифметика) — это произвольные поиски, направление которых определяется прихотью Человека; он доказал, что математика — это нечто абсолютное, и в ней мы должны не изобретать, но открывать (см. §1.17). Мы открываем, что такое натуральные числа и без труда отличаем их от любых сверхнатуральных чисел. Гёдель показал, что ни одна система «искусственных» правил не способна сделать это за нас. Такая платоническая точка зрения была существенна для Гёделя, не менее существенной она будет и для нас в последующих рассуждениях (§8.7).

 

Q17. Допустим, что формальная система F предназначена для представления тех математических истин, что в принципе доступны человеческому разуму. Не можем ли мы обойти проблему невозможности формального включения в систему F гёделевского высказывания G ( F ), включив вместо него что-либо, имеющее смысл G ( F ), воспользовавшись при этом новой интерпретацией смысла символов системы F ?

 

Определенные способы представления примененного к F гёделевского доказательства в рамках формальной системы F (достаточно обширной) действительно существуют, коль скоро новый, реинтерпретированный, смысл символов системы F полагается отличным от исходного смысла символов этой системы. Однако если мы пытаемся таким образом интерпретировать систему F как процедуру, с помощью которой разум приходит к тем или иным математическим выводам, то подобный подход является не чем иным, как шулерством. Если мы намерены толковать мыслительную деятельность исключительно в рамках системы F , то ее символы не должны изменять свой смысл «на полпути». Если же мы принимаем, что мыслительная деятельность может содержать что-то помимо операций самой системы F — т.е. изменение смысла символов, — то нам необходимо знать и правила, управляющие подробным изменением. Либо эти правила окажутся неалгоритмическими, и это сыграет в пользу G, либо для них найдется какая-то конкретная алгоритмическая процедура, и тогда нам следовало бы изначально включить эту процедуру в нашу «систему F » — обозначим ее через F † — с тем, чтобы она представляла собой полную совокупность процедур, обусловливающих наши с вами понимание и проницательность, а значит, необходимости в изменении смысла символов не возникло бы вовсе. В последнем случае вместо гёделевского высказывания G ( F ) из предыдущего рассуждения нам предстоит разбираться уже с высказыванием G ( F †), так что ничего мы в результате не выигрываем.

 

Q18. Даже в такой простой системе, как арифметика Пеано, можно сформулировать теорему, интерпретация которой имеет следующий смысл:

«система F обоснованна», а следовательно, «высказывание G ( F ) истинно».

Разве это не все, что нам нужно от теоремы Гёделя? Значит, теперь, полагая обоснованной какую угодно формальную систему F , мы вполне можем поверить и в истинность ее гёделевского высказывания — при условии, разумеется, что мы готовы принять арифметику Пеано, разве не так?

 

Подобную теорему35 действительно можно сформулировать в рамках арифметики Пеано. Точнее (поскольку мы не можем в пределах какой бы то ни было формальной системы должным образом выразить понятие «обоснованности» или «истинности», как это следует из знаменитой теоремы Тарского), мы, в сущности, формулируем более сильный результат:

 

«система F непротиворечива», а следовательно, «высказывание G ( F ) истинно»,

 

либо иначе:

 

«система F ω -непротиворечива», а следовательно, «высказывание Ω ( F ) истинно».

 

Из этих высказываний следует вывод, необходимый для Q18 , поскольку если система F обоснованна, то она, разумеется, непротиворечива или омега-непротиворечива, в зависимости от обстоятельств. Понимая смысл присутствующего здесь символизма, мы и в самом деле можем поверить в истинность высказывания G ( F ) на основании одной лишь веры в обоснованность системы F. Это, впрочем, мы уже приняли. Если понимать смысл, то действительно возможно перейти от F к G ( F ). Сложности возникнут лишь в том случае, если нам вздумается исключить необходимость интерпретаций и сделать переход от F к G ( F ) автоматическим. Будь это возможно, мы смогли бы автоматизировать общую процедуру «гёделизации» и создать алгоритмическое устройство, которое действительно будет содержать в себе все, что нам нужно от теоремы Гёделя. Однако такой возможности у нас нет — захоти мы добавить эту предполагаемую алгоритмическую процедуру в какую угодно формальную систему F , выбранную нами в качестве отправной, в результате просто-напросто получилась бы, по сути, некоторая новая формальная система F #, а ее гёделевское высказывание G ( F #) оказалось бы уже за ее рамками. Таким образом, согласно теореме Гёделя, какой-то аспект понимания всегда остается «за нами», независимо от того, какая доля его оказалась включена в формализованную или алгоритмическую процедуру. Это «гёделево понимание» требует постоянного соотнесения с действительным смыслом символов какой бы то ни было формальной системы, к которой применяется процедура Гёделя. В этом смысле ошибка Q18 весьма похожа на ту, что мы обнаружили, комментируя возражение Q17. С невозможностью автоматизации процедуры гёделизации тесно связаны также рассуждения по поводу Q6 и Q19.

В возражении Q18 присутствует еще один аспект, который стоит рассмотреть. Представим себе, что у нас есть обоснованная формальная система H , содержащая арифметику Пеано. Теорема, о которой говорилось в Q18 , окажется среди следствий системы H , а частным ее примером, применимым к конкретной системе F (т.е., собственно, H ), будет теорема системы H. Таким образом, можно сформулировать один из выводов формальной системы H :

 

«система H обоснованна», а следовательно, «высказывание G ( H ) истинно»;

 

или, точнее, скажем так:

 

«система H непротиворечива», а следовательно, «высказывание G ( H ) истинно».

 

Если говорить о реальном смысле этих утверждений, то из них, в сущности, следует, что высказывание G ( H ) также утверждается системой. А так как (что касается первого из двух вышеприведенных утверждений) истинность любого производимого системой H утверждения, во всяком случае, обусловлена допущением, что система H обоснованна, то получается, что если система H утверждает нечто, явно обусловленное ее собственной обоснованностью, то она вполне может утверждать это напрямую. (Из утверждения «если мне можно верить, то X истинно» следует более простое утверждение, исходящее из того же источника: «X истинно».) Однако в действительности обоснованная формальная система H не может утверждать истинность высказывания G ( H ), что является следствием ее неспособности утверждать собственную обоснованность. Более того, как мы видим, она не может включать в себя и смысл символов, которыми оперирует. Те же факты годятся и для иллюстрации второго утверждения, причем в этом случае ко всему прочему добавляется и некоторая ирония: система H не способна утверждать собственную непротиворечивость лишь в том случае, если она действительно непротиворечива, если же формальная система непротиворечивой не является, то подобные ограничения ей неведомы. Противоречивая формальная система H может утверждать (в качестве «теоремы») вообще все, что она в состоянии сформулировать! Она вполне может, как выясняется, сформулировать и утверждение: «система М. непротиворечива». Формальная система (достаточно обширная) утверждает собственную непротиворечивость тогда и только тогда, когда она противоречива!

 

Q19. Почему бы нам просто не учредить процедуру многократного добавления высказывания G ( F ) к любой системе F , какой мы в данным момент пользуемся, и не позволить этой процедуре выполняться бесконечно?

 

Когда нам дана какая-либо конкретная формальная система F , достаточно обширная и полагаемая обоснованной, мы в состоянии понять, как добавить к ней высказывание G ( F ) в качестве новой аксиомы и получить тем самым новую систему F 1, которая также будет считаться обоснованной. (Для согласования обозначений в последующем изложении систему F можно также обозначить через F 0.) Теперь мы можем добавить к системе F 1 высказывание G ( F 1), получив в результате новую систему F 2, также, предположительно, обоснованную. Повторив данную процедуру, т.е. добавив к системе F 2 высказывание G ( F 2), получим систему F 3 и т.д. Приложив еще совсем немного усилий, мы непременно сообразим, как построить еще одну формальную систему F ω , аксиомы которой позволят нам включить в систему в качестве дополнительных аксиом для F все бесконечное множество высказываний G ( F 0), G ( F 1), G ( F 2), G ( F 3), …. Очевидно, что система F ω также будет обоснованной. Этот процесс можно продолжить и дальше: к системе F ω добавляется высказывание G ( F ω ), в результате чего получается система F ω +1, к которой затем добавляется высказывание G ( F ω +1), что дает систему F ω +2, и т.д. Далее, как и в предыдущий раз, мы можем построить формальную систему F ω 2 (= F ω +ω ), включив в нее весь бесконечный набор соответствующих аксиом, каковая система опять-таки окажется очевидно обоснованной. Добавлением к ней высказывания G ( F ω 2), получим систему F ω 2+1 и т.д., а потом построим новую систему F ω 3 (= F ω 2+ω ), включив в нее опять-таки бесконечное множество аксиом. Повторив всю вышеописанную процедуру, мы сможем получить формальную систему F ω 4, после следующего повтора — систему F ω 5 и т.д. Еще чуть-чуть потрудиться, и мы обязательно увидим, как можно включить уже это множество новых аксиом G ( F ω ), G ( F ω 2), G ( F ω 3), G ( F ω 4), … в новую формальную систему F ω 2(= F ω ω ). Повторив всю процедуру, мы получим новую систему F ω 2+ω 2, затем — систему F ω 2+ω 2+ω 2 и т.д.; в конце концов, когда мы сообразим, как связать все это вместе (разумеется, и на этот раз не без некоторого напряжения умственных способностей), наши старания приведут нас к еще более всеобъемлющей системе F ω 3, которая также должна быть обоснованной.

Читатели, которые знакомы с понятием канторовых трансфинитных ординалов, несомненно, узнают индексы, обычно используемые для обозначения таких чисел. Тем же, кто от подобных вещей далек, не стоит беспокоиться из-за незнания точного значения этих символов. Достаточно сказать, что описанную процедуру «гёделизации» можно продолжить и далее: мы получим формальные системы F ω 4, F ω 5, …, после чего придем к еще более обширной системе F ω ω , затем процесс продолжается до еще больших ординалов, например, ω ω ω и т.д. — до тех пор, пока мы все еще способны на каждом последующем этапе понять, каким образом систематизировать все множество гёделизаций, которые мы получили на данный момент. В этом и заключается основная проблема: для упомянутых нами «усилий, трудов и напряжений» требуется соответствующее понимание того, как должно систематизировать предыдущие гёделизаций. Эта систематизация выполнима при условии, что достигаемый к каждому последующему моменту этап будет помечаться так называемым рекурсивным ординалом, что, в сущности, означает, что должен существовать определенный алгоритм, способный такую процедуру генерировать. Однако алгоритмической процедуры, которую можно было бы заложить заранее и которая позволила бы выполнить описанную систематизацию для всех рекурсивных ординалов раз и навсегда, просто-напросто не существует. Нам снова неизбежно потребуется понимание.

Вышеприведенная процедура была впервые предложена Аланом Тьюрингом в его докторской диссертации (а опубликована в [368])36; там же Тьюринг показал, что любое истинное Π 1-высказывание можно, в некотором смысле, доказать с помощью многократной гёделизаций, подобной описанной нами. (См. также [117].) Впрочем, воспользоваться этим для получения механической процедуры установления истинности Π 1-высказываний нам не удастся по той простой причине, что механически систематизировать гёделизацию невозможно. Более того, невозможность «автоматизации» процедуры гёделизаций как раз и выводится из результата Тьюринга. А в §2.5 мы уже показали, что общее установление истинности (либо ложности) Π 1-высказываний невозможно произвести с помощью каких бы то ни было алгоритмических процедур. Так что в поисках систематической процедуры, не доступной тем вычислительным соображениям, которые мы рассматривали до настоящего момента, многократная гёделизация нам ничем помочь не сможет. Таким образом, для вывода G возражение Q19 угрозы не представляет.

 

Q20. Реальная ценность математического понимания состоит, безусловно, не в том, что благодаря ему мы способны выполнять невычислимые действия, а в том, что оно позволяет нам заменить невероятно сложные вычисления сравнительно простым пониманием. Иными словами, разве не правда, что, используя разум, мы, скорее, «срезаем углы» в смысле теории сложности, а вовсе не «выскакиваем» за пределы вычислимого?

 

Я вполне готов поверить в то, что на практике интуиция математика гораздо чаще используется для «обхода» вычислительной сложности, чем невычислимости. Как-никак математики по природе своей склонны к лени, а потому зачастую стараются изыскать всяческие способы избежать вычислений (пусть даже им придется в итоге выполнить значительно более сложную мыслительную работу, нежели потребовало бы собственно вычисление). Часто случается так, что попытки заставить компьютеры бездумно штамповать теоремы даже умеренно сложных формальных систем быстро загоняют эти самые компьютеры в ловушку фактически безнадежной вычислительной сложности, тогда как математик-человек, вооруженный пониманием смысла, лежащего в основе правил такой системы, без особого труда получит в рамках этой системы множество интересных результатов37.

Причина того, что в своих доказательствах я рассматривал не сложность, а невычислимость, заключается в том, что только с помощью последней мне удалось сформулировать необходимые для доказательства сильные утверждения. Не исключено, что в работе большинства математиков вопросы невычислимости играют весьма незначительную роль, если вообще играют. Однако суть не в этом. Я глубоко убежден, что понимание (в частности, математическое) представляет собой нечто, недоступное вычислению, а одной из немногих возможностей вообще подступиться ко всем этим вопросам является как раз доказательство Гёделя(—Тьюринга). Никто не отрицает, что наши математические интуиция и понимание нередко используются для получения результатов, достижимых, в принципе, и вычислительным путем, — но и здесь слепое, не отягощенное пониманием, вычисление может оказаться неэффективным настолько, что попросту не будет работать (см. §3.26). Однако рассмотрение всех таких случаев представляется мне неизмеримо более сложным подходом, нежели обращение к общей невычислимости.

Как бы то ни было, высказанные в возражении Q20 соображения, пусть и справедливые, все же ни в коей мере не противоречат выводу G.

 

 

Приложение A: Гёделизирующая машина Тьюринга в явном виде

 

Допустим, что у нас имеется некая алгоритмическая процедура A, которая, как нам известно, корректно устанавливает незавершаемость тех или иных вычислений. Мы получим вполне явную процедуру для построения на основе процедуры A конкретного вычисления C, для которого A оказывается неадекватной; при этом мы сможем убедиться, что вычисление C действительно не завершается. Приняв это явное выражение для C, мы сможем определить степень его сложности и сравнить ее со сложностью процедуры A, чего требуют аргументы §2.6 (возражение Q8 ) и §3.20.

Для определенности я воспользуюсь спецификациями той конкретной машины Тьюринга, которую я описал в НРК. Подробное описание этих спецификаций читатель сможет найти в названной работе. Здесь же я дам лишь краткое описание, которого вполне должно хватить для наших настоящих целей.

Машина Тьюринга имеет конечное число внутренних состояний, но производит все операции на бесконечной ленте. Эта лента представляет собой линейную последовательность «ячеек», причем каждая ячейка может быть маркированной или пустой, а общее количество отметок на ленте — величина конечная. Обозначим каждую маркированную ячейку символом 1 , а каждую пустую ячейку — 0. В машине Тьюринга имеется также считывающее устройство, которое поочередно рассматривает отметки и, в явной зависимости от внутреннего состояния машины Тьюринга и характера рассматриваемой в данный момент отметки, определяет дальнейшие действия машины по следующим трем пунктам: (I) следует ли изменить рассматриваемую в данный момент отметку; (II) каким будет новое внутреннее состояние машины; (III) должно ли устройство сдвинуться по ленте на один шаг вправо (обозначим это действие через R ) или влево (обозначим через L ), или же на один шаг вправо с остановкой машины ( STOP ). Когда машина, в конце концов, остановится, на ленте слева от считывающего устройства будет представлен в виде последовательности символов 0 и 1 ответ на выполненное ею вычисление. Изначально лента должна быть абсолютно чистой, за исключением отметок, описывающих исходные данные (в виде конечной строки символов 1 и 0 ), над которыми машина и будет выполнять свои операции. Считывающее устройство в начале работы располагается слева от всех отметок.

При представлении на ленте натуральных чисел (будь то входные или выходные данные) иногда удобнее использовать так называемую расширенную двоичную запись, согласно которой число, в сущности, записывается в обычной двоичной системе счисления, только двоичный знак «1» представляется символами 10 , а двоичный знак «0» — символом 0. Таким образом, мы получаем следующую схему перевода десятичных чисел в расширенные двоичные:

 

0 ↔ 0

1 ↔ 10

2 ↔ 100

3 ↔ 1010

4 ↔ 1000

5 ↔ 10010

6 ↔ 10100

7 ↔ 101010

8 ↔ 10000

9 ↔ 100010

10 ↔ 100100

11 ↔ 1001010

12 ↔ 101000

13 ↔ 1010010

14 ↔ 1010100

15 ↔ 10101010

16 ↔ 100000

17 ↔ 1000010

и т.д.

 

Заметим, что в расширенной двоичной записи символы 1 никогда не встречаются рядом. Таким образом, последовательность из двух или более 1 вполне может послужить сигналом о начале и конце записи натурального числа. То есть для записи всевозможных команд на ленте мы можем использовать последовательности типа 110 , 1110 , 11110 и т.д.

Отметки на ленте также можно использовать для спецификации конкретных машин Тьюринга. Это необходимо, когда мы рассматриваем работу универсальной машины Тьюринга U. Универсальная машина U работает с лентой, начальная часть которой содержит подробную спецификацию некоторой конкретной машины Тьюринга T, которую универсальной машине предстоит смоделировать. Данные, с которыми должна работать сама машина T, подаются в U вслед за тем участком ленты, который определяет машину T. Для спецификации машины T можно использовать последовательности 110 , 1110 и 11110 , которые будут обозначать, соответственно, различные команды для считывающего устройства машины T, например: переместиться по ленте на один шаг вправо, на один шаг влево, либо остановиться, сдвинувшись на один шаг вправо:

 

R ↔ 110

L ↔ 1110

STOP ↔ 11110.

 

Каждой такой команде предшествует либо символ 0 , либо последовательность 10 , что означает, что считывающее устройство должно пометить ленту, соответственно, либо символом 0 , либо 1 , заменив тот символ, который оно только что считало. Непосредственно перед вышеупомянутыми 0 или 10 располагается расширенное двоичное выражение числа, описывающего следующее внутреннее состояние, в которое должна перейти машина Тьюринга согласно этой самой команде. (Отметим, что внутренние состояния, поскольку количество их конечно, можно обозначать последовательными натуральными числами 0, 1, 2, 3, 4, 5, 6, …, N. При кодировании на ленте для обозначения этих чисел будет использоваться расширенная двоичная запись.)

Конкретная команда, к которой относится данная операция, определяется внутренним состоянием машины перед началом считывания ленты и собственно символами 0 или 1 , которые наше устройство при следующем шаге считает и, возможно, изменит. Например, частью описания машины T может оказаться команда 23 0 → 17 1R , что означает следующее: «Если машина T находится во внутреннем состоянии 23, а считывающее устройство встречает на ленте символ 0 , то его следует заменить символом 1 , перейти во внутреннее состояние 17 и переместиться по ленте на один шаг вправо». В этом случае часть «17 1R » данной команды будет кодироваться последовательностью 100001010110. Разбив ее на участки 1000010.10.110 , мы видим, что первый из них представляет собой расширенную двоичную запись числа 17, второй кодирует отметку 1 на ленте, а третий — команду «переместиться на шаг вправо». А как нам описать предыдущее внутреннее состояние (в данном случае 23) и считываемую в соответствующий момент отметку на ленте (в данном случае 0 )? При желании можно задать их так же явно с помощью расширенной двоичной записи. Однако на самом деле в этом нет необходимости, поскольку для этого будет достаточно упорядочить различные команды в виде цифровой последовательности (например, такой: 0 0 →, 0 1 →, 1 0 →, 1 1 →, 2 0 →, 2 1 →, 3 0 →, …).

К этому, в сущности, и сводится все кодирование машин Тьюринга, предложенное в НРК, однако для завершенности картины необходимо добавить еще несколько пунктов. Прежде всего, следует проследить за тем, чтобы каждому внутреннему состоянию, действующему на отметки 0 и 1 (не забывая, впрочем, о том, что команда для внутреннего состояния с наибольшим номером, действующая на 1 , оказывается необходимой не всегда), была сопоставлена какая-либо команда. Если та или иная команда вообще не используется в программе, то необходимо заменить ее «пустышкой». Предположим, например, что в ходе выполнения программы внутреннему состоянию 23 нигде не придется сталкиваться с отметкой 1 — соответствующая команда-пустышка в этом случае может иметь следующий вид: 23 1 → 0 0R.

Согласно вышеприведенным предписаниям, в кодированной спецификации машины Тьюринга на ленте пара символов 0 0 должна быть представлена последовательностью 00 , однако можно поступить более экономно и записать просто 0 , что явится ничуть не менее однозначным разделителем двух последовательностей, составленных из более чем одного символа 1 подряд[18]. Машина Тьюринга начинает работу, находясь во внутреннем состоянии 0 ; считывающее устройство движется по ленте, сохраняя это внутреннее состояние до тех пор, пока не встретит первый символ 1. Это обусловлено допущением, что в набор команд машины Тьюринга всегда входит операция 0 0 → 0 0R. Таким образом, в действительной спецификации машины Тьюринга в виде последовательности 0 и 1 явного задания этой команды не требуется; вместо этого мы начнем с команды 0 1 → X , где X обозначает первую нетривиальную операцию запущенной машины, т.е. первый символ 1 , встретившийся ей на ленте. Это значит, что начальную последовательность 110 (команду → 0 0R ), которая в противном случае непременно присутствовала бы в определяющей машину Тьюринга последовательности, можно спокойно удалить. Более того, в такой спецификации мы будем всегда удалять и завершающую последовательность 110 , так как она одинакова для всех машин Тьюринга.

Получаемая в результате последовательность символов 0 и 1 представляет собой самую обыкновенную (т.е. нерасширенную) двоичную запись номера машины Тьюринга n для данной машины (см. главу 2 НРК). Мы называем ее n -й машиной Тьюринга и обозначаем T = Tn. Каждый такой двоичный номер (с добавлением в конце последовательности 110 ) есть последовательность символов 0 и 1 , в которой нигде не встречается более четырех 1 подряд. Номер n, не удовлетворяющий данному условию, определяет «фиктивную машину Тьюринга», которая прекратит работать, как только встретит «команду», содержащую более четырех 1. Такую машину «Tn » мы будем называть некорректно определенной. Ее работа с какой угодно лентой является по определению незавершающейся. Аналогично, если действующая машина Тьюринга встретит команду перехода в состояние, определенное числом, большим всех тех чисел, для которых были явно заданы возможные последующие действия, то она также «зависнет»: такую машину мы будем полагать «фиктивной», а ее работу — незавершающейся. (Всех этих неудобств можно без особого труда избежать с помощью тех или иных технических средств, однако реальной необходимости в этом нет; см. §2.6, Q4 ).

Для того чтобы понять, как на основе заданного алгоритма A построить явное незавершающееся вычисление, факт незавершаемости которого посредством алгоритма A установить невозможно, необходимо предположить, что алгоритм A задан в виде машины Тьюринга. Эта машина работает с лентой, на которой кодируются два натуральных числа p и q. Мы полагаем, что если завершается вычисление A (p, q ), то вычисление, производимое машиной Tp с числом q, не завершается вовсе. Вспомним, что если машина Tp определена некорректно, то ее работа с числом q не завершается, каким бы это самое q ни было. В случае такого «запрещенного» p исход вычисления A (p, q ) может, согласно исходным допущениям, быть каким угодно. Соответственно, нас будут интересовать исключительно те числа p, для которых машина Tp определена корректно. Таким образом, в записанном на ленте двоичном выражении числа 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 как 1101110

14 как 11011110

15 как 11100

16 как 111010

…

25 как 1000

26 как 10010

и т.д.

 

Под «Cp » здесь будет пониматься вычисление, выполняемое корректно определенной машиной Тьюринга Tr, где r есть число, обыкновенное двоичное выражение которого (с добавлением в конце последовательности символов 110 ) в точности совпадает с числом p в нашей пятеричной записи. Число q, над которым производится вычисление Cp, также необходимо представлять в пятеричном выражении. Вычисление же A (p, q ) задается в виде машины Тьюринга, выполняющей действие с лентой, на которой кодируется пара чисел p, q. Запись на ленте будет выглядеть следующим образом:

 

… 00111110p111110q11111000 …,

 

где p и q суть вышеописанные пятеричные выражения чисел, соответственно, p и q.

Требуется отыскать такие числа p и q, для которых не завершается не только вычисление Cp (q ), но и вычисление A (p, q ). Процедура из §2.5 позволяет сделать это посредством отыскания такого числа k, при котором вычисление Ck, производимое с числом n, в точности совпадает с вычислением A (n, n ) при любом n, и подстановки p = q = k. Для того чтобы проделать это же в явном виде, отыщем машинное предписание K (= Ck ), действие которого на последовательность символов на ленте

 

… 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]. (Нуль можно использовать только в командах-пустышках.)

Затем при определении алгоритма 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. )

 

∅ 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.

 

Теперь мы готовы точно определить предельную длину предписания K, получаемого путем вышеприведенного построения, как функцию от длины алгоритма A. Сравним эту «длину» со «степенью сложности», определенной в §2.6 (в конце комментария к возражению Q8 ). Для некоторой конкретной машины Тьюринга Tm (например, той, что выполняет вычисление A ) эта величина равна количеству знаков в двоичном представлении числа m. Для некоторого конкретного машинного действия Tm (n ) (например, выполнения предписания K ) эта величина равна количеству двоичных цифр в большем из чисел тип. Обозначим через α и κ количество двоичных цифр в a и k' соответственно, где

 

A = Ta и K = Tk' (= Ck ).

 

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

 

α ≥ 6N - 6.

 

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

 

κ & lt; α + 527 + 210 log2(N + 55).

 

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

 

κ & lt; α - 15 + 210 log2(α + 336).

 

Затем найдем степень сложности η конкретного вычисления Ck (k ), получаемого посредством этой процедуры. Вспомним, что степень сложности машины Tm (n ) определяется как количество двоичных цифр в большем из двух чисел m, n. В данной ситуации Ck = Tk, так что число двоичных цифр в числе «m » этого вычисления равно κ . Для того чтобы определить, сколько двоичных цифр содержит число «n » этого вычисления, рассмотрим ленту, содержащую вычисление Ck (k ). Эта лента начинается с последовательности символов 111110 , за которой следует двоичное выражение числа k', и завершается последовательностью 11011111. В соответствии с предложенным в НРК соглашением всю эту последовательность (без последней цифры) следует читать как двоичное число; эта операция дает нам номер «n », который присваивается ленте машины, выполняющей вычисление Tm (n ). То есть число двоичных цифр в данном конкретном номере «n » равно κ + 13, и, следовательно, число κ + 13 совпадает также со степенью сложности ту вычисления Ck (k ), благодаря чему мы можем записать η = κ + 13 & lt; α — 2 + 210 log2(α + 336), или проще:

 

η & lt; α + 210 log2(α + 336).

 

Детали вышеприведенного рассуждения специфичны для данного конкретного предложенного еще в НРК способа кодирования машин Тьюринга, и при использовании какого-либо иного кодирования они также будут несколько иными. Основная же идея очень проста. Более того, прими мы формализм λ -исчисления, вся операция оказалась бы, в некотором смысле, почти тривиальной. (Достаточно обстоятельное описание λ -исчисления Черча можно найти в НРК, конец главы 2; см. также [52].) Предположим, например, что алгоритм A определяется некоторым λ -оператором A , выполняющим действие над другими операторами P и Q , что выражается в виде операции ( AP ) Q. Оператором P здесь представлено вычисление Cp, а оператором 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 «числом» не является). Вообще говоря, λ -исчисление не вполне подходит для работы с явными численными операциями, и зачастую бывает довольно сложно понять, каким образом ту или иную заданную алгоритмическую процедуру, применяемую к натуральным числам, можно выразить в виде операции λ -исчисления. По этим и подобным причинам обсуждение с привлечением машин Тьюринга имеет, как нам представляется, более непосредственное отношение к теме нашего исследования и достигает требуемого результата более наглядным путем.

 

⇐ Предыдущая13141516171819202122Следующая ⇒

Поделиться: