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

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

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

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

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

Введем следующие способы (операторы) построения из арифметических функций новых арифметических функций. Эти способы предполагаются применяемыми как ко всюду определенным, так и к не всюду определенным (частичным) функциям.

I. Подстановка. Из функции получается новая функция, если вместо всех ее аргументов подставить функции[2].

II. Примитивная рекурсия[3]. Она заключается в получении (n + 1)-местной функции f из данных n-местной функции g и (n + 2)-местной функции h по схеме:

f(х1, х2,... хn, 0) = g(x1, х2,..., xn),

f(x1, х2,..., хn, m') = h(х1, х2,..., хn, m, f(х1, х2, ..., хn, m)).

Здесь n = 1,2, ...; для случая, когда аргументы х1, х2, ...,Хn (называемые параметрами рекурсии) отсутствуют, отдельно устанавливается f(0) =r (где r — фиксированное целое неотрицательное число), f(m') = h(m, f(m)). Здесь m'—число, непосредственно следующее за числом m в натуральном раду.

III. Мю-операция (или (μ-оператор). Пусть дана (n + 1)-местная функция (функция от n + 1 аргумента) g; по ней (μ-оператор строит n-местную функцию f следующим образом.

Для любого набора чисел х1, х2, ..., Хn f(х1, x2,... хn) равно наименьшему целому неотрицательному числу а, удовлетворяющему условию g (х1 ..., xn, а) = 0. Это число обозначается через рy(g (х1, ..., хn, у) = 0), откуда и название операции.

Если такого числа для набора чисел x1, х2, ..., хn не существует, то функция f на этом наборе не определена.

Будем считать теперь, что следующие всюду определенные функции, называемые исходными, рекурсивны.

(а) Многоместные функции (от n аргументов, n = 0, 1,2....) Nⁿ, тождественно-равные нулю, то есть функции, для которых верно:

Nⁿ (х1, х2, ..., Хn) = 0 при любых значениях аргументов.

(б) Одноместная функция S «следования за», то есть функция, для которой выполняется равенство S(х) = х' где штрих означает взятие числа, непосредственно следующего за x в натуральном ряду.

(в) n-местные проектирующие функции Iⁿi, Для которых Iⁿi{х1, .... xn) = xi ( i = 1, 2, ..., n; n = 1, 2, 3, ...).