Общая рекурсивная функция - General recursive function

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

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

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

Определение

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

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

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

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

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

1. Оператор композиции ${displaystyle circ ,}$ (также называемый оператор подстановки): Для m-арной функции ${displaystyle h(x_{1},ldots ,x_{m}),}$ и m k-арных функций ${displaystyle g_{1}(x_{1},ldots ,x_{k}),ldots ,g_{m}(x_{1},ldots ,x_{k})}$:
       ${displaystyle hcirc (g_{1},ldots ,g_{m}){stackrel {mathrm {def} }{=}}f,quad { ext{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 f(x_{1},ldots ,x_{k})}$ определяется, только если ${displaystyle 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 ho ,}$: Учитывая k-арная функция ${displaystyle g(x_{1},ldots ,x_{k}),}$ и k+2 -арная функция ${displaystyle h(y,z,x_{1},ldots ,x_{k}),}$:
       ${displaystyle {egin{aligned}ho (g,h)&{stackrel {mathrm {def} }{=}}fquad { ext{where the k+1 -ary function }}f{ ext{ is defined by}}f(0,x_{1},ldots ,x_{k})&=g(x_{1},ldots ,x_{k})f(S(y),x_{1},ldots ,x_{k})&=h(y,f(y,x_{1},ldots ,x_{k}),x_{1},ldots ,x_{k}),.end{aligned}}}$
   Это означает, что ${displaystyle f(y,x_{1},ldots ,x_{k})}$ определяется, только если ${displaystyle g(x_{1},ldots ,x_{k})}$ и ${displaystyle h(z,f(z,x_{1},ldots ,x_{k}),x_{1},ldots ,x_{k})}$ определены для всех ${displaystyle z<y.}$
3. Оператор минимизации ${displaystyle mu ,}$: Учитывая (k+1) -арная функция ${displaystyle f(y,x_{1},ldots ,x_{k}),}$, то k-арная функция ${displaystyle mu (f)}$ определяется:
       ${displaystyle {egin{aligned}mu (f)(x_{1},ldots ,x_{k})=z{stackrel {mathrm {def} }{iff }} f(i,x_{1},ldots ,x_{k})&>0quad { ext{for}}quad i=0,ldots ,z-1quad { ext{and}}f(z,x_{1},ldots ,x_{k})&=0quad end{aligned}}}$
   Интуитивно минимизация ищет - начиная поиск с 0 и продолжая вверх - наименьший аргумент, который заставляет функцию возвращать ноль; если такого аргумента нет, или если встречается аргумент, для которого ж не определено, то поиск никогда не прекращается, и ${displaystyle mu (f)}$ не определено для аргумента ${displaystyle (x_{1},ldots ,x_{k}).}$
   (Примечание: Хотя в некоторых учебниках используется μ-оператор, как здесь определено,^[4][5] другим нравится^[6][7] требовать, чтобы μ-оператор применялся к общий функции ${displaystyle f}$ Только. Хотя это ограничивает μ-оператор по сравнению с приведенным здесь определением, класс μ-рекурсивных функций остается тем же, что следует из теоремы Клини о нормальной форме.^[4][5] Единственное отличие состоит в том, что становится неразрешимым, удовлетворяет ли некоторый текст требованиям, предъявляемым к базовым функциям и операторам, поскольку не является полуразрешимым (следовательно, неразрешимым), является ли вычислимая (то есть μ-рекурсивная) функция тотальной.^[6])

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

${displaystyle f(x_{1},ldots ,x_{k})simeq g(x_{1},ldots ,x_{l})}$

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

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

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

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

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

${displaystyle f(x_{1},ldots ,x_{k})simeq U(mu y,T(y,e,x_{1},ldots ,x_{k}))}$.

Номер е называется индекс или же Число Гёделя для функции ж.^[8]:52–53 Следствием этого результата является то, что любая μ-рекурсивная функция может быть определена с использованием единственного экземпляра оператора μ, примененного к (общей) примитивной рекурсивной функции.

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

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

Символизм

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

• Постоянная функция: Клини использует "C"^п
  _q(Икс) = q », а Boolos-Burgess-Jeffrey (2002) (B-B-J) используют сокращение« const_п( Икс) = n ":

например C⁷
₁₃ (r, s, t, u, v, w, x) = 13

например const₁₃ (r, s, t, u, v, w, x) = 13

• Функция преемника: Клини использует x 'и S для «Преемника». Поскольку «преемник» считается примитивным, в большинстве текстов апостроф используется следующим образом:

S (а) = а +1 =_def a ', где 1 =_def 0', 2 =_def 0 '' и т. Д.

• Функция идентичности: Kleene (1952) использует "U^п
  _я "для указания функции тождества по переменным x_я; B-B-J использовать идентификатор функции идентификации^п
  _я по переменным x₁ к х_п:

U^п
_я( Икс ) = id^п
_я( Икс ) = х_я

например U⁷
₃ = id⁷
₃ (r, s, t, u, v, w, x) = t

• Оператор композиции (подстановки): Клини использует жирное лицо S^м
  _п (не путать с его S для "преемника" ! ). Верхний индекс «m» означает букву m.^th функции "f_м", тогда как нижний индекс" n "относится к n^th переменная "x_п":

Если нам задано h ( Икс ) = g (f₁(Икс), ..., f_м(Икс) )

час(Икс) = S^п
_м(г, ж₁, ..., f_м )

Аналогичным образом, но без нижних и верхних индексов, B-B-J пишут:

час(Икс') = Cn [g, f₁ , ..., f_м](Икс)

• Примитивная рекурсия: Клини использует символ " р^п(базовый шаг, шаг индукции) ", где n указывает количество переменных, B-B-J используют" Pr (базовый шаг, шаг индукции) (Икс)". Данный:

• базовый шаг: h (0, Икс ) = f ( Икс ), и
• шаг индукции: h (y + 1, Икс ) = g (y, h (y, Икс),Икс )

Пример: определение a + b примитивной рекурсией:

• базовый шаг: f (0, a) = a = U¹
  ₁(а)
• шаг индукции: f (b ', a) = (f (b, a))' = g (b, f (b, a), a) = g (b, c, a) = c '= S (U³
  ₂(б, в, а))

р² {U¹
₁(а), S [(U³
₂(б, в, а)]}

Пр {У¹
₁(а), S [(U³
₂(б, в, а)]}

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

1. S (а) = а '
2. U¹
   ₁(а) = а
3. U³
   ₂(b, c, a) = c
4. g (b, c, a) = S (U³
   ₂(b, c, a)) = c '
5. базовый шаг: h (0, a) = U¹
   ₁(а)

шаг индукции: h (b ', a) = g (b, h (b, a), a)

Он прибывает в:

а + Ь = р²[U¹
₁, S³
₁(S, U³
₂) ]

Примеры

• Число Фибоначчи
• Функция Маккарти 91

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

• Теория рекурсии
• Рекурсия
• Рекурсия (информатика)

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

1. Стэнфордская энциклопедия философии, Вход Рекурсивные функции, Раздел 1.7: «[Класс μ-рекурсивных функций] оказывается, что он совпадает с классом вычислимых по Тьюрингу функций, введенным Аланом Тьюрингом, а также с классом λ-определимых функций, введенным Алонзо Чёрчем."
2. Клини, Стивен С. (1936). «λ-определимость и рекурсивность». Математический журнал герцога. 2 (2): 340–352. Дои:10.1215 / s0012-7094-36-00227-2.
3. Тьюринг, Алан Мэтисон (Декабрь 1937 г.). «Вычислимость и λ-определимость». Журнал символической логики. 2 (4): 153–163. JSTOR  2268280. Схема доказательства на стр.153: ${displaystyle lambda {mbox{-definable}}}$ ${displaystyle {stackrel {triv}{implies }}}$ ${displaystyle lambda {mbox{-}}K{mbox{-definable}}}$ ${displaystyle {stackrel {160}{implies }}}$ ${displaystyle {mbox{Turing computable}}}$ ${displaystyle {stackrel {161}{implies }}}$ ${displaystyle mu {mbox{-recursive}}}$ ${displaystyle {stackrel {Kleene}{implies }}}$^[2] ${displaystyle lambda {mbox{-definable}}}$
4. Эндертон, Х. Б., Математическое введение в логику, Academic Press, 1972
5. Булос Г. С., Берджесс Дж. П., Джеффри Р. С., Вычислимость и логика, Cambridge University Press, 2007.
6. Джонс, Н. Д., Вычислимость и сложность: с точки зрения программирования, MIT Press, Кембридж, Массачусетс, Лондон, Англия, 1997 г.
7. Кфоури, А. Дж., Р. Н. Молл, М. А. Арбиб, Программный подход к вычислимости, 2-е изд., Springer-Verlag, Берлин, Гейдельберг, Нью-Йорк, 1982
8. Стивен Коул Клини (январь 1943 г.). «Рекурсивные предикаты и кванторы» (PDF). Труды Американского математического общества. 53 (1): 41–73. Дои:10.1090 / S0002-9947-1943-0007371-8.

• Клини, Стивен (1991) [1952]. Введение в метаматематику. Walters-Noordhoff и Северная Голландия. ISBN  0-7204-2103-9.
• Соаре, Р. (1999) [1987]. Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимо генерируемых множеств. Springer-Verlag. ISBN  9783540152996.
• Мински, Марвин Л. (1972) [1967]. Вычисления: конечные и бесконечные машины. Прентис-Холл. С. 210–5. ISBN  9780131654495.

На страницах 210-215 Мински показывает, как создать μ-оператор, используя зарегистрировать машину модель, демонстрируя тем самым ее эквивалентность общерекурсивным функциям.

• Булос, Джордж; Берджесс, Джон; Джеффри, Ричард (2002). «6.2 Минимизация». Вычислимость и логика (4-е изд.). Издательство Кембриджского университета. С. 70–71. ISBN  9780521007580.

внешняя ссылка

• Стэнфордская энциклопедия философии
• Компилятор для преобразования рекурсивной функции в эквивалентную машину Тьюринга.