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

В теории вычислимости — примитивно-рекурсивная функция это, грубо говоря, функция, которая может быть вычислена с помощью компьютерной программы которой , все циклы являются циклами «for» (т. е. верхняя граница числа итераций каждого цикла фиксируется перед вводом петля). Примитивно-рекурсивные функции образуют строгое подмножество тех общерекурсивных функций , которые также являются полными функциями .

Важность примитивно-рекурсивных функций заключается в том, что большинство вычислимых функций , изучаемых в теории чисел (и в более общем плане в математике), являются примитивно-рекурсивными. Например, сложение и деление , факториал и экспоненциальная функция , а также функция, возвращающая n- е простое число, являются примитивно-рекурсивными. Фактически, чтобы показать, что вычислимая функция является примитивно-рекурсивной, достаточно показать, что ее временная сложность ограничена сверху примитивно-рекурсивной функцией входного размера. Следовательно, не так-то просто придумать вычислимую функцию , которая не была бы примитивно-рекурсивной; некоторые примеры показаны в разделе § Ограничения ниже.

Набор примитивно-рекурсивных функций известен как PR в теории сложности вычислений .

Определение

Примитивная рекурсивная функция принимает фиксированное количество аргументов, каждый из которых является натуральным числом (неотрицательное целое число: {0, 1, 2, ...}), и возвращает натуральное число. Если он принимает n аргументов, он называется n - арным .

Основные примитивно-рекурсивные функции задаются этими аксиомами :

1. Постоянные функции $C_{n}^{k}$: Для каждого натурального числа $n$ и каждый $k$, k -арная постоянная функция, определенная формулой $C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n$, является примитивно-рекурсивным.
2. Функция-преемник : 1-арная функция-преемник S , которая возвращает преемника своего аргумента (см. постулаты Пеано ), то есть, $S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1$, является примитивно-рекурсивным.
3. Функции проецирования $P_{i}^{k}$: Для всех натуральных чисел $i,k$ такой, что $1\leq i\leq k$, k -арная функция, определенная формулой $P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}$ является примитивно-рекурсивным.

Более сложные примитивно-рекурсивные функции можно получить, применяя операции, заданные этими аксиомами:

4. Оператор композиции $\circ \,$ (также называемый оператором подстановки ): для данной m -арной функции $h(x_{1},\ldots ,x_{m})\,$ и m k -арные функции $g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})$: $$h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})).$$ Для $m=1$, обычная композиция функций $h\circ g_{1}$ получается.
5. Примитивный оператор рекурсии $\rho$: Учитывая k -арную функцию $g(x_{1},\ldots ,x_{k})\,$ и ( k + 2)-арная функция $h(y,z,x_{1},\ldots ,x_{k})\,$: $${\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where the }}(k+1){\text{-ary function }}f{\text{ is defined by}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(S(y),x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k}).\end{aligned}}$$

   Интерпретация:

   Функция $f$ действует как цикл for из $0$ до значения его первого аргумента. Остальные аргументы в пользу $f$, обозначенный здесь $x_{1},\ldots ,x_{k}$, представляют собой набор начальных условий для цикла for, которые могут использоваться им во время вычислений, но являются для него неизменяемыми. Функции $g$ и $h$ в правой части уравнений, определяющих $f$ представляют тело цикла, который выполняет вычисления. Функция $g$ используется только один раз для выполнения первоначальных вычислений. Расчеты для последующих шагов цикла выполняются по формуле $h$. Первый параметр $h$ передается «текущее» значение индекса цикла for. Второй параметр $h$ передается результат предыдущих вычислений цикла for из предыдущих шагов. Остальные параметры для $h$ — это те неизменные начальные условия для цикла for, упомянутые ранее. Они могут быть использованы $h$ выполнять вычисления, но сами они не будут изменены $h$.

Примитивно -рекурсивные функции — это базовые функции и функции, полученные из базовых функций путем применения этих операций конечное число раз.

Примеры

• $C_{0}^{1}$ — это 1-арная функция, которая возвращает $0$ для каждого входа: $C_{0}^{1}(x)=0$.
• $C_{1}^{1}$ — это 1-арная функция, которая возвращает $1$ для каждого входа: $C_{1}^{1}(x)=1$.
• $C_{3}^{0}$ является 0-арной функцией, т.е. константой: $C_{3}^{0}=3$.
• $P_{1}^{1}$ - тождественная функция натуральных чисел: $P_{1}^{1}(x)=x$.
• $P_{1}^{2}$ и $P_{2}^{2}$ — левая и правая проекции на пары натуральных чисел соответственно: $P_{1}^{2}(x,y)=x$ и $P_{2}^{2}(x,y)=y$.
• $S\circ S$ — это 1-арная функция, которая добавляет 2 к своим входным данным, $(S\circ S)(x)=x+2$.
• $S\circ C_{0}^{1}$ — это 1-арная функция, которая возвращает 1 для каждого ввода: $(S\circ C_{0}^{1})(x)=S(C_{0}^{1}(x))=S(0)=1$. То есть, $S\circ C_{0}^{1}$ и $C_{1}^{1}$ это одна и та же функция: $S\circ C_{0}^{1}=C_{1}^{1}$. Подобным образом каждый $C_{n}^{k}$ можно выразить как композицию достаточного количества $S$ и $C_{0}^{k}$. Более того, $C_{0}^{k}$ равно $C_{0}^{1}\circ P_{1}^{k}$, с $C_{0}^{k}(x_{1},\ldots ,x_{k})=0=C_{0}^{1}(x_{1})=C_{0}^{1}(P_{1}^{k}(x_{1},\ldots ,x_{k}))=(C_{0}^{1}\circ P_{1}^{k})(x_{1},\ldots ,x_{k})$. По этим причинам некоторые авторы определять $C_{n}^{k}$ только для $n=0$ и $k=1$.

Добавление

Определение 2-арной функции $Add$, для вычисления суммы его аргументов, можно получить с помощью примитивного оператора рекурсии $\rho$. Для этого используются известные уравнения

${\begin{array}{rcll}0+y&=&y&{\text{ and}}\\S(x)+y&=&S(x+y)&.\\\end{array}}$

«перефразированы в терминологии примитивно-рекурсивных функций»: в определении $\rho (g,h)$, первое уравнение предлагает выбрать $g=P_{1}^{1}$ чтобы получить $Add(0,y)=g(y)=y$; второе уравнение предлагает выбрать $h=S\circ P_{2}^{3}$ чтобы получить $Add(S(x),y)=h(x,Add(x,y),y)=(S\circ P_{2}^{3})(x,Add(x,y),y)=S(Add(x,y))$. Следовательно, функцию сложения можно определить как $Add=\rho (P_{1}^{1},S\circ P_{2}^{3})$. В качестве примера вычислений:

${\begin{array}{lll}&Add(1,7)\\=&\rho (P_{1}^{1},S\circ P_{2}^{3})\;(S(0),7)&{\text{ by Def. }}Add,S\\=&(S\circ P_{2}^{3})(0,Add(0,7),7)&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&S(Add(0,7))&{\text{ by Def. }}\circ ,P_{2}^{3}\\=&S(\;\rho (P_{1}^{1},S\circ P_{2}^{3})\;(0,7)\;)&{\text{ by Def. }}Add\\=&S(P_{1}^{1}(7))&{\text{ by case }}\rho (g,h)\;(0,...)\\=&S(7)&{\text{ by Def. }}P_{1}^{1}\\=&8&{\text{ by Def. }}S.\\\end{array}}$

удвоение

Данный $Add$, 1-арная функция $Add\circ (P_{1}^{1},P_{1}^{1})$ удваивает свой аргумент, $(Add\circ (P_{1}^{1},P_{1}^{1}))(x)=Add(x,x)=x+x$.

Умножение

Подобно сложению, умножение можно определить формулой $Mul=\rho (C_{0}^{1},Add\circ (P_{2}^{3},P_{3}^{3}))$. Это воспроизводит известные уравнения умножения:

${\begin{array}{lll}&Mul(0,y)\\=&\rho (C_{0}^{1},Add\circ (P_{2}^{3},P_{3}^{3}))\;(0,y)&{\text{ by Def. }}Mul\\=&C_{0}^{1}(y)&{\text{ by case }}\rho (g,h)\;(0,...)\\=&0&{\text{ by Def. }}C_{0}^{1}.\\\end{array}}$

и

${\begin{array}{lll}&Mul(S(x),y)\\=&\rho (C_{0}^{1},Add\circ (P_{2}^{3},P_{3}^{3}))\;(S(x),y)&{\text{ by Def. }}Mul\\=&(Add\circ (P_{2}^{3},P_{3}^{3}))\;(x,Mul(x,y),y)&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&Add(Mul(x,y),y)&{\text{ by Def. }}\circ ,P_{2}^{3},P_{3}^{3}\\=&Mul(x,y)+y&{\text{ by property of }}Add.\\\end{array}}$

Предшественник

Функция-предшественница действует как «противоположность» функции-последователя и рекурсивно определяется правилами $Pred(0)=0$ и $Pred(S(n))=n$. Примитивное рекурсивное определение $Pred=\rho (C_{0}^{0},P_{1}^{2})$. В качестве примера вычислений:

${\begin{array}{lll}&Pred(8)\\=&\rho (C_{0}^{0},P_{1}^{2})\;(S(7))&{\text{ by Def. }}Pred,S\\=&P_{1}^{2}(7,Pred(7))&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&7&{\text{ by Def. }}P_{1}^{2}.\\\end{array}}$

Усеченное вычитание

Ограниченная функция вычитания (также называемая « монус » и обозначаемая « ${\stackrel {.}{-}}$") определяется из функции-предшественника. Он удовлетворяет уравнениям

${\begin{array}{rcll}y{\stackrel {.}{-}}0&=&y&{\text{and}}\\y{\stackrel {.}{-}}S(x)&=&Pred(y{\stackrel {.}{-}}x)&.\\\end{array}}$

Поскольку рекурсия проходит по второму аргументу, мы начинаем с примитивно-рекурсивного определения обратного вычитания: $RSub(y,x)=x{\stackrel {.}{-}}y$. Затем его рекурсия проходит по первому аргументу, поэтому можно получить его примитивно-рекурсивное определение, аналогично сложению, как $RSub=\rho (P_{1}^{1},Pred\circ P_{2}^{3})$. Чтобы избавиться от обратного порядка аргументов, определите $Sub=RSub\circ (P_{2}^{2},P_{1}^{2})$. В качестве примера вычислений:

${\begin{array}{lll}&Sub(8,1)\\=&(RSub\circ (P_{2}^{2},P_{1}^{2}))\;(8,1)&{\text{ by Def. }}Sub\\=&RSub(1,8)&{\text{ by Def. }}\circ ,P_{2}^{2},P_{1}^{2}\\=&\rho (P_{1}^{1},Pred\circ P_{2}^{3})\;(S(0),8)&{\text{ by Def. }}RSub,S\\=&(Pred\circ P_{2}^{3})\;(0,RSub(0,8),8)&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&Pred(RSub(0,8))&{\text{ by Def. }}\circ ,P_{2}^{3}\\=&Pred(\;\rho (P_{1}^{1},Pred\circ P_{2}^{3})\;(0,8)\;)&{\text{ by Def. }}RSub\\=&Pred(P_{1}^{1}(8))&{\text{ by case }}\rho (g,h)\;(0,...)\\=&Pred(8)&{\text{ by Def. }}P_{1}^{1}\\=&7&{\text{ by property of }}Pred.\\\end{array}}$

Преобразование предикатов в числовые функции

В некоторых ситуациях естественно рассматривать примитивно-рекурсивные функции, которые принимают в качестве входных данных кортежи, смешивающие числа со значениями истинности (т.е. $t$ для истинного и $f$ для false), или которые выдают на выходе значения истинности. Этого можно достичь путем идентификации значений истинности с числами любым фиксированным способом. Например, обычно определяют истинностное значение $t$ с номером $1$ и истинное значение $f$ с номером $0$. Как только это отождествление сделано, характеристическая функция множества $A$, который всегда возвращает $1$ или $0$, можно рассматривать как предикат, который сообщает, находится ли число в наборе $A$. Такая идентификация предикатов с числовыми функциями будет предполагаться в оставшейся части статьи.

Предикат «Ноль»

В качестве примера примитивно-рекурсивного предиката можно привести 1-арную функцию. $IsZero$ должно быть определено так, чтобы $IsZero(x)=1$ если $x=0$, и $IsZero(x)=0$, в противном случае. Этого можно достичь, определив $IsZero=\rho (C_{1}^{0},C_{0}^{2})$. Затем, $IsZero(0)=\rho (C_{1}^{0},C_{0}^{2})(0)=C_{1}^{0}(0)=1$ и например $IsZero(8)=\rho (C_{1}^{0},C_{0}^{2})(S(7))=C_{0}^{2}(7,IsZero(7))=0$.

Предикат «Меньше или равно»

Использование недвижимости $x\leq y\iff x{\stackrel {.}{-}}y=0$, 2-арная функция $Leq$ может быть определен $Leq=IsZero\circ Sub$. Затем $Leq(x,y)=1$ если $x\leq y$, и $Leq(x,y)=0$, в противном случае. В качестве примера вычислений:

${\begin{array}{lll}&Leq(8,3)\\=&IsZero(Sub(8,3))&{\text{ by Def. }}Leq\\=&IsZero(5)&{\text{ by property of }}Sub\\=&0&{\text{ by property of }}IsZero\\\end{array}}$

Предикат «Больше или равно»

Как только определение $Leq$ получен, обратный предикат можно определить как $Geq=Leq\circ (P_{2}^{2},P_{1}^{2})$. Затем, $Geq(x,y)=Leq(y,x)$ истинно (точнее: имеет значение 1) тогда и только тогда, когда $x\geq y$.

Если-то-иначе

Трехмерный оператор if-then-else, известный в языках программирования, можно определить следующим образом: ${\textit {If}}=\rho (P_{2}^{2},P_{3}^{4})$. Тогда для произвольного $x$,

${\begin{array}{lll}&{\textit {If}}(S(x),y,z)\\=&\rho (P_{2}^{2},P_{3}^{4})\;(S(x),y,z)&{\text{ by Def. }}{\textit {If}}\\=&P_{3}^{4}(x,{\textit {If}}(x,y,z),y,z)&{\text{ by case }}\rho (S(...),...)\\=&y&{\text{ by Def. }}P_{3}^{4}\\\end{array}}$

и

${\begin{array}{lll}&{\textit {If}}(0,y,z)\\=&\rho (P_{2}^{2},P_{3}^{4})\;(0,y,z)&{\text{ by Def. }}{\textit {If}}\\=&P_{2}^{2}(y,z)&{\text{ by case }}\rho (0,...)\\=&z&{\text{ by Def. }}P_{2}^{2}.\\\end{array}}$.

То есть, ${\textit {If}}(x,y,z)$ возвращает часть then, $y$, если if-часть, $x$, верно, а остальная часть, $z$, в противном случае.

Развязки

На основании ${\textit {If}}$ функции, легко определить логические узлы. Например, определение $And={\textit {If}}\circ (P_{1}^{2},P_{2}^{2},C_{0}^{2})$, получается $And(x,y)={\textit {If}}(x,y,0)$, то есть, $And(x,y)$ истинно тогда и только тогда , когда оба $x$ и $y$ истинны ( логическое соединение $x$ и $y$).

Сходным образом, $Or={\textit {If}}\circ (P_{1}^{2},C_{1}^{2},P_{2}^{2})$ и $Not={\textit {If}}\circ (P_{1}^{1},C_{0}^{1},C_{1}^{1})$ приводят к соответствующим определениям дизъюнкции и отрицания : $Or(x,y)={\textit {If}}(x,1,y)$ и $Not(x)={\textit {If}}(x,0,1)$.

Предикат равенства

Использование вышеуказанных функций $Leq$, $Geq$ и $And$, определение $Eq=And\circ (Leq,Geq)$ реализует предикат равенства. Фактически, $Eq(x,y)=And(Leq(x,y),Geq(x,y))$ истинно тогда и только тогда, когда $x$ равно $y$.

Аналогично, определение $Lt=Not\circ Geq$ реализует предикат «меньше чем», и $Gt=Not\circ Leq$ реализует «больше чем».

Другие операции с натуральными числами

Возведение в степень и проверка простоты являются примитивно-рекурсивными. Даны примитивно-рекурсивные функции $e$, $f$, $g$, и $h$, функция, которая возвращает значение $g$ когда $e\leq f$ и ценность $h$ в противном случае является примитивно-рекурсивным.

Операции с целыми и рациональными числами

Используя нумерацию Гёделя , примитивно-рекурсивные функции могут быть расширены для работы с другими объектами, такими как целые и рациональные числа . Если целые числа кодируются числами Гёделя стандартным способом, все арифметические операции, включая сложение, вычитание и умножение, являются примитивно-рекурсивными. Аналогично, если рациональные числа представлены числами Гёделя, то все полевые операции являются примитивно-рекурсивными.

Некоторые распространенные примитивно-рекурсивные функции

Следующие примеры и определения взяты из работы Клини (1952), стр. 223–231. Многие появляются с доказательствами. Большинство из них также появляются под похожими именами либо в качестве доказательств, либо в качестве примеров в Boolos-Burgess-Jeffrey 2002, стр. 63–70; они добавляют логарифм lo(x, y) или lg(x, y) в зависимости от точного вывода.

В дальнейшем знак " ' ", например a', является примитивным знаком, означающим "преемник", обычно обозначаемым как "+1", например a +1 = _def a'. Функции 16–20 и #G представляют особый интерес с точки зрения преобразования примитивно-рекурсивных предикатов в их «арифметическую» форму, выраженную в виде чисел Гёделя , и их извлечения из нее .

1. Дополнение: а+б
2. Умножение: a×b
3. Возведение в степень: а ^б
4. Факториал а! : 0! = 1, а'! = а!×а'
5. pred(a): (предшественник или декремент): если a > 0, то a−1, иначе 0
6. Правильное вычитание a ∸ b: если a ≥ b, то a−b иначе 0
7. Минимум (a ₁ , ... a _n )
8. Максимум(a ₁ , ... a _n )
9. Абсолютная разница: | а-б | = _def (а ∸ b) + (b ∸ а)
10. ~sg(a): NOT[signum(a)]: Если a=0, то 1, иначе 0
11. sg(a): Signum(a): Если a=0, то 0, иначе 1
12. а | b: (a делит b): если b=k×a для некоторого k, то 0 иначе 1
13. Остаток(a, b): остаток, если b не делит a «на поровну». Также называется MOD(a, b)
14. а = б: сг | а - б | (Соглашение Клини заключалось в том, чтобы представлять истинное значение 0 и ложное значение 1; в настоящее время, особенно в компьютерах, наиболее распространенным соглашением является обратное, а именно представлять истинное значение 1 и ложное значение 0, что равнозначно замене sg на ~sg здесь и в следующий пункт)
15. а < б: sg( а' ∸ б)
16. Pr(a): a — простое число Pr(a) = _def a>1 & NOT(Существует c) _1<c<a [c|a]
17. p _i : i+1-е простое число
18. (a) _i : показатель степени pi _в a: уникальный x такой, что _pi ^х |a & NOT(p _i ^х' |а)
19. lh(a): «длина» или количество ненулевых показателей степени в
20. lo(a, b): (логарифм от a по основанию b): если a, b > 1, то наибольший x такой, что b ^х | еще 0

Далее сокращение x = _def x ₁ , ... x _n ; индексы могут применяться, если этого требует смысл.

• #A: Функция φ, определяемая явно из функций Ψ и констант q ₁ , ... q _n, является примитивно-рекурсивной в Ψ.
• #B: Конечная сумма Σ _y<z ψ( x , y) и произведение Π _y<z ψ( x , y) примитивно рекурсивны по ψ.
• #C: Предикат P, полученный заменой функций χ ₁ ,..., χ _m на соответствующие переменные предиката Q, примитивно рекурсивен в χ ₁ ,..., χ _m , Q.
• #D: Следующие предикаты примитивно рекурсивны в Q и R:

• НЕ_Q( х ) .
• Q ИЛИ R: Q( x ) VR( x ),
• Q И R: Q( x ) и R( x ),
• Q ПРЕДЛАГАЕТ R: Q( x ) → R( x )
• Q эквивалентен R: Q( x ) ≡ R( x )

• #E: Следующие предикаты примитивно рекурсивны в предикате R:

• (Ey) _y<z R( x , y), где (Ey) _y<z означает «существует хотя бы один y, который меньше z такой, что»
• (y) _y<z R( x , y), где (y) _y<z означает «для всех y меньше z верно, что»
• µy _y<z R( x , y). Оператор µy _y<z R( x , y) представляет собой ограниченную форму так называемого оператора минимизации или mu : определяется как «наименьшее значение y меньше z такое, что R( x , y) истинно; или z, если такого значения нет».

• #F: Определение по случаям: функция, определенная таким образом, где Q ₁ , ..., Q _m являются взаимоисключающими предикатами (или «ψ( x ) должна иметь значение, заданное первым применимым предложением), является примитивно-рекурсивной в φ ₁ , ..., Q ₁ , ... Q _м :

φ( Икс ) =

• φ ₁ ( x ), если Q ₁ ( x ) истинно,
• . . . . . . . . . . . . . . . . . . .
• φ _m ( x ), если Q _m ( x ) верно
• φ _m+1 ( x ) в противном случае

• #G: Если φ удовлетворяет уравнению:

φ(y, x ) = χ(y, COURSE-φ(y; x ₂ , ... x _n ), x ₂ , ... x _n, то φ примитивно рекурсивно по χ. Значение COURSE-φ(y ; x _{2 to n} ) функции хода значений кодирует последовательность значений φ(0, x _{2 to n} ), ..., φ(y-1, x _{2 to n} ) исходной функции.

Связь с рекурсивными функциями

Более широкий класс частично рекурсивных функций определяется введением оператора неограниченного поиска . Использование этого оператора может привести к созданию частичной функции , то есть отношения, имеющего не более одного значения для каждого аргумента, но не обязательно имеющего какое-либо значение для любого аргумента (см. Домен ). Эквивалентное определение гласит, что частично рекурсивная функция — это функция, которую можно вычислить с помощью машины Тьюринга . Полнорекурсивная функция — это частично рекурсивная функция, определенная для каждого входа.

Любая примитивно-рекурсивная функция является тотально рекурсивной, но не все тотальные рекурсивные функции являются примитивно-рекурсивными. Функция Аккермана A ( m , n ) является хорошо известным примером тотально рекурсивной функции (фактически доказуемой тотальной), которая не является примитивно-рекурсивной. Примитивно-рекурсивные функции характеризуются как подмножество тотально-рекурсивных функций с помощью функции Аккермана. Эта характеристика утверждает, что функция является примитивно-рекурсивной тогда и только тогда, когда существует натуральное число m такое, что функция может быть вычислена машиной Тьюринга, которая всегда останавливается в течение A( m , n ) или меньшего количества шагов, где n — сумма аргументы примитивно-рекурсивной функции.

Важным свойством примитивно-рекурсивных функций является то, что они представляют собой рекурсивно перечислимое подмножество множества всех тотально рекурсивных функций (которое само по себе не является рекурсивно перечислимым). Это означает, что существует единственная вычислимая функция f ( m , n ), которая перечисляет примитивно-рекурсивные функции, а именно:

• Для каждой примитивно-рекурсивной функции g существует m такое, что g ( n ) = f ( m , n ) для всех n , и
• Для каждого m функция h ( n ) = f ( m , n ) является примитивно-рекурсивной.

f может быть явно сконструировано путем итеративного повторения всех возможных способов создания примитивно-рекурсивных функций. Таким образом, оно доказуемо тотально. Можно использовать аргумент диагонализации , чтобы показать, что f сам по себе не является рекурсивным примитивом: если бы он был таковым, то было бы и h ( n ) = f ( n , n )+1. Но если это соответствует некоторой примитивно-рекурсивной функции, существует m такое, что h ( n ) = f ( m , n ) для всех n , и тогда h ( m ) = f ( m , m ), что приводит к противоречию.

Однако набор примитивно-рекурсивных функций не является самым большим рекурсивно перечислимым подмножеством множества всех тотально рекурсивных функций. Например, набор доказуемо полных функций (в арифметике Пеано) также рекурсивно перечислим, поскольку можно перечислить все доказательства теории. Хотя все примитивно-рекурсивные функции доказуемо тотальны, обратное неверно.

Ограничения

Примитивно-рекурсивные функции, как правило, очень близко соответствуют нашему интуитивному пониманию того, какой должна быть вычислимая функция. Конечно, исходные функции интуитивно вычислимы (в силу своей простоты), и две операции, с помощью которых можно создавать новые примитивно-рекурсивные функции, также очень просты. Однако набор примитивно-рекурсивных функций не включает в себя все возможные тотальные вычислимые функции — в этом можно убедиться с помощью варианта диагонального аргумента Кантора . Этот аргумент предоставляет полностью вычислимую функцию, которая не является примитивно-рекурсивной. Схема доказательства такова:

Примитивно-рекурсивные функции одного аргумента (т. е. унарные функции) могут быть вычислимо перечислены . В этом перечислении используются определения примитивно-рекурсивных функций (которые, по сути, представляют собой просто выражения с операциями композиции и примитивной рекурсии в качестве операторов, а базовые примитивно-рекурсивные функции — в виде атомов), и можно предположить, что оно содержит каждое определение один раз, даже если одна и та же функция будет встречаться в списке много раз (поскольку многие определения определяют одну и ту же функцию; действительно, простое составление с помощью тождественной функции генерирует бесконечное количество определений любой одной примитивно-рекурсивной функции). Это означает, что $n$-е определение примитивно-рекурсивной функции в этом перечислении можно эффективно определить из $n$. Действительно, если использовать некоторую нумерацию Гёделя для кодирования определений в виде чисел, то это $n$-е определение в списке вычисляется примитивно-рекурсивной функцией $n$. Позволять $f_{n}$ обозначают унарную примитивно-рекурсивную функцию, заданную этим определением.

Теперь определите «функцию оценщика» $ev$ с двумя аргументами, по $ev(i,j)=f_{i}(j)$. Четко $ev$ является тотальным и вычислимым, поскольку можно эффективно определить определение $f_{i}$и являясь примитивно-рекурсивной функцией $f_{i}$ само по себе тотально и вычислимо, поэтому $f_{i}(j)$ всегда определена и эффективно вычислима. Однако диагональный аргумент покажет, что функция $ev$ двух аргументов не является примитивно-рекурсивным.

Предполагать $ev$ были примитивно-рекурсивными, то унарная функция $g$ определяется $g(i)=S(ev(i,i))$ также будет примитивно-рекурсивным, поскольку он определяется композицией из функции-преемника и $ev$. Но тогда $g$ встречается в перечислении, поэтому существует некоторое число $n$ такой, что $g=f_{n}$. Но сейчас $g(n)=S(ev(n,n))=S(f_{n}(n))=S(g(n))$ дает противоречие.

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

Известны и другие примеры тотально рекурсивных, но не примитивно рекурсивных функций:

• Функция, которая переводит m в Аккерман ( m , m ), является унарной полностью рекурсивной функцией, которая не является примитивно-рекурсивной.
• Теорема Пэрис-Харрингтона включает в себя полностью рекурсивную функцию, которая не является примитивно-рекурсивной.
• Судана Функция
• Функция Гудштейна

Варианты

Постоянные функции

Вместо $C_{n}^{k}$,альтернативные определения используют только одну 0-арную нулевую функцию $C_{0}^{0}$ как примитивную функцию, которая всегда возвращает ноль, и построила константные функции из нулевой функции, функции-преемника и оператора композиции.

Слабая примитивная рекурсия

Функция-предшественник с 1 местом является примитивно-рекурсивной, см. раздел #Predecessor . Фишер, Фишер и Бейгель удалил неявный предшественник из правила рекурсии, заменив его более слабым правилом

${\begin{array}{lcl}f(0,x_{1},\ldots ,x_{k})&=&g(x_{1},\ldots ,x_{k})&{\text{and}}\\f(S(y),x_{1},\ldots ,x_{k})&=&h(S(y),f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\end{array}}$

Они доказали, что функция-предшественница все еще может быть определена, и, следовательно, «слабая» примитивная рекурсия также определяет примитивно-рекурсивные функции.

Итерационные функции

Ослабление этого еще больше с помощью функций $h$ арности k +1, удаляя $y$ и $S(y)$ из аргументов $h$ полностью, мы получаем правило итерации :

${\begin{array}{lcll}f(0,x_{1},\ldots ,x_{k})&=&g(x_{1},\ldots ,x_{k})&{\textrm {and}}\\f(S(y),x_{1},\ldots ,x_{k})&=&h(f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\end{array}}$

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

Дополнительные примитивно-рекурсивные формы

Некоторые дополнительные формы рекурсии также определяют функции, которые на самом деле являютсяпримитивно-рекурсивный. Определения в этих формах может быть легче найти илиболее естественно для чтения или письма. Рекурсия курса значений определяет примитивные рекурсивные функции. Некоторые формы взаимной рекурсии также определяют примитивно-рекурсивные функции.

Функции, которые можно запрограммировать на языке программирования LOOP, представляют собой именно примитивно-рекурсивные функции. Это дает разную характеристику мощности этих функций. Основное ограничение языка LOOP по сравнению с языком, полным по Тьюрингу , заключается в том, что в языке LOOP количество раз, которое будет выполняться каждый цикл, указывается до того, как цикл начнет выполняться.

Определение компьютерного языка

Примером примитивно-рекурсивного языка программирования является язык, который содержит основные арифметические операторы (например, + и - или ДОБАВИТЬ и ВЫЧИТАТЬ), условные выражения и сравнения (ЕСЛИ-ТО, РАВНО, МЕНЬШЕ-ЧЕМ) и ограниченные циклы, такие как базовый for цикл , где существует известная или вычислимая верхняя граница для всех циклов (FOR i FROM 1 TO n, при этом ни i, ни n не могут быть изменены телом цикла). Никакие управляющие структуры большей общности, такие как циклы while или IF-THEN плюс GOTO , не допускаются в примитивно-рекурсивном языке.

Язык LOOP , представленный в 1967 году в статье Альберта Р. Мейера и Денниса М. Ритчи , это такой язык. Его вычислительная мощность совпадает с примитивно-рекурсивными функциями. Вариантом языка LOOP является Дугласа Хофштадтера в BlooP произведениях Гёделя, Эшера, Баха . Добавление неограниченных циклов (WHILE, GOTO) делает язык общерекурсивным и полным по Тьюрингу , как и все реальные языки компьютерного программирования.

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

Финитизм и результаты согласованности

Примитивные рекурсивные функции тесно связаны с математическим финитизмом и используются в нескольких контекстах математической логики, где требуется особенно конструктивная система. Для этой цели часто используется примитивно-рекурсивная арифметика (PRA), формальная система аксиом для натуральных чисел и примитивно-рекурсивных функций над ними.

PRA намного слабее арифметики Пеано , которая не является финитистской системой. Тем не менее, многие результаты в теории чисел и теории доказательств можно доказать с помощью PRA. Например, теорема Гёделя о неполноте может быть формализована в PRA, давая следующую теорему:

Если T — теория арифметики, удовлетворяющая определенным гипотезам, с предложением Гёделя G _T , то PRA доказывает импликацию Con( T )→ G _T .

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

В теории доказательств и теории множеств существует интерес к финитистским доказательствам непротиворечивости , то есть доказательствам непротиворечивости, которые сами по себе финитистски приемлемы. Такое доказательство устанавливает, что непротиворечивость теории T подразумевает непротиворечивость теории S путем создания примитивно-рекурсивной функции, которая может преобразовать любое доказательство несовместимости из S в доказательство несогласованности из T . Одним из достаточных условий для того, чтобы доказательство непротиворечивости было финитистским, является возможность формализовать его в PRA. Например, многие результаты о непротиворечивости в теории множеств, полученные путем принуждения, можно преобразовать в синтаксические доказательства, которые можно формализовать в PRA.

История

Рекурсивные определения и раньше использовались в математике более или менее формально, но построение примитивной рекурсии восходит к Ричарда Дедекинда теореме 126 из его книги «Was sind und was sollen die Zahlen?» (1888). Эта работа была первой, в которой было доказано, что некоторая рекурсивная конструкция определяет уникальную функцию.

Примитивную рекурсивную арифметику впервые предложил Торальф Скулем. в 1923 году.

Нынешняя терминология была придумана Рожа Петером (1934) после того, как Акерман в 1928 году доказал, что функция, которая сегодня названа в его честь, не была примитивно-рекурсивной, и это событие вызвало необходимость переименовать то, что до этого называлось просто рекурсивными функциями.

См. также

• Иерарх Гжегорчик
• Рекурсия (информатика)
• Примитивный рекурсивный функционал
• Двойная рекурсия
• Примитивная рекурсивная функция множества
• Примитивная рекурсивная порядковая функция
• Хвостовой вызов

Ссылки

• Брейнерд, В.С., Ландвебер, Л.Х. (1974), Теория вычислений , Уайли, ISBN   0-471-09585-0
• Фишер, Майкл Дж.; Фишер, Роберт П.; Бейгель, Ричард (ноябрь 1989 г.). «Примитивная рекурсия без неявного предшественника» . Новости ACM SIGACT . 20 (4): 87–91. дои : 10.1145/74074.74089 . S2CID   33850327 .
• Юрис Хартманис (1989), «Обзор теории сложности вычислений» в книге Дж. Хартманиса (ред.), Теория сложности вычислений, Провиденс: Американское математическое общество, стр. 1–17.
• Роберт И. Соаре , Рекурсивно перечислимые множества и степени , Springer-Verlag, 1987. ISBN   0-387-15299-7
• Стивен Клини (1952) Введение в метаматематику , издательство North-Holland Publishing Company, Нью-Йорк, 11-е переиздание 1971 г.: (примечания ко 2-му изданию добавлены к 6-му переизданию). В главе XI. Общие рекурсивные функции §57
• Джордж Булос , Джон Берджесс , Ричард Джеффри (2002), Вычислимость и логика: четвертое издание , издательство Кембриджского университета, Кембридж, Великобритания. См. стр. 70–71.
• Роберт И. Соаре, 1995 г. Вычислимость и рекурсия http://www.people.cs.uchicago.edu/~soare/History/compute.pdf
• Дэниел Северин 2008, Унарные примитивно-рекурсивные функции , J. Символическая логика, том 73, выпуск 4, стр. 1122–1138 arXiv projecteuclid doi : 10.2178/jsl/1230396909 JSTOR   275903221