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

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

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, тождественно-равные нулю, то есть функции, для которых верно:

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

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

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

Функции, получающиеся из исходных конечным числом применений схем порождения I и II, называются примитивно рекурсивными; как очевидно, эти функции являются всюду определенными. К примитивно рекурсивным относятся не все, а только часть арифметических функций (правда, наиболее часто встречающееся такого рода функции примитивно рекурсивны). Если разрешить применять схему порождения III, то функции, которые будут таким образом возникать, называются частично рекурсивными. Хотя частично рекурсивные функции — как и примитивно рекурсивные — в конечной счете получаются из исходных (примитивно рекурсивных) функций (а), (б), (в), они в общем случае не всюду определены; это вызывается спецификой (μ-оператора, который из всюду определенной может породить частичную (и даже нигде не определенную) функцию. Если частично рекурсивная функция от n аргументов является всюду определенной (то есть если она определена для любого набора из n натуральных чисел), она называется общерекурсивной функцией. Таким образом, каждая примитивно рекурсивная функция является общерекурсивной, а каждая общерекурсивная — частично рекурсивной. Однако существуют частично рекурсивные функции, не являющиеся общерекурсивными, и общерекурсивные, не являющиеся примитивно рекурсивными.

Итак, математическая часть нами изложена; перейдем к методологическому аспекту разговора. Рассмотрим характер тех действий, которые производятся при вычислении значений рекурсивных функций.

Если исходная функция принадлежит к типу (а), то для любого набора значений ее аргументов ее значением является нуль. Эта функция «аннулирует» любой набор. Операция очень проста, она не требует особой фантазии или интуиции.

Работа с исходной функцией (б) сводится к написанию вместо данного числа такого числа, которое непосредственно следует за ним в натуральном ряду. Такая операция необходима для математики —это некий ее «голодный минимум». Она необходима также для любого конструктивного процесса, независимо от области, в которой он осуществляется. Брауэр, как мы знаем, считал процесс порождения следующего натурального числа изначальным актом, на котором зиждется вся деятельность интеллекта математика. Оставляя в стороне философскую сторону взглядов Брауэра, следует согласиться с тем, что операция «взятие следующего» обладает определенной «первичностью» — не ясно, к чему более простому можно было бы ее редуцировать.

Смысл проектирующих функций тоже очень прост: каждая из них отыскивает i-тый по порядку аргумент и объявляет его значением функции. Вычисление значений такой Функции выполняется с помощью обыкновенного счета: если дан определенный набор значений аргументов некоторой функции типа (в), то считывается нижний индекс i в ее обозначении и в упомянутом наборе отыскивается (с помощью счета) i-тое число; это число и оказывается значением функции.