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

Функция, которую можно вычислить с помощью циклов ограниченной длины

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

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

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

• 1 Определение
  • 1.1 Роль функций проекции
  • 1.2 Преобразование предикатов в числовые функции
  • 1.3 Определение компьютерного языка
• 2 Примеры
  • 2.1 Сложение
  • 2.2 Вычитание
  • 2.3 Другие операции с натуральными числами
  • 2.4 Операции с целыми и рациональными числами
• 3 Использование в арифметике Пеано первого порядка
• 4 Связь с рекурсивными функциями
• 5 Ограничения
• 6 Некоторые общие примитивно-рекурсивные функции
• 7 Дополнительные примитивные рекурсивные формы
• 8 Конечность и согласованность результатов
• 9 История
• 10 См. Также
• 11 Примечания
• 12 Ссылки

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

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

1. Постоянная функция : 0-арный постоянная функция 0 является примитивно рекурсивной.
2. функция-последователь : 1-арная функция-преемник S, которая возвращает преемника своего аргумента (см. постулаты Пеано ), является примитивно-рекурсивной. То есть S (k) = k + 1.
3. Функция проекции : для каждого n≥1 и каждого i с 1≤i≤n n-арная функция проекции P i, который возвращает свой i-й аргумент, является примитивно рекурсивным.

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

4. Состав : задано k -арная примитивно-рекурсивная функция f, и k многие m-арные примитивно-рекурсивные функции g 1,..., g k, композиция f с g 1,..., g k, т.е. m-арная функция $h\; (x\; 1,\dots ,\; xm)\; =\; f\; (g\; 1\; (x\; 1,\dots ,\; xm),\dots ,\; gk\; (x\; 1,\dots ,\; xm))\; \{\backslash \; displaystyle\; h\; (x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{m\})\; =\; f\; (g\_\; \{1\}\; (x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{m\}),\; \backslash \; ldots,\; g\_\; \{k\}\; (x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{m\}))\; \backslash ,\}$примитивно рекурсивно.

Пример. Возьмем f (x) в качестве S (x), определенного выше. Это f - одномерная примитивно рекурсивная функция. И так g (x) = S (x). Таким образом, h (x), определенный как f (g (x)) = S (S (x)), также является примитивной рекурсивной одномерной функцией. Неформально говоря, h (x) - это функция, которая превращает x в x + 2.

5. Примитивная рекурсия : Для заданной f, k-арной примитивной рекурсивной функции и g, (k + 2) -арной примитивной рекурсивной функции, (k + 1) -арная функция h определяется как примитивная рекурсия f и g, т.е. функция h примитивно рекурсивна, когда

   $h\; (0,\; x\; 1,\dots ,\; xk)\; =\; f\; (x\; 1,\dots ,\; xk)\; \{\backslash \; displaystyle\; h\; (0,\; x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{k\})\; =\; f\; (x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{k\})\; \backslash ,\}$и

   $h\; (S\; (y),\; x\; 1,\dots ,\; xk)\; =\; g\; (y,\; h\; (y,\; x\; 1,\dots ,\; xk),\; x\; 1,\dots ,\; xk).\; \{\backslash \; Displaystyle\; час\; (S\; (y),\; x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{k\})\; =\; g\; (y,\; h\; (y,\; x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{k\}),\; x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{k\})\; \backslash ,.\}$

Пример. Предположим, что f (x) = P 1 (x) = x и g (x, y, z) = S (P 2 (x, y, z)) = S ( у). Тогда h (0, x) = x и h (S (y), x) = g (y, h (y, x), x) = S (h (y, x)). Теперь h (0,1) = 1, h (1,1) = S (h (0,1)) = 2, h (2,1) = S (h (1,1)) = 3. Это h 2-арная примитивная рекурсивная функция. Мы можем назвать это «сложением».

Интерпретация. Функция h действует как для цикла от 0 до значения его первого аргумента. Остальные аргументы для h, обозначенные здесь как x i (i = 1,..., k), представляют собой набор начальных условий для цикла For, которые могут использоваться им во время расчеты, но которые им неизменны. Функции f и g в правой части уравнений, определяющих h, представляют собой тело цикла, который выполняет вычисления. Функция f используется только один раз для выполнения начальных вычислений. Расчеты для последующих шагов цикла выполняет g. Первому параметру g передается «текущее» значение индекса цикла For. Второй параметр g получает результат предыдущих вычислений цикла For из предыдущих шагов. Остальные параметры для g - это те неизменные начальные условия для цикла For, упомянутые ранее. Они могут использоваться g для выполнения вычислений, но сами они не будут изменены g.

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

Роль функций проекции

Функции проекции можно использовать, чтобы избежать очевидной жесткости с точки зрения арности функций, указанных выше; Используя композиции с различными функциями проекции, можно передать подмножество аргументов одной функции другой функции. Например, если g и h - двумерные примитивные рекурсивные функции, то

$f\; (a,\; b,\; c)\; =\; g\; (h\; (c,\; a),\; h\; (a,\; b))\; \{\backslash \; displaystyle\; f\; (a,\; b,\; c)\; =\; g\; (h\; (c,\; a),\; h\; (a,\; b))\; \backslash !\}$

также примитивно рекурсивно. Одно формальное определение с использованием функций проекции:

$f\; (a,\; b,\; c)\; =\; g\; (h\; (P\; 3\; 3\; (a,\; b,\; c),\; P\; 1\; 3\; (a,\; b,\; c)),\; h\; (P\; 1\; 3\; (а,\; б,\; в),\; П\; 2\; 3\; (а,\; б,\; в))).\; \{\backslash \; displaystyle\; f\; (a,\; b,\; c)\; =\; g\; (час\; (P\_\; \{3\}\; ^\; \{3\}\; (a,\; b,\; c),\; P\_\; \{1\}\; ^\; \{3\}\; (a,\; b,\; c)),\; час\; (P\_\; \{1\}\; ^\; \{3\}\; (a,\; b,\; c),\; P\_\; \{2\}\; ^\; \{3\}\; (a,\; b,\; c))).\}$

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

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

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

Примером примитивного рекурсивного языка программирования является язык, содержащий базовые арифметические операторы (например, + и - или ADD и SUBTRACT), условные выражения и сравнение (IF-THEN, EQUALS, LESS-THAN), и ограниченные циклы, такие как базовый для цикла, где есть известная или вычисляемая верхняя граница для всех циклов (FOR i FROM 1 TO n, без изменения i и n телом петли). Никакие управляющие структуры большей общности, такие как циклы while или IF-THEN плюс GOTO, не допускаются в примитивно-рекурсивном языке. Дуглас Хофштадтер BlooP в Гёдель, Эшер, Бах - такой язык. Добавление неограниченных циклов (WHILE, GOTO) делает язык частично рекурсивным или полным по Тьюрингу ; Примером может служить Floop, как и почти все реальные языки компьютерного программирования.

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

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

Сложение

Интуитивно сложение может быть определено рекурсивно с помощью правил:

$add\; (0,\; x)\; =\; x\; \{\backslash \; displaystyle\; add\; (0,\; x)\; =\; x\}$,

$add\; (n\; +\; 1,\; x)\; =\; add\; (n,\; x)\; +\; 1\; \{\backslash \; displaystyle\; add\; (n\; +\; 1,\; x)\; =\; add\; (n,\; x)\; +1\}$

Чтобы вписать это в строго примитивно-рекурсивное определение, определите:

$add\; (0,\; x)\; =\; P\; 1\; 1\; (x),\; \{\backslash \; displaystyle\; add\; (0,\; x)\; =\; P\_\; \{1\}\; ^\; \{1\}\; (x),\}$

$add\; (S\; (\; п),\; Икс)\; знак\; равно\; S\; (п\; 2\; 3\; (п,\; добавить\; (п,\; х),\; х))\; \{\backslash \; Displaystyle\; добавить\; (S\; (п),\; х)\; =\; S\; (P\_\; \{2\}\; ^\; \{3\}\; (п,\; add\; (n,\; x),\; x))\}$

Здесь S (n) - это «преемник n» (т. е. n + 1), P 1 - функция идентичности, а P 2 - это функция проекции , которая принимает 3 аргумента и возвращает второй. Функции f и g, требуемые приведенным выше определением операции примитивной рекурсии, соответственно воспроизводятся P 1 и композицией S и P 2.

Subtraction

Поскольку примитивные рекурсивные функции используют натуральные числа вместо целых чисел, и натуральные числа не замыкаются при вычитании, в этом контексте изучается функция усеченного вычитания (также называемая «правильным вычитанием»). Эта функция ограниченного вычитания sub (a, b) [или b ∸ a] возвращает b - a, если оно неотрицательно, и возвращает 0 в противном случае.

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

pred (0) = 0,

pred (n + 1) = n.

Эти правила можно преобразовать в более формальное определение с помощью примитивной рекурсии:

pred (0) = 0,

pred (S (n)) = P 1 (n, pred (n)).

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

sub (0, x) = P 1 (x),

sub (S (n), x) = pred (P 2 (n, sub (n, x), x)).

Здесь sub (a, b) соответствует b ∸ a; для простоты порядок аргументов был изменен с "стандартного" определения, чтобы соответствовать требованиям примитивной рекурсии. Это легко исправить с помощью композиции с подходящими выступами.

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

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

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

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

В арифметике Пеано первого порядка арифметике Пеано существует бесконечно много переменных (0-арных символов), но нет k-арный нелогические символы с k>0, кроме S, +, * и ≤. Таким образом, чтобы определить примитивные рекурсивные функции, нужно использовать следующий прием Гёделя.

Используя нумерацию Гёделя для последовательностей, например, β-функцию Гёделя, любую конечную последовательность чисел можно закодировать одним числом. Таким образом, такое число может представлять примитивно рекурсивную функцию до заданного n.

Пусть h будет однозначной примитивной функцией рекурсии, определенной следующим образом:

$h\; (0)\; =\; C\; \{\backslash \; displaystyle\; h\; (0)\; =\; C\}$

$h\; (n\; +\; 1)\; =\; g\; (\; n,\; час\; (n))\; \{\backslash \; displaystyle\; h\; (n\; +\; 1)\; =\; g\; (n,\; h\; (n))\}$

где C - константа, а g - уже определенная функция.

Используя β-функцию Гёделя, для любой последовательности натуральных чисел (k 0, k 1,…, k n) существуют натуральные числа b и c такие, что для любого i ≤ n β (b, c, i) = k i. Таким образом, мы можем использовать следующую формулу для определения h; более точно, m = h (n) является сокращением для следующего:

и приравнивание к g, будучи уже определенным, фактически является сокращением для некоторой другой уже определенной формулы (как и β, формула которого дана здесь ).

Обобщение на любую k-арную примитивную функцию рекурсии тривиально.

Более широкий класс частично рекурсивных функций определяется введением оператора неограниченного поиска. Использование этого оператора может привести к частичной функции, то есть к отношению не более чем с одним значением для каждого аргумента, но не обязательно имеет какое-либо значение для любого аргумента (см. домен ). Эквивалент В определении говорится, что частично рекурсивная функция - это функция, которая может быть вычислена с помощью машины Тьюринга. Полная рекурсивная функция - это частично рекурсивная функция, которая определена для каждого ввода. является полностью рекурсивным, но не все полностью рекурсивные функции являются примитивно рекурсивными. Функция Аккермана 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 на Ackermann (m, m), является унарной тотальной рекурсивной функцией, которая не является примитивной. рекурсивный.
• Теорема Париса – Харрингтона включает в себя тотально рекурсивную функцию, которая не является примитивно рекурсивной. Поскольку эта функция мотивирована теорией Рамсея, она иногда считается более «естественной», чем функция Аккермана.
• Функция Судана
• функция Гудштейна

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

Далее мы замечаем, что примитивные рекурсивные функции могут быть четырех типов:

1. для краткости функции: «число -теоретические функции "от {0, 1, 2,...} до {0, 1, 2,...},
2. предикатов: от {0, 1, 2,...} до значения истинности {t = true, f = false},
3. пропозициональные связки: от значений истинности {t, f} к значениям истинности {t, f},
4. , представляющие функции: от значений истинности {t, f} на {0, 1, 2,...}. Часто предикату требуется представляющая функция для преобразования вывода предиката {t, f} в {0, 1} (обратите внимание, что порядок «t» в «0» и «f» в «1» совпадает с определением ~ sg () ниже). По определению функция φ (x ) является «представляющей функцией» предиката P (x ), если φ принимает только значения 0 и 1 и производит 0, когда P истинно ».

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

1. Дополнение: a + b
2. Умножение: a × b
3. Возведение в степень: a
4. Факториал a!: 0! = 1, a '! = A! × a'
5. pred (a): (Предшественник или декремент): Если a>0, то a-1 else 0
6. Правильное вычитание a ∸ b: Если a ≥ b, то ab else 0
7. Минимум (a 1,... a n)
8. Максимум (a 1,... a n)
9. Абсолютная разница: | ab | = 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: (ad ivides b): если b = k × a для некоторого k, то 0 else 1
13. Остаток (a, b): остаток, если b не делит a «равномерно». Также называется MOD (a, b)
14. a = b: sg | а - б | (Соглашение Клини состояло в том, чтобы представлять истину через 0 и ложь через 1; в настоящее время, особенно в компьютерах, наиболее распространенным соглашением является обратное, а именно представлять истину через 1 и ложь через 0, что равносильно замене sg на ~ sg здесь и в следующий элемент)
15. a < b: sg( a' ∸ b)
16. Pr (a): a - простое число Pr (a) = def a>1 НЕ (существует c) 1
17. pi: i + 1-е простое число
18. (a) i : показатель степени p i в a: уникальный x такой, что p i | a NOT (p i | a)
19. lh (a): «длина» или количество ненулевых показателей в
20. lo (a, b): логарифм от a до основания b

Далее сокращение x=def x1,... x n ; индексы могут применяться, если того требует значение.

• #A: Функция φ, явно определяемая из функций Ψ и констант q 1,... q n, является примитивно рекурсивной в Ψ.
• #B: Конечная сумма Σ y
• #C: Предикат P, полученный заменой функции χ 1,..., χ m для соответствующих переменных предиката Q примитивно рекурсивны в χ 1,..., χ m, Q.
• #D: Следующие предикаты примитивно рекурсивны в Q и R:

• NOT_Q (x ).
• Q OR R: Q (x ) VR (x),
• Q AND R: Q (x ) R (x),
• Q ПОДРАЗУМЕВАЕТ R: Q (x ) → R (x)
• Q эквивалентно R: Q (x ) ≡ R (x)

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

• (Ey) y
• (y) y
• μyymu-оператора : определяется как «наименьшее значение y меньше z, такое что R (x, у) верно; или z, если такого значения нет. "

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

φ(x) =

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

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

φ (y, x ) = χ (y, КУРС-φ (y; x 2,... x n), x 2,... x n, то φ является примитивно рекурсивным в χ. Значение COURSE-φ (y; x2 до n) функции курса значений кодирует последовательность значений φ (0, xОт 2 до n),..., φ (y-1, xот 2 до n) исходной функции.

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

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

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

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

• Brainerd, WS, Landweber, LH (1974), Theory of Computing, Wiley, ISBN 0 -471-09585-0
• Роберт И. Соар, Рекурсивно перечислимые множества и степени, Springer-Verlag, 1987. ISBN 0-387-15299-7
• Стивен Клини (19 52) Введение в метаматематику, издательство 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
• Дэниел Северин 2008, Унарные примитивные рекурсивные функции, J. Symbolic Logic Volume 73, Issue 4, pp. 1122–1138 arXiv projecteuclid