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

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

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

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

Определение [ править ]

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

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

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

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

Оператор композиции $\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})).$
Примитивный оператор рекурсии $ρ$ : Учитывая 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 ₁ , ..., 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}^{1}$ можно выразить как композицию достаточного количества $S$ и $C_{0}^{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 для ложи), или которые создают значения истинности в качестве выходных данных. ^[3]Этого можно достичь путем идентификации значений истинности с числами любым фиксированным способом. Например, обычно значение истинности 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 ≤ 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 представляют особый интерес с точки зрения преобразования примитивно-рекурсивных предикатов в их «арифметическую» форму, выраженную как числа Гёделя , и их извлечения из нее .

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

Важным свойством примитивно-рекурсивных функций является то, что они представляют собой рекурсивно перечислимое подмножество множества всех тотально рекурсивных функций (которое само по себе не является рекурсивно перечислимым). Это означает, что существует единственная вычислимая функция 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$ с двумя аргументами: $(i, j) = fi j (ev)$ . Очевидно, $ev$ является полным и вычислимым, поскольку можно эффективно определить определение $f i$ , а будучи примитивно-рекурсивной функцией, $f i$ сама является полной и вычислимой, поэтому $fi что (j)$ всегда определена и эффективно вычислима. Однако диагональный аргумент покажет, что функция $ev$ двух аргументов не является примитивно-рекурсивной.

Предположим,

что ev

примитивно рекурсивны, тогда унарная функция

g,

определенная формулой

g (i) = S(ev (i, i))

также будет примитивно рекурсивной, поскольку она определяется композицией из функции-последователя и

ev

. Но тогда

в перечислении встречается g

, поэтому существует некоторое число

n

такое, что

g = f n

. Но теперь

g (n) = S(ev (n, n)) = S(fn (n)) = S(g (n))

дает противоречие.

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

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

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

Варианты [ править ]

Постоянные функции [ править ]

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

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

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

{\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}}$

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

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

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

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

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

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

Язык LOOP , представленный в 1967 году в статье Альберта Р. Мейера и Денниса М. Ритчи , ^[6]это такой язык. Его вычислительная мощность совпадает с примитивно-рекурсивными функциями. Вариантом языка 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). Эта работа была первой, в которой было доказано, что некоторая рекурсивная конструкция определяет уникальную функцию. ^[7]^[8]^[9]

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

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

См. также [ править ]

Примечания [ править ]

^ Брейнерд и Ландвебер, 1974 г.
^ Хартман, 1989.
^ Клини [1952, стр. 226–227]
^ Это следует из того факта, что функции этой формы являются наиболее быстро растущими примитивно-рекурсивными функциями и что функция является примитивно-рекурсивной тогда и только тогда, когда ее временная сложность ограничена примитивно-рекурсивной функцией. О первом см. Линц, Питер (2011), Введение в формальные языки и автоматы , Jones & Bartlett Publishers, стр. 332, ISBN 9781449615529 . О последнем см. Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений , Oxford University Press, стр. 287, ISBN 9780191620805
^ Перейти обратно: ^а ^б Фишер, Фишер и Бейгель, 1989 .
^ Мейер, Альберт Р .; Ричи, Деннис М. (1967). Сложность циклических программ . ACM '67: Материалы 22-й национальной конференции 1967 года. дои : 10.1145/800196.806014 .
^ Питер Смит (2013). Введение в теоремы Гёделя (2-е изд.). Издательство Кембриджского университета. стр. 100-1 98–99. ISBN 978-1-107-02284-3 .
^ Перейти обратно: ^а ^б Джордж Турлакис (2003). Лекции по логике и теории множеств: Том 1, Математическая логика . Издательство Кембриджского университета. п. 129. ИСБН 978-1-139-43942-8 .
^ Перейти обратно: ^а ^б Род Дауни, изд. (2014). Наследие Тьюринга: развитие идей Тьюринга в логике . Издательство Кембриджского университета. п. 474. ИСБН 978-1-107-04348-0 .
^ Торальф Скулем (1923) «Основы элементарной арифметики» Жана ван Хейеноорта , переводчика и изд. (1967) От Фреге до Гёделя: Справочник по математической логике, 1879–1931 . Гарвардский университет. Пресса: 302-33.

Ссылки [ править ]

Брейнерд, В.С., Ландвебер, Л.Х. (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

[1] Брейнерд и Ландвебер, 1974 г.

[2] Хартман, 1989.

[3] Клини [1952, стр. 226–227]

[4] Это следует из того факта, что функции этой формы являются наиболее быстро растущими примитивно-рекурсивными функциями и что функция является примитивно-рекурсивной тогда и только тогда, когда ее временная сложность ограничена примитивно-рекурсивной функцией. О первом см. Линц, Питер (2011), Введение в формальные языки и автоматы , Jones & Bartlett Publishers, стр. 332, ISBN 9781449615529 . О последнем см. Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений , Oxford University Press, стр. 287, ISBN 9780191620805

[FOOTNOTEFischerFischerBeigel1989-5] Перейти обратно: ^а ^б Фишер, Фишер и Бейгель, 1989 .

[6] Мейер, Альберт Р .; Ричи, Деннис М. (1967). Сложность циклических программ . ACM '67: Материалы 22-й национальной конференции 1967 года. дои : 10.1145/800196.806014 .

[Smith2013-7] Питер Смит (2013). Введение в теоремы Гёделя (2-е изд.). Издательство Кембриджского университета. стр. 100-1 98–99. ISBN 978-1-107-02284-3 .

[Tourlakis2003-8] Перейти обратно: ^а ^б Джордж Турлакис (2003). Лекции по логике и теории множеств: Том 1, Математическая логика . Издательство Кембриджского университета. п. 129. ИСБН 978-1-139-43942-8 .

[Downey2014-9] Перейти обратно: ^а ^б Род Дауни, изд. (2014). Наследие Тьюринга: развитие идей Тьюринга в логике . Издательство Кембриджского университета. п. 474. ИСБН 978-1-107-04348-0 .

[10] Торальф Скулем (1923) «Основы элементарной арифметики» Жана ван Хейеноорта , переводчика и изд. (1967) От Фреге до Гёделя: Справочник по математической логике, 1879–1931 . Гарвардский университет. Пресса: 302-33.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]