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

• ;
• ;
• .

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

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

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

Определение

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

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

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

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

• Оператор суперпозиции (иногда — оператор подстановки ). Пусть ${\displaystyle f}$ — функция от m переменных, а ${\displaystyle g_{1},\dots ,g_{m}}$ — упорядоченный набор функций от ${\displaystyle n}$ переменных каждая. Тогда результатом суперпозиции функций ${\displaystyle g_{k}}$ в функцию ${\displaystyle f}$ называется функция ${\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 f}$ и ${\displaystyle g}$ называется функция ${\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 I_{1}^{1}}$ и ${\displaystyle F}$ , вторая из которых получается подстановкой основной функции ${\displaystyle I_{3}^{3}}$ в основную функцию ${\displaystyle S}$ :

${\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 O}$ и ${\displaystyle G}$ , вторая из которых получается подстановкой основных функций ${\displaystyle I_{3}^{1}}$ и ${\displaystyle I_{3}^{3}}$ в функцию сложения:

${\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 Sub(a,\;b)=|a-b|}$ ) может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения следующих подстановок и примитивных рекурсий:

${\displaystyle Sub(x,\;y)=Sum(Sub_{1}(x,\;y),\;Sub_{2}(x,\;y))}$ ;

${\displaystyle Sub_{2}(x,\;y)=Sub_{1}(I_{2}^{2}(x,\;y),\;I_{2}^{1}(x,\;y))}$ ;

${\displaystyle \left\{{\begin{array}{l}Sub_{1}(x,\;0)=I_{1}^{1}(x)\\Sub_{1}(x,\;y+1)=f(x,\;y,\;Sub_{1}(x,\;y))\end{array}}\right.}$ ;

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

${\displaystyle \left\{{\begin{array}{l}p(0)=0\\p(y+1)=I_{2}^{1}(y,\;p(y))\end{array}}\right.}$ ;

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

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

• Оператор минимизации аргумента . Пусть ${\displaystyle f}$ — функция от 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}$ может быть не равной нулю ни при каких значениях аргументов. С точки зрения императивного программирования, результатом частично рекурсивной функции может быть не только число, но и исключение или уход в бесконечный цикл, соответствующие неопределённому значению.

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

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

Свойства

Легко понять, что любая примитивно рекурсивная функция является частично рекурсивной, так как по определению операторы для построения частично рекурсивных функций включают в себя операторы для построения примитивно рекурсивных функций.

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

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

Как было показано Гёделем , частично рекурсивные функции совпадают с множеством вычислимых функций . ^{[ источник не указан 4361 день ]}

История возникновения названий

Термины «частично рекурсивная функция» и «общерекурсивная функция» прижились в силу исторических причин и по сути являются результатом неточного перевода английских терминов partial recursive function и total recursive function , которые по смыслу более правильно переводить как «рекурсивные функции, определенные на части множества возможных аргументов» и «рекурсивные функции, определенные на всём множестве возможных аргументов». Наречие «частично» относится не к прилагательному «рекурсивные», а к области определения функции. Возможно, более правильным названием было бы «частично определённые рекурсивные функции» и просто «везде определённые рекурсивные функции». Но длинные названия не прижились.

См. также

• Алгоритм Маркова ( )
• Машина Тьюринга ( автоматное программирование )
• Машина Поста ( автоматное программирование )
• Лямбда-исчисление ( функциональное программирование )
• Brainfuck ( императивное программирование )
• Unlambda ( функциональное исчисление )
• Примитивно рекурсивный функционал

Литература

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

Для улучшения этой статьи желательно : Проставить сноски , внести более точные указания на источники. Оформить список литературы. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.