имеем здесь дело с классом математических проблем гораздо более ограниченной природы, нежели те, что, подобно аксиоме выбора и континуум-гипотезе, относятся к неконструктивно-бесконечным множествам. В данном случае нас занимают лишь утверждения вида
«такое-то вычисление никогда не завершается»,
причем рассматриваемые вычисления можно задать совершенно точно через действия машины Тьюринга. Такие утверждения в логике называются Π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 следующим образом:
