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

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

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

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

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

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

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

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

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

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

Оператор композиции (также называемый оператором подстановки ): для m-арной функции и m k-арной функции : это означает, что она определена, только если и все они определены. ${\ Displaystyle \ circ \,}$ ${\ Displaystyle ч (х_ {1}, \ ldots, х_ {м}) \,}$ ${\ displaystyle g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k})}$
$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})).$
$f(x_{1},\ldots ,x_{k})$ $g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),$ $h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))$
Оператор примитивной рекурсии : Учитывая k -арную функцию и k +2 -арную функцию : Это означает, что он определен, только если и определены для всех $\rho \,$ $g(x_{1},\ldots ,x_{k})\,$ $h(y,z,x_{1},\ldots ,x_{k})\,$
${\begin{aligned}\rho (g,h)&{\stackrel {\mathrm {def} }{=}}f\quad {\text{where the k+1 -ary function }}f{\text{ 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}}$
$f(y,x_{1},\ldots ,x_{k})$ $g(x_{1},\ldots ,x_{k})$ $h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})$ $z<y.$
Оператор минимизации . Для ( k +1) -арной функции , k -арная функция определяется следующим образом: интуитивно минимизация ищет - начиная поиск с 0 и продвигаясь вверх - наименьший аргумент, который заставляет функцию возвращать ноль; если такого аргумента нет или если встречается аргумент, для которого $f$ не определено, то поиск никогда не прекращается и не определен для аргумента ( Примечание : хотя в некоторых учебниках используется μ-оператор, как определено здесь, ^{[5 ]}^[6] другие, такие как ^[7]^[8], требуют, чтобы μ-оператор применялся к полным функциям $\mu \,$ $f(y,x_{1},\ldots ,x_{k})\,$ $\mu (f)$
${\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{aligned}}$
$\mu (f)$ $(x_{1},\ldots ,x_{k}).$
$f$ Только. Хотя это ограничивает μ-оператор по сравнению с приведенным здесь определением, класс μ-рекурсивных функций остается тем же, что следует из теоремы Клини о нормальной форме. ^[5]^[6] Единственное отличие состоит в том, что становится неразрешимым, удовлетворяет ли некоторый текст требованиям, предъявляемым к базовым функциям и операторам, поскольку не является полуразрешимым (следовательно, неразрешимым), является ли вычислимая (т.е. μ-рекурсивная) функция общий. ^[7] )

Сильное равенство оператор может быть использован для сравнения частичного мю-рекурсивной функции. Это определено для всех частичных функций f и g так, что $\simeq$

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

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

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

Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Февраль 2010 г. )

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

Теорема о нормальной форме [ править ]

Нормальная форма теоремы из - за Клини говорит , что для каждого к существуют примитивные рекурсивные функции и таким образом, что для любого ц-рекурсивной функции с K свободными переменными существует е такое , что $U(y)\!$ $T(y,e,x_{1},\ldots ,x_{k})\!$ $f(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 . ^[9]^{: 52–53} Следствием этого результата является то, что любая μ-рекурсивная функция может быть определена с использованием одного экземпляра оператора μ, примененного к (общей) примитивно-рекурсивной функции.

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

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

Символизм [ править ]

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

Постоянная функция : Клини использует "C"^п
_д( x ) = q "и Boolos-Burgess-Jeffrey (2002) (BBJ) используют сокращение" const _n ( x ) = n ":

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

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

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

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

Функция идентичности : Kleene (1952) использует "U^н
_я"для обозначения функции идентичности по переменным x _i ; BBJ использует идентификатор функции идентичности^н
_япо переменным от x ₁ до x _n :

U^н
_я( x ) = идентификатор^н
_я( х ) = х _я

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

Оператор композиции (подстановки) : Клини использует жирный шрифт S^m
_n(не путать с его S для "преемника" ! ). Верхний индекс «m» относится к m- ^й функции «f _m », тогда как нижний индекс «n» относится к n- ^й переменной «x _n »:

Если нам дано h ( x ) = g (f ₁ ( x ), ..., f _m ( x ))

h ( x ) = S^п
_м(g, f ₁ , ..., f _m )

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

h ( x ' ) = Cn [g, f ₁ , ..., f _m ] ( x )

Примитивная рекурсия : Клини использует символ « 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¹
₁(а)
шаг индукции: f (b ', a) = (f (b, a))' = g (b, f (b, a), a) = g (b, c, a) = c '= S (U³
₂(б, в, а))

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

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

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

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

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

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

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

Примеры [ править ]

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

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

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

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

^ https://plato.stanford.edu/entries/recursive-functions/#PartRecuFuncPartRecuFuncREC
^ Стэнфордская энциклопедия философии , Entry Recursive Functions , Sect.1.7: «[Класс μ-рекурсивных функций] оказывается совпадающим с классом вычислимых по Тьюрингу функций, введенных Аланом Тьюрингом, а также с классом λ -определяемые функции, введенные Алонзо Черчем ".
Перейти ↑ Kleene, Stephen C. (1936). «λ-определимость и рекурсивность» . Математический журнал герцога . 2 (2): 340–352. DOI : 10,1215 / s0012-7094-36-00227-2 .
↑ Тьюринг, Алан Мэтисон (декабрь 1937 г.). «Вычислимость и λ-определимость». Журнал символической логики . 2 (4): 153–163. JSTOR 2268280 . Схема доказательства на стр.153: ^[3] $\lambda {\mbox{-definable}}$ ${\stackrel {triv}{\implies }}$ $\lambda {\mbox{-}}K{\mbox{-definable}}$ ${\stackrel {160}{\implies }}$ ${\mbox{Turing computable}}$ ${\stackrel {161}{\implies }}$ $\mu {\mbox{-recursive}}$ ${\stackrel {Kleene}{\implies }}$ $\lambda {\mbox{-definable}}$
^ а б Эндертон, HB, Математическое введение в логику, Academic Press, 1972
^ a b Булос, GS, Берджесс, JP, Джеффри, Р.С., Вычислимость и логика, Cambridge University Press, 2007
^ a b Джонс, Н. Д., Вычислимость и сложность: с точки зрения программирования, MIT Press, Кембридж, Массачусетс, Лондон, Англия, 1997
^ Kfoury, AJ, Р. Моль, М. А. Арбиб, программирование подход к вычислимости, 2е изд., Springer-Verlag, Berlin, Heidelberg, НьюЙорк, 1982
↑ Стивен Коул Клини (январь 1943 г.). «Рекурсивные предикаты и кванторы» (PDF) . Труды Американского математического общества . 53 (1): 41–73. DOI : 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.

Внешние ссылки [ править ]

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

[1] ttps://plato.stanford.edu/entries/recursive-functions/#PartRecuFuncPartRecuFuncREC

[2] Стэнфордская энциклопедия философии , Entry Recursive Functions , Sect.1.7: «[Класс μ-рекурсивных функций] оказывается совпадающим с классом вычислимых по Тьюрингу функций, введенных Аланом Тьюрингом, а также с классом λ -определяемые функции, введенные Алонзо Черчем ".

[3] Перейти ↑ Kleene, Stephen C. (1936). «λ-определимость и рекурсивность» . Математический журнал герцога . 2 (2): 340–352. DOI : 10,1215 / s0012-7094-36-00227-2 .

[4] Тьюринг, Алан Мэтисон (декабрь 1937 г.). «Вычислимость и λ-определимость». Журнал символической логики . 2 (4): 153–163. JSTOR 2268280 . Схема доказательства на стр.153: ^[3] $\lambda {\mbox{-definable}}$ ${\stackrel {triv}{\implies }}$ $\lambda {\mbox{-}}K{\mbox{-definable}}$ ${\stackrel {160}{\implies }}$ ${\mbox{Turing computable}}$ ${\stackrel {161}{\implies }}$ $\mu {\mbox{-recursive}}$ ${\stackrel {Kleene}{\implies }}$ $\lambda {\mbox{-definable}}$

[Enderton.1972-5] а б Эндертон, HB, Математическое введение в логику, Academic Press, 1972

[Boolos.Burgess.Jeffrey.2007-6] Булос, GS, Берджесс, JP, Джеффри, Р.С., Вычислимость и логика, Cambridge University Press, 2007

[Jones.1997-7] Джонс, Н. Д., Вычислимость и сложность: с точки зрения программирования, MIT Press, Кембридж, Массачусетс, Лондон, Англия, 1997

[8] Kfoury, AJ, Р. Моль, М. А. Арбиб, программирование подход к вычислимости, 2е изд., Springer-Verlag, Berlin, Heidelberg, НьюЙорк, 1982

[9] Стивен Коул Клини (январь 1943 г.). «Рекурсивные предикаты и кванторы» (PDF) . Труды Американского математического общества . 53 (1): 41–73. DOI : 10.1090 / S0002-9947-1943-0007371-8 .

[1]