Примитивная рекурсивная функция - Primitive recursive function

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

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

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

Определение

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

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

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

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

4. Сочинение: Учитывая k-арная примитивная рекурсивная функция ж, и k много м-арно-примитивные рекурсивные функции грамм₁,...,грамм_k, то сочинение из ж с грамм₁,...,грамм_k, т.е. м-арная функция ${displaystyle h(x_{1},ldots ,x_{m})=f(g_{1}(x_{1},ldots ,x_{m}),ldots ,g_{k}(x_{1},ldots ,x_{m})),}$ примитивно рекурсивно.

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

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

   ${displaystyle h(0,x_{1},ldots ,x_{k})=f(x_{1},ldots ,x_{k}),}$ и

   ${displaystyle h(S(y),x_{1},ldots ,x_{k})=g(y,h(y,x_{1},ldots ,x_{k}),x_{1},ldots ,x_{k}),.}$

Пример. Предполагать ж(Икс) = п₁¹(Икс) = Икс и грамм(Икс,у,z)= S(п₂³(Икс,у,z)) = S(у). потом час(0,Икс) = Икс и час(S(у),Икс) = грамм(у,час(у,Икс),Икс) = S(час(у,Икс)). Сейчас же час(0,1) = 1, час(1,1) = S(час(0,1)) = 2, час(2,1) = S(час(1,1)) = 3. Это час 2-арная примитивная рекурсивная функция. Мы можем назвать это «сложением».

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

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

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

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

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

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

${displaystyle f(a,b,c)=g(h(P_{3}^{3}(a,b,c),P_{1}^{3}(a,b,c)),h(P_{1}^{3}(a,b,c),P_{2}^{3}(a,b,c))).}$

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

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

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

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

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

Примеры

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

Добавление

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

${displaystyle add(0,x)=x}$,

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

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

${displaystyle add(0,x)=P_{1}^{1}(x),}$

${displaystyle add(S(n),x)=S(P_{2}^{3}(n,add(n,x),x))}$

Здесь S (п) является "преемником п"(т.е. п+1), п₁¹ это функция идентичности, и п₂³ это функция проекции который принимает 3 аргумента и возвращает второй. Функции ж и грамм требуемые в соответствии с приведенным выше определением операции примитивной рекурсии, соответственно играют п₁¹ и состав S и п₂³.

Вычитание

Смотрите также: Монус

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

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

пред (0) = 0,

пред (п + 1) = п.

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

пред (0) = 0,

пред (S (п)) = п₁²(п, пред (п)).

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

sub (0, Икс) = п₁¹(Икс),

sub (S (п), Икс) = пред (п₂³(п, sub (п, Икс), Икс)).

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

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

Возведение в степень и проверка на простоту примитивно рекурсивны. Учитывая примитивные рекурсивные функции е, ж, грамм, и час, функция, возвращающая значение грамм когда е≤ж и ценность час в противном случае примитивно рекурсивно.

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

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

Использование в арифметике Пеано первого порядка

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

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

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

${displaystyle h(0)=C}$

${displaystyle h(n+1)=g(n,h(n))}$

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

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

${displaystyle exists b:exists c:eta (b,c,0)=Cland forall i:(i<n)ightarrow (eta (b,c,i+1)=g(i,eta (b,c,i)))land (m=eta (b,c,n))}$

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

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

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

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

Каждая примитивно рекурсивная функция является полностью рекурсивной, но не все полностью рекурсивные функции являются примитивно рекурсивными. В Функция Аккермана А(м,п) является хорошо известным примером тотальной рекурсивной функции (фактически, доказуемой суммы), которая не является примитивно рекурсивной. Существует характеристика примитивно-рекурсивных функций как подмножества полных рекурсивных функций с помощью функции Аккермана. Эта характеристика утверждает, что функция является примитивно рекурсивной. если и только если есть натуральное число м такой, что функция может быть вычислена машина, которая всегда останавливается в пределах A (м,п) или меньше шагов, где п - сумма аргументов примитивной рекурсивной функции.^[3]

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

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

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

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

Ограничения

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

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

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

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

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

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

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

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

Следующие ниже примеры и определения взяты из Kleene (1952) pp. 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 () ниже). По определению функция φ (Икс) является «представляющей функцией» предиката P (Икс), если φ принимает только значения 0 и 1 и дает 0 когда P истинно ".

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

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

В дальнейшем сокращение Икс =_def Икс₁, ... Икс_п; нижние индексы могут применяться, если того требует значение.

• #A: Функция φ, явно определяемая из функций Ψ и констант q₁, ... q_п примитивно рекурсивно в.
• #B: Конечная сумма Σ_{у <г} ψ (Икс, y) и произведением Π_{у <г}ψ (Икс, y) примитивно рекурсивны по ψ.
• #C: A предикат P, полученный подстановкой функций χ₁, ..., χ_м для соответствующих переменных предиката Q примитивно рекурсивно по χ₁, ..., χ_м, В.
• #D: Следующие предикаты примитивно рекурсивны в Q и R:

• NOT_Q (Икс) .
• Q ИЛИ R: Q (Икс) V R (Икс),
• В И Р: Q (Икс) & Р(Икс),
• Q ПОДРАЗУМЕВАЕТ R: Q (Икс) → R (Икс)
• Q эквивалентно R: Q (Икс) ≡ R (Икс)

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

• (Эй)_{у <г} Р(Икс, y) где (Ey)_{у <г} означает «существует хотя бы один y, который меньше z такой, что»
• (у)_{у <г} Р(Икс, y) где (y)_{у <г} означает "для всех y меньше z верно, что"
• μy_{у <г} Р(Икс, у). Оператор μy_{у <г} Р(Икс, y) является ограниченный форма так называемой минимизации - или мю-оператор: Определяется как "наименьшее значение y меньше z такого, что R (Икс, y) верно; или z, если такого значения нет ".

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

φ (Икс) =

• φ₁(Икс) если Q₁(Икс) правда,
• . . . . . . . . . . . . . . . . . . .
• φ_м(Икс) если Q_м(Икс) правда
• φ_{м + 1}(Икс) иначе

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

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

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

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

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

Конечность и постоянство результатов

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

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

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

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

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

История

Рекурсивные определения ранее использовались более или менее формально в математике, но построение примитивной рекурсии восходит к Ричард Дедекинд теорема 126 его Was sind und was sollen die Zahlen? (1888). В этой работе впервые было доказано, что некоторая рекурсивная конструкция определяет уникальную функцию.^[4][5][6]

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

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

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

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

Примечания

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

Рекомендации

• Брейнерд, У.С., Ландвебер, Л.Х. (1974), Теория вычислений, Wiley, ISBN  0-471-09585-0
• Роберт И. Соаре, Рекурсивно перечислимые множества и степени, 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
• Даниэль Северин 2008, Унарные примитивные рекурсивные функции, J. Symbolic Logic Volume 73, Issue 4, pp. 1122–1138 arXiv projecteuclid