Определение

Рекурсивная функция (теория вычислимости)

Материал из Википедии — свободной энциклопедии

У этого термина существуют и другие значения, см. Рекурсивная функция (значения).

Термин рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций

• примитивно рекурсивные функции;
• общерекурсивные функции;
• частично рекурсивные функции.

Последние совпадают с классом вычислимых по Тьюрингу функций. Определения этих трёх классов сильно связаны. Они были введены Куртом Гёделем с целью формализации понятия вычислимости.

Множество частично рекурсивных функции включает в себя множество общерекурсивных функции, а общерекурсивные функции включают в себя примитивно рекурсивные функции. Частично рекурсивные функции иногда называют просто рекурсивными функциями.

Примитивно рекурсивная функция

Определение

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

К числу базовых примитивно рекурсивных функций относятся функции следующих трёх видов:

• Нулевая функция O — функция без аргументов, всегда возвращающая 0.
• Функция следования S одного переменного, сопоставляющая любому натуральному числу x непосредственно следующее за ним натуральное число x + 1.
• Функции , где , от n переменных, сопоставляющие любому упорядоченному набору натуральных чисел число x_m из этого набора.

Операторы подстановки и примитивной рекурсии определяются следующим образом:

• Оператор суперпозиции (иногда — оператор подстановки). Пусть f — функция от m переменных, а — упорядоченный набор функций от n переменных каждая. Тогда результатом суперпозиции функций g_k в функцию f называется функция h от n переменных, сопоставляющая любому упорядоченному набору натуральных чисел число

.

• Оператор примитивной рекурсии. Пусть f — функция от n переменных, а g — функция от n + 2 переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций f и g называется функция h от n + 1 переменной вида

;

.

В данном определении переменную y можно понимать как счётчик итераций, f — как исходную функцию в начале итерационного процесса, выдающего некую последовательность функций n переменных, начинающуюся с f, и g — как оператор, принимающий на вход n переменных , номер шага итерации , функцию на данном шаге итерации, и возвращающий функцию на следующем шаге итерации.

Множество примитивно рекурсивных функций — это минимальное множество, содержащее все базовые функции и замкнутое относительно указанных операторов подстановки и примитивной рекурсии.

Примеры

Укажем на ряд широко известных арифметических функций, являющихся примитивно рекурсивными.

• Функция Сложения двух натуральных чисел ( ) может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям и , вторая из которых получается подстановкой основной функции в основную функцию S:

;

;

.

• Умножение двух натуральных чисел ( ) может быть рассмотрено в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям O и G, вторая из которых получается подстановкой основных функций и в функцию сложения:

;

;

.

• Симметрическая разность (абсолютная величина разности) двух натуральных чисел ( ) может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения следующих подстановок и примитивных рекурсий:

;

;

;

;

;