Рекурсивная функция - NiNa.Az

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

Рекурсивная функция в теории вычислимости — функция, формализующая понятие рекурсии с вычислительной точки зрения; подразделяются на три последовательно входящих класса функций: примитивно рекурсивные➤, общерекурсивные➤ и частично рекурсивные➤. Последние совпадают с классом вычислимых по Тьюрингу функций и занимают центральное место в логике и теоретической информатике, соответственно, при упоминании рекурсивных функций без уточнения обычно имеются в виду частично рекурсивные функции. Введены Куртом Гёделем.

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

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

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

• нулевая функция ${\displaystyle O}$ — функция без аргументов, всегда возвращающая ;
• функция следования ${\displaystyle S}$ одной переменной, сопоставляющая любому натуральному числу ${\displaystyle x}$ непосредственно следующее за ним натуральное число ${\displaystyle x+1}$;
• функция ${\displaystyle I_{n}^{m}}$ (${\displaystyle 0<m\leqslant n}$) от ${\displaystyle n}$ переменных, сопоставляющая любому упорядоченному набору ${\displaystyle x_{1},\dots ,x_{n}}$ натуральных чисел число ${\displaystyle x_{m}}$ из этого набора (например, ${\displaystyle I_{3}^{2}(10,20,30)=20}$).

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

• оператор подстановки (оператор суперпозиции) для функции ${\displaystyle f}$ от ${\displaystyle m}$ переменных и упорядоченного набора ${\displaystyle m}$ функций ${\displaystyle g_{1},\dots ,g_{m}}$ от ${\displaystyle n}$ переменных каждая даёт функцию ${\displaystyle h}$ от ${\displaystyle n}$ переменных, сопоставляющую любому упорядоченному набору ${\displaystyle x_{1},\dots ,x_{n}}$ натуральных чисел число:

  ${\displaystyle h(x_{1},\ldots ,x_{n})=f{\big (}g_{1}(x_{1},\ldots ,x_{n}),\ldots ,g_{m}(x_{1},\ldots ,x_{n}){\big )}}$;

• оператор примитивной рекурсии для функции ${\displaystyle f}$ от ${\displaystyle n}$ переменных и функции ${\displaystyle g}$ от ${\displaystyle n+2}$ переменных дающий функцию ${\displaystyle h}$ от ${\displaystyle n+1}$ переменной вида:

  ${\displaystyle h(x_{1},\ldots ,x_{n},0)=f(x_{1},\ldots ,x_{n})}$,

  ${\displaystyle h(x_{1},\ldots ,x_{n},y+1)=g(x_{1},\ldots ,x_{n},y,h(x_{1},\ldots ,x_{n},y))}$.

В данном определении переменную ${\displaystyle y}$ можно понимать как счётчик итераций, ${\displaystyle f}$ — как исходную функцию в начале итерационного процесса, выдающего некую последовательность функций ${\displaystyle n}$ переменных, начинающуюся с ${\displaystyle f}$, и ${\displaystyle g}$ — как оператор, принимающий на вход ${\displaystyle n}$ переменных ${\displaystyle x_{1},\ldots ,x_{n}}$, номер шага итерации ${\displaystyle y}$, функцию ${\displaystyle h(x_{1},\ldots ,x_{n},y)}$ на данном шаге итерации, и возвращающий функцию на следующем шаге итерации.

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

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

Например, примитивно рекурсивны функция сложения двух натуральных чисел (${\displaystyle Sum(a,\;b)=a+b}$):

${\displaystyle Sum(x,\;0)=I_{1}^{1}(x)}$;

${\displaystyle Sum(x,\;y+1)=F(x,\;y,\;Sum(x,\;y))}$;

${\displaystyle F(x,\;y,\;z)=S(I_{3}^{3}(x,\;y,\;z))}$

и функция умножения двух натуральных чисел (${\displaystyle Mul(a,\;b)=a\times b}$):

${\displaystyle Mul(x,\;0)=O(x)}$;

${\displaystyle Mul(x,\;y+1)=G(x,\;y,\;Mul(x,y))}$;

${\displaystyle G(x,\;y,\;z)=Sum(I_{3}^{1}(x,\;y,\;z),I_{3}^{3}(x,\;y,\;z))}$.

Примитивно рекурсивный функционал — обобщение понятия примитивно рекурсивной функции в многомерной теории типов.

Частично рекурсивная функция

Частично рекурсивная функция определяется аналогично примитивно рекурсивной, только к двум операторам, суперпозиции и примитивной рекурсии, добавляется ещё третий оператор — минимизации аргумента, дающий для функции от ${\displaystyle n}$ переменных ${\displaystyle f}$ функцию ${\displaystyle h}$ от ${\displaystyle n-1}$ переменной, задаваемую следующим определением:

${\displaystyle h(x_{1},\ldots ,x_{n-1})=\min y}$, при условии ${\displaystyle f(x_{1},\ldots ,x_{n-1},\,y)=0}$

(то есть функция ${\displaystyle h}$ возвращает минимальное значение последнего аргумента функции ${\displaystyle f}$, при котором её значение равно 0).

Частично рекурсивные функции для некоторых значений аргумента могут быть не определены, так как оператор минимизации аргумента не всегда корректно определён, поскольку функция ${\displaystyle f}$ может быть не равной нулю ни при каких значениях аргументов. С точки зрения императивного программирования, результатом частично рекурсивной функции может быть не только число, но и исключение или уход в бесконечный цикл, соответствующие неопределённому значению.

Общерекурсивная функция

Общерекурсивная функция — частично рекурсивная функция, определённая для всех значений аргументов. Задача определения того, является ли частично рекурсивная функция с данным описанием общерекурсивной или нет, алгоритмически неразрешима.

Пример общерекурсивной функции, не являющейся примитивно рекурсивной — функция Аккермана. Другой пример общерекурсивной функции, не являющейся примитивно рекурсивной, строится диагональным методом Кантора из универсальной функции для множества одноместных примитивно рекурсивных функций.

Литература

• Гильберт Д., Бернайс П. Основания математики. — М.: Наука, 1979. — Т. 1.
• Клини С. К. Введение в метаматематику. — М.: Иностранная литература, 1957.
• Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1986.
• Петер Р. Рекурсивные функции . — М.: Иностранная литература, 1954.
• Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. — 2-е изд., исправленное. — М.: МЦНМО, 2002. — Т. 3. Вычислимые функции.