Нам уже известно, что для п = 3 ответ может быть получен очень быстро, а для чисел п > 4 вычислительные операции никогда не закончатся (в соответствии с теоремой Лагранжа). Попробуем далее решить следующую задачу:
• Найти нечетное число, являющееся суммой п четных чисел.
В этом случае нам нет даже необходимости говорить о зависимости от п, поскольку для любых п вычисления никогда не закончатся. Наконец, в качестве обобщения проблемы Гольдбаха я предлагаю задачу следующего вида:
• Найти четное число больше 2, не являющееся суммой п простых чисел.
Если утверждение Гольдбаха верно, то вычисления будут длиться бесконечно для всех п (кроме 0 и 1). В некотором смысле доказательство даже упрощается с ростом п. Я действительно верю, что существует достаточно большое число п, для которого вычисления «продолжаются вечно».
Важнейшей характеристикой вычислений такого типа является их зависимость от чисел натурального ряда п, и именно это обстоятельство стало центральным моментом для так называемой теоремы Гёделя о неполноте (в Англии ее иногда называют догадкой или конъектурой Гёделя). Я буду рассматривать ее в формулировке, предложенной Аланом Тьюрингом, однако незначительно изменю ход его рассуждений. Если вы не любите математические выкладки, то можете просто пропустить этот кусок текста. Получаемый результат очень важен, но особенно интересно то, что доказательство вовсе не является сложным — оно всего лишь поразительно и даже вызывает недоумение!
Вычисления, связанные с конкретным числом п, совершенно стандартны и привычны для большинства компьютерных программ. Вы можете, например, просто взять набор программ, пронумеровать их в соответствии с текущим номером (обозначив его через р), а затем запустить компьютер, заложив в него этот порядковый номер. Компьютер начнет добросовестно «тарахтеть», последовательно осуществляя вычисления с числом п в соответствии с р-й программой. Вам необходимо лишь записать порядковый номер р в виде нижнего индекса справа, и тогда набор программ (или вычислений), связанных с числом п, примет простой и ясный вид
С(n), С1(n), С2(n), С3(n), ..., Сp(n), ... .
Предположим, что этот набор содержит все возможные вычисления Сp(n) и что мы можем найти какой-то эффективный метод упорядочения этих компьютерных программ, так что индекс р означает р-ю по порядку программу вычислений в соответствии с некоторым правилом, вследствие чего Сp(n) будет означать р-ю программу, примененную к числу п.
Предположим далее, что мы имеем какую-то вычислительную (т. е. алгоритмическую) процедуру А, относящуюся к паре чисел (р, п), осуществление которой дает очевидное и убедительное доказательство того, что работа программы Сp(n) еще не закончена. При этом вовсе не требуется, чтобы алгоритм А(р, п) работал постоянно, т. е. если вычисление Сp(n) является бесконечным, то это не значит, что характеризующий его алгоритм А(р, п) тоже будет выполняться за бесконечное время. Но я подчеркиваю, что алгоритм А (в соответствии с уже отмеченными свойствами компьютера) срабатывает без ошибок, т. е. если операция А(р, п) не завершена, то это также означает, что вычисление Сp(n) не закончено. А теперь представим себе, что какие-то математики, исходя из соображений типа описанного алгоритма А, сформулировали (или просто повторили) в строгом математическом виде некоторое утверждение (например, П1-утверждение). Предположим также, что они знают о существовании операции А и уверены в ее надежности и обоснованности. Представим себе далее, что процедура А включает в себя все операции, доступные математикам для того, чтобы убедить последних в бесконечном характере вычислений. Процедура А начинается с отбора программы, имеющей индекс р, а затем натурального числа п, к которому относится данная программа. Далее, если вычислительная операция А(р, п) закончена, то это означает, что вычисление Сp(n) не завершено, т.е.
Если операция А(р, п) завершена, то вычисление Сp(n) не закончено. (1)
Собственно говоря, в этом и заключается роль процедуры А — она должна давать неопровержимые доказательства того, что определенные вычисления не окончены.
Предположим далее, что р = п, в результате чего возникает хорошо известная и довольно забавная ситуация, известная под названием диагонализации Кантора (кстати, ее использование математически совершенно обоснованно), после которой мы вдруг приходим к следующему выводу:
Если операция А(п, п) завершена, то вычисление Сn(n) не закончено.
Но в данном случае A(п, п) зависит лишь от одного параметра п и, следовательно, принадлежит к набору вычислительных программ Сp(n) (поскольку этот список по определению включал в себя все вычисления, связанные с единственной переменной п). Предположим, что вычислительная программа, идентичная A(п, п), имела индекс k, т.е.
А(n, n) = Сk(n).
Положив n = k, мы тут же получаем
А(k, k) = Сk(k),
что в сочетании с условием (1) сразу приводит к заключению:
Если операция А(k, k) завершена, то вычисление Сk(k) не закончено.
Вспомнив, что А(k, k) совпадает с Сk(k), мы попадаем в логическую ловушку. Раз вычисление Сk(k) заканчивается, то оно не заканчивается (следовательно, оно заканчивается и т. д.). Ловушка заключается в том, что если мы доверяемся проверочной процедуре А, то должны верить и в то, что вычисление Сk(k) не закончено. Однако при этом процедура А тоже никак не может закончиться, т. е. «понять» наконец, что вычисление Сk(k) не кончается. Поэтому вычислительная процедура никак не может замкнуть цепочку математических рассуждений и решить, что заданное вычисление не заканчивается, т. е. установить истину П1-утверждения. В этом суть доводов Гёделя-Тьюринга в той форме, которая нужна мне для дальнейших рассуждений.
Вы можете подумать об общем смысле этого доказательства. Оно ясно демонстрирует, что математическое понимание и/или интуиция не могут быть закодированы в виде какого-то вычислительного процесса, в справедливости которого мы можем быть абсолютно уверены. Мне кажется, что приведенная формулировка наиболее ясным образом определяет сущность подхода Гёделя-Тьюринга, хотя некоторые придерживаются другой точки зрения. В этой связи интересно вспомнить, что писали сами эти авторы о полученном ими результате. Предлагаю вам одну из оценок Тьюринга:
«Другими словами, абсолютно безупречно работающая машина не может обладать интеллектом. Об этом свидетельствует ряд теорем, которые, однако, ничего не говорят о том, каким уровнем интеллекта может обладать машина, не претендующая на безошибочность и безупречность работы».
Таким образом, согласно Тьюрингу утверждения теоремы Гёделя-Тьюринга совместимы с идеей о том, что математиков можно действительно рассматривать в качестве компьютеров, если алгоритмические операции, выполняемые ими при выводе математических истин, не являются принципиально здравыми, обоснованными и разумными. Мы можем ограничиться рассмотрением лишь арифметических утверждений, например, лишь П1-высказываниями, которые представляют собой интересный, но весьма ограниченный тип утверждений. Мне кажется, что на самом деле Тьюринг верил в то, что человеческий мозг использует алгоритмы, но эти алгоритмы являются совершенно нерегулярными (именно в этом смысле они неразумны). Такая ситуация представляется неправдоподобной, поскольку она не только обескураживает, но и просто не позволяет понять, каким образом можно обсуждать что-то и приходить к каким-то выводам вообще. В любом случае точка зрения Тьюринга не внушает мне доверия, а в предложенной выше схеме (см. табл. 3.1) его рассуждения следует отнести к A-подходу.