Википедия

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

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
→‎Примеры: исправлено
отмена правки 81009080 участника Well very well (обс) было правильно
Строка 18:
К числу базовых примитивно рекурсивных функций относятся функции следующих трёх видов:
 
* ''Нулевая функция'' <math>O</math>  — функция без аргументов, всегда возвращающая [[0 (число)|0]].
* ''Функция следования'' <math>S</math> одного переменного, сопоставляющая любому натуральному числу <math>x</math> непосредственно следующее за ним натуральное число <math>x+1</math>.
* Функции <math>I_n^m</math>, где <math>0<m\leqslant n</math>, от n переменных, сопоставляющие любому упорядоченному набору <math>x_1,\dots, x_n</math> натуральных чисел число <math>x_m</math> из этого набора.
Строка 24:
Операторы подстановки и примитивной рекурсии определяются следующим образом:
 
* '''Оператор суперпозиции''' (иногда  — ''оператор подстановки''). Пусть <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>f</math>  — функция от n переменных, а <math>g</math>  — функция от <math>n+2</math> переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций <math>f</math> и <math>g</math> называется функция <math>h</math> от <math>n+1</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>.
 
В данном определении переменную <math>y</math> можно понимать как счётчик итераций, <math>f</math>  — как исходную функцию в начале итерационного процесса, выдающего некую последовательность функций <math>n</math> переменных, начинающуюся с <math>f</math>, и <math>g</math>  — как оператор, принимающий на вход <math>n</math> переменных <math>x_1,\ldots,x_n</math>, номер шага итерации <math>\left(y\right)</math>, функцию <math>h(x_1,\ldots, x_n,y)</math> на данном шаге итерации, и возвращающий функцию на следующем шаге итерации.
 
Множество '''примитивно рекурсивных функций'''  — это минимальное множество, содержащее все базовые функции и замкнутое относительно указанных операторов подстановки и примитивной рекурсии.
 
В терминах [[Императивное программирование|императивного программирования]]  — примитивно рекурсивные функции соответствуют программным блокам, в которых используется только арифметические операции, а также [[Оператор ветвления|условный оператор]] и оператор арифметического цикла ([[Цикл (программирование)|оператор цикла]], в котором число итераций известно на момент начала цикла). Если же программист начинает использовать оператор цикла <code>while</code>, в котором число итераций заранее неизвестно и, в принципе, может быть бесконечным, то он переходит в класс частично рекурсивных функций.
 
=== Примеры ===
Строка 46:
: <math>Mul(x,\;0)=O(x)</math>;
: <math>Mul(x,\;y+1)=G(x,\;y,\;Mul(x,y))</math>;
: <math>G(x,\;y,\;z)=Sum(I_3^21(x,\;y,\;z),I_3^3(x,\;y,\;z))</math>.
* ''Симметрическая разность'' (абсолютная величина разности) двух натуральных чисел (<math>Sub(a,\;b)=|a-b|</math>) может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения следующих подстановок и примитивных рекурсий:
: <math>Sub(x,\;y)=Sum(Sub_1(x,\;y),\; Sub_2(x,\;y))</math>;
Строка 58:
== Частично рекурсивная функция ==
<!-- используется для перенаправления [[Частично рекурсивная функция]] -->
'''Частично рекурсивная функция''' определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции и примитивной рекурсии добавляется ещё третий оператор  — минимизации аргумента.
 
* '''Оператор минимизации аргумента'''. Пусть <math>f</math>  — функция от ''n'' натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции <math>f</math> называется функция <math>h</math> от <math>n-1</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.
Строка 68:
== Общерекурсивная функция ==
<!-- используется для перенаправления [[Общерекурсивная функция]] -->
'''Общерекурсивная функция'''  — частично рекурсивная функция, определённая для всех значений аргументов. Задача определения того, является ли частично рекурсивная функция с данным описанием общерекурсивной или нет, [[Алгоритмическая неразрешимость|алгоритмически неразрешима]].
 
== Свойства ==
Строка 80:
Довольно сложно доказать существование и привести пример общерекурсивной функции, не являющейся примитивно рекурсивной. Одним из популярных примеров является [[функция Аккермана]]. Другой пример общерекурсивной функции, не являющейся примитивно рекурсивной, строится диагональным методом Кантора из универсальной функции для множества одноместных примитивно рекурсивных функций.
 
Как было показано [[Гёдель, Курт|Гёделем]], частично рекурсивные функции совпадают с множеством [[Вычислимые функции|вычислимых функций]].{{нет АИ|1|02|2012}}<!-- Это же тезис Чёрча  — Тьюринга. Что именно доказал Гёдель? -->
<!-- Гедель и Эрбран доказали, что всякая частично-рекурсивная функция ЭГ-вычислима, мендельсон «Введение в математическую логику», стр.263 -->
 
Строка 97:
 
== Литература ==
* ''Гильберт Д, Бернайс П.'' Основания математики. Т. 1.  — М.: Наука, 1979.
* ''Клини С. К.'' Введение в метаматематику.  — М., 1957.
* ''Мальцев А. И.'' Алгоритмы и рекурсивные функции. М.: Наука, 1986.
* ''Петер Р.'''Рекурсивные функции  — ИЛ, 1954.
* ''Верещагин Н. К., Шень А.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции, 2-е изд., исправленное.  — М.: МЦНМО, 2002.
 
== Ссылки ==
Источник — https://ru.wikipedia.org/wiki/Рекурсивная_функция_(теория_вычислимости)