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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\ Displaystyle е (а, б, с) = г (час (с, а), час (а, Ь)) \!}$

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

${\ 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 для false), или которые производят значения истинности в качестве выходных. ^[2] Этого можно достичь, отождествляя значения истинности с числами любым фиксированным способом. Например, обычно значение истинности t отождествляется с числом 1, а значение истинности f - с числом 0. После того, как эта идентификация выполнена, характеристическая функция набора A , которая всегда возвращает 1 или 0, может быть рассматривается как предикат, который сообщает, входит ли число в набор A. Такое отождествление предикатов с числовыми функциями предполагается до конца этой статьи.

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

Примером примитивного рекурсивного языка программирования является язык, который содержит основные арифметические операторы (например, + и - или ADD и SUBTRACT), условные выражения и сравнение (IF-THEN, EQUALS, LESS-THAN) и ограниченные циклы, такие как базовые for цикл , где существует известная или вычисляемая верхняя граница для всех циклов (FOR i FROM 1 TO n, при этом ни i, ни n не могут быть изменены телом цикла). Никакие управляющие структуры большей общности, такие как циклы while или IF-THEN плюс GOTO , не допускаются в примитивно-рекурсивном языке. Хофштадтер «s 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 ( n ) - это «преемник n » (т. Е. N +1), P ₁ ¹ - функция идентичности , а P ₂ ³ - функция проекции, которая принимает 3 аргумента и возвращает второй. Функции f и g, требуемые приведенным выше определением операции примитивной рекурсии, исполняются соответственно P ₁ ¹ и композицией S и P ₂ ³ .

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

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

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

пред (0) = 0,

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

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

пред (0) = 0,

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

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

sub (0, x ) = P ₁ ¹ ( x ),

sub (S ( n ), x ) = pred ( P ₂ ³ ( 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 - одномерная примитивная функция рекурсии, определенная следующим образом:

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

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

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

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

${\displaystyle \exists b:\exists c:\beta (b,c,0)=C\land \forall i:(i<n)\rightarrow (\beta (b,c,i+1)=g(i,\beta (b,c,i)))\land (m=\beta (b,c,n))}$

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

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

Связь с рекурсивными функциями [ править ]

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

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

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

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

Ограничения [ править ]

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

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

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

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

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

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

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

1. Дополнение: a + b
2. Умножение: a × b
3. Возведение в степень: a ^b
4. Факториал а! : 0! = 1, a '! = а! × а '
5. pred (a): (Предшественник или декремент): Если a> 0, то a-1 else 0
6. Правильное вычитание a ∸ b: если a ≥ b, то ab else 0
7. Минимум (a ₁ , ... a _n )
8. Максимум (a ₁ , ... 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. а | 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} [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 | а еще 0

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

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

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

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

• (Ey) _{y <z} R ( x , y), где (Ey) _{y <z} означает «существует хотя бы один y, который меньше z, такой, что»
• (y) _{y <z} R ( x , y), где (y) _{y <z} означает «для всех y, меньших z, верно, что»
• μy _{y <z} R ( x , y). Оператор μy _{y <z} R ( x , y) является ограниченной формой так называемого минимизирующего или мю-оператора : определяется как «наименьшее значение 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} ) исходной функции.

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

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

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

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

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

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

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

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

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

История [ править ]

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

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

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

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

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

Заметки [ править ]

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

• Брейнерд, WS, Ландвебер, LH (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