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

Функция, вычислимая с ограниченными циклами

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

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

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

Определение

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

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

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

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

4. Оператор композиции (также называемый оператором подстановки ): Дана m -ичная функция и m k -ичных функций : Для получается обычная композиция функций . ${\displaystyle \circ \,}$ ${\displaystyle h(x_{1},\ldots ,x_{m})\,}$ ${\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}$ $${\displaystyle 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})).}$$ ${\displaystyle m=1}$ ${\displaystyle h\circ g_{1}}$
5. Примитивный оператор рекурсии : Даны k -арная функция и ( k  + 2)-арная функция : ${\displaystyle \rho }$ ${\displaystyle g(x_{1},\ldots ,x_{k})\,}$ ${\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}$ $${\displaystyle {\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}}}$$

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

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

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

Примеры

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

Добавление

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

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

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

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

Удвоение

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

Умножение

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

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

и

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

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

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

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

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

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

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

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

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

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

В некоторых ситуациях естественно рассматривать примитивные рекурсивные функции, которые принимают в качестве входных данных кортежи, которые смешивают числа со значениями истинности (то есть для true и для false), или которые производят значения истинности в качестве выходных данных. ^[4] Это может быть достигнуто путем идентификации значений истинности с числами любым фиксированным способом. Например, обычно значение истинности идентифицируется с числом , а значение истинности — с числом . После того, как эта идентификация сделана, характеристическая функция множества , которая всегда возвращает или , может рассматриваться как предикат, который сообщает, находится ли число в множестве . Такая идентификация предикатов с числовыми функциями будет предполагаться в оставшейся части этой статьи. ${\displaystyle t}$ ${\displaystyle f}$ ${\displaystyle t}$ ${\displaystyle 1}$ ${\displaystyle f}$ ${\displaystyle 0}$ ${\displaystyle A}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle A}$

Предикат «Равно нулю»

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

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

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

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

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

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

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

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

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

и

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

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

Соединители

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

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

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

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

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

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

Возведение в степень и проверка простоты являются примитивно рекурсивными. При наличии примитивно рекурсивных функций , , , и , функция, которая возвращает значение when и значение otherwise, является примитивно рекурсивной. ${\displaystyle e}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle h}$ ${\displaystyle g}$ ${\displaystyle e\leq f}$ ${\displaystyle h}$

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

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

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

Следующие примеры и определения взяты из Kleene (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. Умножение: а×b
3. Возведение в степень: a ^b
4. Факториал a! : 0! = 1, a'! = a!×a'
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. Абсолютная разность: | a−b | = _def (a ∸ b) + (b ∸ a)
10. ~sg(a): НЕ[signum(a)]: Если a=0, то 1, иначе 0
11. sg(a): signum(a): Если a=0, то 0, иначе 1
12. a | b: (a делит b): Если b=k×a для некоторого k, то 0, иначе 1
13. Остаток(a, b): остаток, если b не делит a "нацело". Также называется MOD(a, b)
14. a = b: sg | a − b | (Соглашение Клини состояло в том, чтобы представлять истину как 0, а ложь как 1; в настоящее время, особенно в компьютерах, наиболее распространенным соглашением является обратное, а именно представлять истину как 1, а ложь как 0, что равносильно замене sg на ~sg здесь и в следующем пункте)
15. а < б: sg( а' ∸ б )
16. Pr(a): a — простое число Pr(a) = _def a>1 & NOT(Exists c) _1<c<a [ c|a ]
17. p _i : i+1-е простое число
18. (a) _i : показатель степени p _i в a: уникальный x такой, что p _i ^x |a & NOT(p _i ^x' |a)
19. lh(a): «длина» или число неисчезающих показателей степеней в
20. lo(a, b): (логарифм a по основанию b): Если a, b > 1, то наибольшее x такое, что b ^x | a иначе 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( x ) .
• Q ИЛИ R: Q( x ) VR( 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) является ограниченной формой так называемого минимизирующего или мю-оператора : определяется как «наименьшее значение y, меньшее z, такое, что R( x , y) является истинным; или z, если такого значения нет».

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

φ( х ) =

• φ ₁ ( 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 — сумма аргументов примитивно-рекурсивной функции. ^[5]

Важным свойством примитивных рекурсивных функций является то, что они являются рекурсивно перечислимым подмножеством множества всех полных рекурсивных функций (которое само по себе не является рекурсивно перечислимым). Это означает, что существует единственная вычислимая функция 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 ), что приводит к противоречию.

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

Ограничения

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

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

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

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

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

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

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

Варианты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примером примитивного рекурсивного языка программирования является язык, содержащий основные арифметические операторы (например, + и −, или ADD и SUBTRACT), условные операторы и операторы сравнения (IF-THEN, EQUALS, LESS-THAN) и ограниченные циклы, такие как базовый цикл for , где есть известная или вычисляемая верхняя граница для всех циклов (FOR i FROM 1 TO n, при этом ни i, ни n не могут быть изменены телом цикла). В примитивном рекурсивном языке не допускаются управляющие структуры большей общности, такие как циклы while или IF-THEN plus GOTO .

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

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

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

Смотрите также

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

Примечания

1. Брейнерд и Ландвебер, 1974 г.
2. Хартманис, 1989
3. Например: Хенк Барендрегт (1990). «Функциональное программирование и лямбда-исчисление». Ян ван Леувен (ред.). Формальные модели и семантика . Справочник по теоретической информатике. Том. Б. Эльзевир. стр. 321–364. ISBN 0-444-88074-7.Здесь: 2.2.6 начальные функции , Опр.2.2.7 примитивная рекурсия , стр.331-332.
4. Клини [1952 стр. 226–227]
5. Это следует из фактов, что функции этой формы являются наиболее быстро растущими примитивно-рекурсивными функциями, и что функция является примитивно-рекурсивной тогда и только тогда, когда ее временная сложность ограничена примитивно-рекурсивной функцией. Для первого см. Linz, Peter (2011), An Introduction to Formal Languages ​​and Automata, Jones & Bartlett Publishers, стр. 332, ISBN 9781449615529. Для последнего см. Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений, Oxford University Press, стр. 287, ISBN 9780191620805
6. Фишер, Фишер и Бейгель 1989.
7. Мейер, Альберт Р.; Ритчи , Деннис М. (1967). Сложность циклических программ . ACM '67: Труды 22-й национальной конференции 1967 года. doi : 10.1145/800196.806014 .
8. Питер Смит (2013). Введение в теоремы Гёделя (2-е изд.). Cambridge University Press. С. 98–99. ISBN 978-1-107-02284-3.
9. Джордж Турлакис (2003). Лекции по логике и теории множеств: Том 1, Математическая логика . Cambridge University Press. стр. 129. ISBN 978-1-139-43942-8.
10. Rod Downey, ed. (2014). Наследие Тьюринга: Развитие идей Тьюринга в логике . Cambridge University Press. стр. 474. ISBN 978-1-107-04348-0.
11. Торальф Скулем (1923) «Основы элементарной арифметики» в книге Жана ван Хейеноорта , переводчика и редактора. (1967) От Фреге до Гёделя: Учебник по математической логике, 1879-1931 . Издательство Гарвардского университета: 302-33.

Ссылки

• Брейнерд, WS, Ландвебер, LH (1974), Теория вычислений , Wiley, 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), Вычислимость и логика: четвертое издание , Cambridge University Press, Кембридж, Великобритания. См. стр. 70–71.
• Роберт И. Соаре 1995 Вычислимость и рекурсия http://www.people.cs.uchicago.edu/~soare/History/compute.pdf
• Daniel Severin 2008, Унарные примитивные рекурсивные функции , J. Symbolic Logic Том 73, Выпуск 4, стр. 1122–1138 arXiv projecteuclid doi :10.2178/jsl/1230396909 JSTOR  275903221