Общая рекурсивная функция

редактировать
Одно из нескольких эквивалентных определений вычислимой функции

В математической логике и информатика, общая рекурсивная функция (часто сокращается до рекурсивная функция ) или μ-рекурсивная функция, является частичной функцией от натуральных чисел до натуральных чисел, что является "вычислимым" в интуитивном смысле. В теории вычислимости показано, что μ-рекурсивные функции - это в точности функции, которые могут быть вычислены машинами Тьюринга (это одна из теорем, поддерживающих Черч. –Тезис Тьюринга ). Μ-рекурсивные функции тесно связаны с примитивно-рекурсивными функциями, и их индуктивное определение (ниже) основано на определении примитивно-рекурсивных функций. Однако не каждая μ-рекурсивная функция является примитивной рекурсивной функцией - наиболее известным примером является функция Аккермана.

. Другими эквивалентными классами функций являются функции лямбда-исчисления и функции, которые могут вычисляться с помощью алгоритмов Маркова.

Подмножество всех полных рекурсивных функций со значениями в {0,1} известно в теории вычислительной сложности как класс сложности R.

Содержание

  • 1 Определение
  • 2 Эквивалентность с другими моделями вычислимости
  • 3 Теорема о нормальной форме
  • 4 Символизм
  • 5 Примеры
  • 6 См. Также
  • 7 Ссылки
  • 8 Внешние ссылки

Определение

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

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

Примитивные или «базовые» функции:

  1. Постоянные функции C n: для каждого натурального числа n {\ displaystyle n \,}n \, и каждого k {\ displaystyle k \,}k \, . C nk (x 1,…, xk) = defn {\ displaystyle C_ {n} ^ {k} (x_ {1}, \ ldots, x_ {k}) {\ stackrel {\ mathrm {def}} {=}} n}{\ displaystyle C_ {n} ^ {k} (x_ {1}, \ ldo ts, x_ {k}) {\ stackrel {\ mathrm {def}} {=}} n} . Альтернативные определения используют вместо этого нулевую функцию как примитивную функцию, которая всегда возвращает ноль, и построили постоянные функции из нулевой функции, преемницы функция и оператор композиции.
  2. Функция-последователь S: . S (x) = defx + 1 {\ displaystyle S (x) {\ stackrel {\ mathrm {def}} {=}} x + 1 \, }{\ displaystyle S (x) {\ stackrel {\ mathrm {def}} {=}} x + 1 \,}
  3. Функция проекции P ik {\ displaystyle P_ {i} ^ {k}}P_ {i} ^ {k} (также называемая функцией идентичности ): для всех натуральных чисел. я, k {\ displaystyle i, k}{\ displaystyle i, k} такой, что 1 ≤ i ≤ k {\ displaystyle 1 \ leq i \ leq k}1 \ leq i \ leq k :. P ik (x 1,…, xk) = defxi. {\ displaystyle P_ {i} ^ {k} (x_ {1}, \ ldots, x_ {k}) {\ stackrel {\ mathrm {def}} {=}} x_ {i} \,.}{\ displaystyle P_ {i} ^ {k} (x_ {1}, \ ldots, x_ {k}) {\ stackrel {\ mathrm {def}} { =}} x_ {i} \,.}

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

  1. Состав оператор ∘ {\ displaystyle \ circ \,}\ circ \, (также называемый оператором подстановки ): дана m-арная функция h (x 1, …, Xm) {\ displaystyle h (x_ {1}, \ ldots, x_ {m}) \,}h (x_ {1}, \ ldots, x_ {m}) \, и m k-арных функций g 1 (x 1,…, xk),…, Gm (x 1,…, xk) {\ displaystyle g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k})}g_ {1} (x_ {1}, \ ldots, x_ {k }),\Я делаю ts, g_ {m} (x_ {1}, \ ldots, x_ {k}) :. h ∘ (g 1,…, gm) = deff, где f (x 1,…, xk) = h (g 1 (x 1,…, xk),…, gm ( x 1,…, xk)). {\ 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 h \ circ (g_ {1}, \ ldots, g_ {m}) {\ stackrel {\ mathrm {def}} {=}} f, \ quad {\ text { где}} \ quad f (x_ {1}, \ ldots, x_ {k}) = h (g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} ( x_ {1}, \ ldots, x_ {k})).} . Это означает, что f (x 1,…, xk) {\ displaystyle f (x_ {1}, \ ldots, x_ {k})}{\ displaystyle f (x_ {1}, \ ldots, x_ {k})} определяется, только если g 1 (x 1,…, xk),…, gm (x 1,…, xk), {\ displaystyle g_ {1} (x_ {1}, \ ldots, x_ {k }), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k}),}{\ displaystyle g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k}),} и h (g 1 (x 1,…, xk),…, gm (x 1,…, xk)) {\ displaystyle h (g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k}))}{\ displaystyle h (g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k}))} все определены.
  2. Оператор примитивной рекурсии ρ {\ displaystyle \ rho \,}\ rho \, : Учитывая k- арная функция g (x 1,…, xk) {\ displaystyle g (x_ {1}, \ ldots, x_ {k}) \,}g (x_ {1}, \ ldots, x_ {k}) \, и k + 2 -арная функция час (y, z, x 1,…, xk) {\ displaystyle h (y, z, x_ {1}, \ ldots, x_ {k}) \,}h (y, z, x_ {1}, \ ldots, x_ {k}) \, :. ρ (g, h) = deff где k + 1 -арная функция f определяется формулой f (0, x 1,…, xk) = g (x 1,…, x k) f (S (y), x 1,…, x k) = h (y, f (y, x 1,…, x k), x 1,…, x k). {\ displaystyle {\ begin {align} \ rho (g, h) {\ stackrel {\ mathrm {def}} {=}} f \ quad {\ text {где k + 1 -арная функция}} f { \ text {определяется как}} \\ 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 {align}}}{\ displaystyle {\ begin {align} \ rho (g, h) {\ stackrel {\ mathrm {def}} {=}} f \ quad {\ text {где k + 1 -арная функция}} f { \ text {определяется как}} \\ 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_ { к}) \,. \ конец {выровнено}}} . Это означает, что f (y, x 1,…, xk) {\ displaystyle f (y, x_ {1}, \ ldots, x_ { k})}{\ displaystyle f (y, x_ {1}, \ ldots, x_ {k})} определяется, только если g (x 1,…, xk) {\ displaystyle g (x_ {1}, \ ldots, x_ {k})}{\ displaystyle g (x_ {1}, \ ldots, x_ {k})} и час (z, f (z, x 1,…, xk), x 1,…, xk) {\ displaystyle h (z, f (z, x_ {1}, \ ldots, x_ {k) }), x_ {1}, \ ldots, x_ {k})}{\ displaystyle h (z, f (z, x_ {1}, \ ldots, x_ {k}), x_ {1}, \ ldots, x_ {k})} определены для всех z < y. {\displaystyle z{\ displaystyle z <y.}
  3. оператор минимизации μ {\ displaystyle \ mu \,}\ му \, : дана (k + 1) -арная функция f (y, x 1,…, xk) {\ displaystyle f (y, x_ {1}, \ ldots, x_ {k}) \, }f (y, x_ {1}, \ ldots, x_ {k}) \, , k-арная функция μ (f) {\ displaystyle \ mu (f)}\ mu (f) определяется следующим образом:. μ (f) ( x 1,…, xk) = z ⟺ deff (i, x 1,…, xk)>0 для i = 0,…, z - 1 и f (z, x 1, …, Xk) = 0 {\ displaystyle {\ begin {align} \ mu (f) (x_ {1}, \ ldots, x_ {k}) = z {\ stackrel {\ mathrm {def}} {\ iff} } \ f (i, x_ {1}, \ ldots, x_ {k})>0 \ quad {\ text {for}} \ quad i = 0, \ ldots, z-1 \ quad {\ text {и }} \\ f (z, x_ {1}, \ ldots, x_ {k}) = 0 \ quad \ end {align}}}{\displaystyle {\begin{aligned}\mu (f)(x_{1},\ldots,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(i,x_{1},\ldots,x_{k})>0 \ quad {\ text {for}} \ quad i = 0, \ ldots, z-1 \ quad {\ text {and}} \\ f (z, x_ {1}, \ ldots, x_ {k}) = 0 \ quad \ end {выровнено}} } . Интуитивно, минимизация ищет— начало поиска с 0 и продвижение вверх - наименьший аргумент, который заставляет функцию возвращать ноль; если такого аргумента нет или если встречается аргумент, для которого f не определено, поиск никогда не прекращается, и μ (f) {\ displaystyle \ mu (f)}{\ displaystyle \ mu (f)} не определено для аргумента (x 1,…, xk). {\ displaystyle (x_ {1}, \ ldots, x_ {k}).}{\ displaystyle (x_ {1}, \ ldots, x_ {k}).} . (Примечание: в некоторых учебниках используется μ-оператор, как определено здесь, в других, например, требуется, чтобы μ-оператор применялся к общим функциям Только f {\ displaystyle f}f . Хотя это ограничивает μ-оператор по сравнению с приведенным здесь определением, класс μ-рекурсивных функций остается прежним, что следует из теоремы Клини о нормальной форме. Единственное отличие состоит в том, что становится неразрешимым, удовлетворяет ли некоторый текст требованиям, предъявляемым к базовым функциям и операторам, поскольку не является полуразрешимым (следовательно, неразрешимым), является ли вычислимая (т. Е. Μ-рекурсивная) функция полной.)

Оператор строгого равенства ≃ {\ displaystyle \ simeq}\ simeq может использоваться для сравнения частичных μ-рекурсивных функций. Это определено для всех частичных функций f и g, так что

f (x 1,…, xk) ≃ g (x 1,…, xl) {\ displaystyle f (x_ {1}, \ ldots, x_ {k }) \ simeq g (x_ {1}, \ ldots, x_ {l})}f (x_ {1}, \ ldots, x_ {k}) \ simeq g (x_ {1}, \ ldots, x_ {l})

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

Эквивалентность с другими моделями вычислимости

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

Теорема о нормальной форме

A Теорема о нормальной форме, принадлежащая Клини, говорит, что для каждого k существуют примитивные рекурсивные функции U (y) {\ displaystyle U (y) \!}U (y) \! и T (y, e, x 1,…, xk) {\ displaystyle T (y, e, x_ {1}, \ ldots, x_ {k}) \!}T (y, e, x_ {1}, \ ldots, x_ {k}) \! такая, что для любой μ-рекурсивной функции f (x 1,…, xk) {\ displaystyle f (x_ {1}, \ ldots, x_ {k}) \!}f (x_ {1}, \ ldots, x_ {k}) \! с k свободных переменных существует такая e, что

f (x 1,…, xk) ≃ U (μ y T (y, e, x 1,…, xk)) {\ displaystyle f (x_ {1}, \ ldots, x_ {k}) \ simeq U (\ mu y \, T (y, e, x_ {1}, \ ldots, x_ {k}))}f (x_ {1}, \ ldots, x_ {k}) \ simeq U (\ mu y \, T (y, e, x_ {1}, \ ldots, x_ {k}))) .

Число e называется индекс или число Гёделя для функции f. Следствием этого результата является то, что любая μ-рекурсивная функция может быть определена с использованием единственного экземпляра оператора μ, примененного к (общей) примитивной рекурсивной функции.

Мински (1967) замечает (как и Булос-Берджесс-Джеффри (2002) стр. 94–95), что U, определенный выше, по существу является μ-рекурсивным эквивалентом универсальной машины Тьюринга :

Построить U - значит записать определение общерекурсивной функции U (n, x), которая правильно интерпретирует число n и вычисляет соответствующую функцию от x. прямое построение U потребовало бы, по сути, того же количества усилий и, по сути, тех же идей, которые мы вложили в построение универсальной машины Тьюринга. (курсив в оригинале, Минский (1967) с. 189)

Символизм

В литературе используется ряд различных символизмов. Преимуществом использования символики является вывод функции путем «вложения» операторов один в другой, что проще записать в компактной форме. Далее мы будем сокращать строку параметров x 1,..., x n как x:

  • Постоянная функция : Клини использует "C. q(x) = q "и Boolos-Burgess-Jeffrey (2002) (BBJ) используют сокращение" const n( x) = n ":
например. C. 13(r, s, t, u, v, w, x) = 13
например, const 13 (r, s, t, u, v, w, x) = 13
  • Функция-последователь : Клини использует x 'и S для «наследника». Поскольку «преемник» считается примитивным, в большинстве текстов апостроф используется следующим образом:
S (a) = a +1 = def a ', где 1 = def 0 ', 2 = def 0' 'и т. Д.
  • Функция идентичности : Клини (1952) использует "U. i" для обозначения функции идентичности по переменным x я ; B-B-J используют идентификатор функции идентификации. iнад переменными x 1 до x n:
U. i( x) = id. i( x) = x i
, например. U. 3= id. 3(r, s, t, u, v, w, x) = t
  • Оператор композиции (подстановки) : Клини использует полужирный шрифт S. n(не для следует путать с его S для "преемника" ! ). Верхний индекс «m» относится к m функции «f m », тогда как нижний индекс «n» относится к переменной n «x n":
. Если нам задано h (x ) = g (f 1(x),..., f m(x))
h(x) = S. m(g, f 1,..., f m)
В аналогичным образом, но без нижних и верхних индексов, BBJ записывает:
h (x ') = Cn [g, f 1,..., f m](x)
  • Primitive Recursion : Клини использует символ «R (базовый шаг, индукционный шаг)», где n указывает количество переменных, BBJ использует «Pr (базовый шаг, индукционный шаг) (x ) ". Дано:
  • базовый шаг: h (0, x ) = f (x ) и
  • шаг индукции: h (y + 1, x ) = g (y, h (y, x),x)
) Пример: определение примитивной рекурсии a + b:
  • базовый шаг: f (0, a) = a = U. 1(a)
  • шаг индукции: f (b ', a) = (f (b, a))' = g (b, f (b, a), a) = g (b, c, a) = c '= S (U. 2(b, c, a))
R {U. 1(a), S [(U. 2(b, c, a)]}
Pr {U. 1(a), S [(U. 2(b, c, a)]}

Пример : Клини приводит пример того, как выполнить рекурсивный вывод f (b, a) = b + a (обратите внимание на изменение переменных a и b). Он начинает с 3 исходных функций

  1. S (a) = a '
  2. U. 1(a) = a
  3. U. 2(b, c, a) = c
  4. g (b, c, a) = S (U. 2(b, c, a)) = c '
  5. базовый шаг: h (0, a) = U. 1(a)
шаг индукции: h (b ', a) = g (b, h (b, a), a)

Он достигает:

a + b = R [U. 1, S. 1(S, U. 2)]

Примеры

См. Также

Ссылки

Внешние ссылки

Последняя правка сделана 2021-05-21 14:46:19
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте