В большей части предлагаемых рассуждений я не стану проводить четкую границу между непротиворечивостью и ω-непротиворечивостью, однако тот вариант теоремы Гёделя, что представлен в §2.5, по сути, гласит, что если формальная система Fнепротиворечива, то она не может быть полной, так как не может включать в себя в качестве теоремы утверждение G( F). Здесь я всего этого демонстрировать не буду (интересующиеся же могут обратиться к [ 223]). Вообще говоря, для того чтобы эту форму гёделевского доказательства можно было свести к доказательству в моей формулировке, система Fдолжна содержать в себе нечто большее, нежели просто «арифметику и обыкновенную логику». Необходимо, чтобы система Fбыла обширной настолько, чтобы включать в себя действия любой машины Тьюринга. Иначе говоря, среди утверждений, корректно формулируемых с помощью символов системы F, должны присутствовать утверждения типа: «Такая-то машина Тьюринга, оперируя над натуральным числом n, дает на выходе натуральное число p». Более того, имеется теорема (см. [ 223], главы 11 и 13), согласно которой так оно само собой и получается, если, помимо обычных арифметических операций, система Fсодержит следующую операцию (так называемую μ-операцию, или операцию минимизации): «найти наименьшее натуральное число, обладающее таким-то арифметическим свойством». Вспомним, что в нашем первом вычислительном примере, (A), предложенная процедура действительно позволяла отыскать наименьшеечисло, не являющееся суммой трех квадратов. То есть, вообще говоря, право на подобные вещи за вычислительными процедурами следует сохранить. С другой стороны, именно благодаря этойих особенности мы и сталкиваемся с вычислениями, которые принципиально не завершаются, — например, вычисление (В), где мы пытаемся отыскать наименьшее число, не являющееся суммой четырехквадратов, а такого числа в природе не существует.

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

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

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

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

Поставив перед собой задачу построить на основе процедуры  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доказательство было сформулировано исключительно для вычислений, оно сгодится и для общих формальных систем. В том доказательстве, если помните, речь шла о совокупности всех вычислениях (действий машины Тьюринга) C _q( n). Следовательно, для того чтобы оно оказалось во всех отношениях применимо к формальной системе F, эта система должна быть достаточно обширной для того, чтобы включать в себя действия всех машин Тьюринга. Алгоритмическую процедуру A, предназначенную для установления факта незавершаемости некоторых вычислений, мы можем теперь добавить к правилам системы Fс тем, чтобы вычисления, предположения о незавершающемся характере которых устанавливаются в рамках Fкак ИСТИННЫЕ, были бы тождественны всем тем вычислениям, незавершаемость которых определяется с помощью процедуры A.