Борис Бирюков - Жар холодных числ и пафос бесстрастной логики

Когда лед тронулся, процесс развивался уже лавинным образом. Тридцатые годы можно назвать «золотым десятилетием» математической логики; именно в этот период логика из падчерицы математики превратилась в ее органическую и важную часть. Но блестящий фейерверк работ этого периода не сопровождался фанфарами; дело делалось тихо и незаметно. Известность статей К. Гёделя. А. Чёрча, Ж. Эрбрана, С. К. Клини, А. М. Тьюринга, А. Тарского, Я. Лукасевича и других логиков тридцатых годов не выходила за рамки довольно узкого круга профессионалов. Перечисленные ученые принадлежали уже к новому поколению; большинство из них живы и сегодня. Являясь, по существу, пионерами нового взгляда на дедуктивные средства познания, они во время полемики Брауэра и Гильберта чувствовали себя юнцами, взирающими на спорящих титанов. Вряд ли они в то время думали, что их работы, посвященные специальным темам, окажут не меньшее влияние на методологию современного математического естествознания, чем многие знаменитые публикации признанных математических лидеров.

«Золотое десятилетие» заслуживает отдельной книги. Наше изложение не предусматривает подробного разбора этого периода; мы ограничимся лишь общим описанием тех результатов, которые непосредственно касаются становления кибернетики.

«Развитие математики в направлении все увеличивающейся строгости», о котором писал Гёдель, а еще более — критика математического платонизма привели к постановке до тех пор не стоявших вопросов: что такое конструктивный математический объект, то есть объект математического построения? Какие доказательства, выводы, числа, функции, формулы можно считать осуществимыми, вычислимыми?

Разберемся в сущности этой проблемы. Возьмем, например, число 2 64. Несмотря на то, что оно очень велико, его можно фактически записать в обычной десятеричной системе счисления. Число же 4 4 4 4таким образом записать уже нельзя — не хватит ни бумаги, ни типографской краски во всем мире. Но вряд ли есть смысл исключать из математики такие числа. Как и всякая теоретическая наука, математика нуждается в отвлечении от реальных условий, в использовании идеализации. В частности, в математических суждениях и выкладках полезно допускать, что в распоряжении рассуждающего всегда имеется достаточно большое количество бумаги и чернил или что доска, на которой пишутся формулы, достаточно велика. Полезно также предполагать, что имеется достаточно много времени для производства расчетов. При этих вполне разумных допущениях [1]число 4 4 4 4существует как бы фактически, являясь построяемым — конструктивным — объектом, хотя никто и никогда не выпишет его на бумаге. Конструктивность объекта в таком понимании сводится к тезису о его потенциальной осуществимости: объект, считающийся конструктивным, мог бы быть фактически получен (выписан), если бы мы располагали необходимым для этого временем (которое может быть необозримо большим, но в любом случае конечным), пространством (на размеры которого также не накладывается каких-либо ограничений) и материалами (масса которых может превосходить массу известной нам части Вселенной).

Для построения конструктивного объекта требуется осуществить всегда конечное число тех или иных актов поведения—действий, операций. Какой характер могут носить эти акты поведения? Они могут быть реальными действиями, совершаемыми над знаками как материальными образованиями, но могут быть действиями умственными — представлениями о реальных действиях. Далее, чтобы избежать опасности (которая после обнаружения парадоксов теории множеств стала очевидной) допущения в отдельных фазах построения объекта чреватых ошибками интуитивных обобщений, требуется, чтобы эти действия имели простой, элементарный характер. Различный выбор элементарных действий — шагов процесса, приводящего к построению конструктивного объекта, определяет разные подходы к уточнению идеи вычислимости. Мы рассмотрим три таких подхода. Первый подход — рекурсивный.

Определение рекурсивной функции содержалось уже в знаменитой статье Гёделя. Позже Гёдель, а также Ж. Эрбран, развили это понятие. Но особое звучание рекурсивным функциям придал американский логик и математик Алонзо Чёрч (род. в 1903 г.).

Дадим более аккуратное, чем в предшествующей главе, определение рекурсивной функции. Оно состоит из четырех пунктов. Всюду впредь в качестве аргументов и значений функций фигурируют лишь натуральные числа 0, 1, 2, ... (такие функции называют теоретико-числовыми, или арифметическими).