Действительно, электронная вычислительная машина есть универсальный инструмент вычисления, о чем пойдет речь ниже. Конечно, в самой схеме ЭВМ вовсе не заложен аксиоматически-дедуктивный метод получения теорем. Но машину в принципе всегда можно «научить» выводить теоремы с помощью заданных правил вывода из заданных аксиом (правда, соответствующие программы могут оказаться очень сложными). В результате машина «овладевает» дедуктивным методом доказательства теорем и, естественно, оказывается подвластной ограничениям, которые налагают на этот процесс положения Гёделя. Но эти же самые ограничения распространяются ина человека, если он работает строго по дедуктивному методу[8].
Впрочем, ограничения, вытекающие из результатов Гёделя, относятся не к дедуктивному методу вообще, а к таким дедуктивным системам, которые содержат теорию натуральных чисел и в которых доказательства представляют собой эффективно распознаваемые (за конечное число шагов) объекты. Но как показало последующее развитие математической логики, проблему непротиворечивости и другие проблемы, касающиеся формальных систем, можно исследовать методами, выходящими за пределы подобного финитизма, но представляющимися достаточно надежными. На этом пути становится возможным, например, доказательство непротиворечивости классической формальной арифметики[9].
Результаты Гёделя, во всяком случае, раскрывают важную особенность определенного аппарата, служащего знанию с большой эффективностью, поэтому часто принимавшегося за аппарат абсолютный и окончательный, аппарата формальной выводимости. Лишая аксиоматически-дедуктивный метод (коль скоро он пользуется лишь средствами строго финитного характера) статуса абсолютного, они разрушают его гипнотическое влияние на математиков и логиков и заставляют их не отождествлять более этот метод с дедуктивным методом вообще, искать новые способы построений, ведущих к познанию истины. В этом заряде антидогматизма заключена большая философ. екая ценность теоремы о неполноте. Она заставляет размышлять над тем, что такое знаковое моделирование реальности, что такое строгая теория и сколь разнообразными могут быть ее разновидности»
7. ЧТО ТАКОЕ «МОЖНО ВЫЧИСЛИТЬ»?
Блестящее исследование Гёделя оказалось возможным благодаря тому, что математический материал, относящийся к логике и теория вывода, достиг уже «критической массы». В логике и основаниях математики образовался солидный багаж конкретных достижений. Стала известной специалистам концепция формализованной арифметики Фреге. Была сформулирована формальная аксиоматическая система теории множеств Цермело—Франкеля. Вышли в свет Principia Mathematica. В свете успехов алгебры новую оценку получили работы Буля. Манифесты Брауэра привели к углубленному анализу классической логики и впервые в истории поставили вопрос о ее пересмотре. Наконец, была провозглашена программа Гильберта, которая хотя и оказалась невыполнимой в центральном пункте, придала исследованиям новый дух и поставила перед ними новые задачи.
Когда лед тронулся, процесс развивался уже лавинным образом. Тридцатые годы можно назвать «золотым десятилетием» математической логики; именно в этот период логика из падчерицы математики превратилась в ее органическую и важную часть. Но блестящий фейерверк работ этого периода не сопровождался фанфарами; дело делалось тихо и незаметно. Известность статей К. Гёделя. А. Чёрча, Ж. Эрбрана, С. К. Клини, А. М. Тьюринга, А. Тарского, Я. Лукасевича и других логиков тридцатых годов не выходила за рамки довольно узкого круга профессионалов. Перечисленные ученые принадлежали уже к новому поколению; большинство из них живы и сегодня. Являясь, по существу, пионерами нового взгляда на дедуктивные средства познания, они во время полемики Брауэра и Гильберта чувствовали себя юнцами, взирающими на спорящих титанов. Вряд ли они в то время думали, что их работы, посвященные специальным темам, окажут не меньшее влияние на методологию современного математического естествознания, чем многие знаменитые публикации признанных математических лидеров.
«Золотое десятилетие» заслуживает отдельной книги. Наше изложение не предусматривает подробного разбора этого периода; мы ограничимся лишь общим описанием тех результатов, которые непосредственно касаются становления кибернетики.
«Развитие математики в направлении все увеличивающейся строгости», о котором писал Гёдель, а еще более — критика математического платонизма привели к постановке до тех пор не стоявших вопросов: что такое конструктивный математический объект, то есть объект математического построения? Какие доказательства, выводы, числа, функции, формулы можно считать осуществимыми, вычислимыми?
Разберемся в сущности этой проблемы. Возьмем, например, число 264. Несмотря на то, что оно очень велико, его можно фактически записать в обычной десятеричной системе счисления. Число же 4444 таким образом записать уже нельзя — не хватит ни бумаги, ни типографской краски во всем мире. Но вряд ли есть смысл исключать из математики такие числа. Как и всякая теоретическая наука, математика нуждается в отвлечении от реальных условий, в использовании идеализации. В частности, в математических суждениях и выкладках полезно допускать, что в распоряжении рассуждающего всегда имеется достаточно большое количество бумаги и чернил или что доска, на которой пишутся формулы, достаточно велика. Полезно также предполагать, что имеется достаточно много времени для производства расчетов. При этих вполне разумных допущениях[1] число 4444существует как бы фактически, являясь построяемым — конструктивным — объектом, хотя никто и никогда не выпишет его на бумаге. Конструктивность объекта в таком понимании сводится к тезису о его потенциальной осуществимости: объект, считающийся конструктивным, мог бы быть фактически получен (выписан), если бы мы располагали необходимым для этого временем (которое может быть необозримо большим, но в любом случае конечным), пространством (на размеры которого также не накладывается каких-либо ограничений) и материалами (масса которых может превосходить массу известной нам части Вселенной).
Для построения конструктивного объекта требуется осуществить всегда конечное число тех или иных актов поведения—действий, операций. Какой характер могут носить эти акты поведения? Они могут быть реальными действиями, совершаемыми над знаками как материальными образованиями, но могут быть действиями умственными — представлениями о реальных действиях. Далее, чтобы избежать опасности (которая после обнаружения парадоксов теории множеств стала очевидной) допущения в отдельных фазах построения объекта чреватых ошибками интуитивных обобщений, требуется, чтобы эти действия имели простой, элементарный характер. Различный выбор элементарных действий — шагов процесса, приводящего к построению конструктивного объекта, определяет разные подходы к уточнению идеи вычислимости. Мы рассмотрим три таких подхода. Первый подход — рекурсивный.
Определение рекурсивной функции содержалось уже в знаменитой статье Гёделя. Позже Гёдель, а также Ж. Эрбран, развили это понятие. Но особое звучание рекурсивным функциям придал американский логик и математик Алонзо Чёрч (род. в 1903 г.).
Дадим более аккуратное, чем в предшествующей главе, определение рекурсивной функции. Оно состоит из четырех пунктов. Всюду впредь в качестве аргументов и значений функций фигурируют лишь натуральные числа 0, 1, 2, ... (такие функции называют теоретико-числовыми, или арифметическими).
Введем следующие способы (операторы) построения из арифметических функций новых арифметических функций. Эти способы предполагаются применяемыми как ко всюду определенным, так и к не всюду определенным (частичным) функциям.
I. Подстановка. Из функции получается новая функция, если вместо всех ее аргументов подставить функции[2].
II. Примитивная рекурсия[3]. Она заключается в получении (n + 1)-местной функции f из данных n-местной функции g и (n + 2)-местной функции h по схеме:
118
8. Краткий, но достаточно ясный обзор проблематики исследований формальных систем читатель найдет в гл. I кн.: С. Клини. Математическая логика. М., 1973.
9. Одно из таких доказательств приводится в кн.: Э. Мендельсон. Введение в математическую логику. М., 1971, с. 282—295.
119
1. Совокупность этих допущений составляет то, что обычно называют
120
2. Более строго операцию подстановки можно задать следующим образом. По n-местным функциям q1..., gm и m-местной функции h строится n-местная функция f такая, что для любых x1, x2,..., Хn
f(x1, x2,..., Хn) = h(x1, ... Хn),... gm(x1,... Хn)).
121
3. Обращаем внимание на то, что в определениях операторов I—III знак равенства (=) следует понимать как знак так называемого