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

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

 

=== Определение ===

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

* '''Оператор суперпозиции''' (иногда — ''оператор подстановки''). Пусть <math>f</math> — функция от m переменных, а <math>g_1, \dots, g_m</math> — упорядоченный набор функций от <math>n</math> переменных каждая. Тогда результатом суперпозиции функций <math>g_k</math> в функцию <math>f</math> называется функция <math>h</math> от <math>n</math> переменных, сопоставляющая любому упорядоченному набору <math>x_1, \dots, x_n</math> натуральных чисел число

: <math>h(x_1,\ldots,x_n)=f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n))</math>.

: <math>h(x_1,\ldots,x_n,0)=f(x_1,\ldots,x_n)</math>;

: <math>h(x_1,\ldots,x_n,y+1)=g(x_1,\ldots,x_n,y,h(x_1,\ldots, x_n,y))</math>.

p(y+1)=I_2^1(y,\;p(y))\end{array}\right.</math>;

 

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

 

: <math>h(x_1,\ldots, x_{n-1}) = \min y</math>, при условии <math>f(x_1,\ldots,x_{n-1},\,y)=0</math>

: То есть функция <math>h</math> возвращает минимальное значение последнего аргумента функции <math>f</math>, при котором её значение равно 0.

Частично рекурсивные функции для некоторых значений аргумента могут быть не определены, так как оператор минимизации аргумента не всегда корректно определён, поскольку функция <math>f</math> может быть не равной нулю ни при каких значениях аргументов. С точки зрения императивного программирования, результатом частично рекурсивной функции может быть не только число, но и [[Исключение (программирование)|исключение]] или уход в бесконечный цикл, соответствующие неопределённому значению.

 

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

 

== Свойства ==

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

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

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

 

 

 

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

Термины «частично рекурсивная функция» и «общерекурсивная функция» прижились в силу исторических причин

и по сути являются результатом неточного перевода английских терминов ''partial recursive function''

 

== См. также ==

* [[Алгоритм Маркова]] ([[продукционное программирование]])

* [[Машина Тьюринга]] ([[автоматное программирование]])

* [[Brainfuck]] ([[императивное программирование]])

* [[Unlambda]] ([[функциональное исчисление]])

 

== Литература ==

* Верещагин Н. К., Шень А.Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции, 2-е изд., исправленное. — М.:МЦНМО, 2002.

 

{{rq|refless|isbn}}