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

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

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

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

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

Определение

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

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

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

1. Постоянные функции C^к
   _н: Для каждого натурального числа n и каждого 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 1\leq i\leq k}$

   ${\displaystyle P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}\,.}$

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

1. Оператор композиции (также называемый оператором подстановки ): Дана m-ичная функция и m k-ичных функций : ${\displaystyle \circ \,}$ ${\displaystyle h(x_{1},\ldots ,x_{m})\,}$ ${\displaystyle 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{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. Примитивный оператор рекурсии ρ : Даны k -арная функция и k +2-арная функция : ${\displaystyle g(x_{1},\ldots ,x_{k})\,}$ ${\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}$

   ${\displaystyle {\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}}}$

   Это означает, что определено только тогда, когда и определены для всех ${\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. Оператор минимизации μ : Для ( k +1)-арной функции k -арная функция определяется как: ${\displaystyle f(y,x_{1},\ldots ,x_{k})\,}$ ${\displaystyle \mu (f)}$

   ${\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{aligned}}}$

Интуитивно минимизация ищет — начиная поиск с 0 и продолжая вверх — наименьший аргумент, который заставляет функцию возвращать ноль; если такого аргумента нет или если встречается аргумент, для которого f не определен, то поиск никогда не заканчивается и не определен для аргумента ${\displaystyle \mu (f)}$ ${\displaystyle (x_{1},\ldots ,x_{k}).}$

В то время как некоторые учебники используют μ-оператор, как он определен здесь, ^{[5] [6]} другие ^{[7] [8]} требуют, чтобы μ-оператор применялся только к тотальным функциям f . Хотя это ограничивает μ-оператор по сравнению с данным здесь определением, класс μ-рекурсивных функций остается тем же самым, что следует из теоремы Клини о нормальной форме (см. ниже). ^{[5] [6]} Единственное отличие состоит в том, что становится неразрешимым, определяет ли конкретное определение функции μ-рекурсивную функцию, как неразрешимым является, является ли вычислимая (т. е. μ-рекурсивная) функция тотальной. ^[7]

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

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

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

Примеры

Примеры, не включающие оператор минимизации, можно найти в разделе Примитивные рекурсивные функции#Примеры .

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

• Целый квадратный корень из x можно определить как наименьшее z такое, что . Используя оператор минимизации, общее рекурсивное определение имеет вид , где Not , Gt и Mul являются логическими отрицанием , больше чем и умножением ^[9] соответственно. Фактически, является ${\displaystyle (z+1)^{2}>x}$ ${\displaystyle \operatorname {Isqrt} =\mu (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))}$ ${\displaystyle (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))\;(z,x)=(\lnot S(z)*S(z)>x)}$0 тогда и только тогда, когда выполняется. Следовательно, это наименьшее z , которое выполняется. Отрицательный юнктор Not необходим, поскольку Gt кодирует истину с помощью ${\displaystyle S(z)*S(z)>x}$ ${\displaystyle \operatorname {Isqrt} (x)}$ ${\displaystyle S(z)*S(z)>x}$ 1 , в то время как μ ищет0 .

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

• ^{[ необходим пример ]}

Полная рекурсивная функция

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

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

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

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

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

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

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

Мински отмечает, что определенное выше по сути является μ-рекурсивным эквивалентом универсальной машины Тьюринга : ${\displaystyle U}$

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

Символизм

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

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

например С⁷
₁₃( р, с, т, у, в, ш, х ) = 13

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

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

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

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

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

например U⁷
₃= идентификатор⁷
₃( р, с, т, у, в, ш, х ) = т

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

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

ч( х ) = S^н
_м(г, ж ₁ , ... , ж _м )

Аналогичным образом, но без нижних и верхних индексов, 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³
  ₂( б, в, а ))

Р ² { У¹
₁(а), С [ (U³
₂( б, в, а ) ] }

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

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

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

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

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

а+б = Р2 [ ^У1
₁, С³
₁(С, У³
₂) ]

Примеры

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

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

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

Ссылки

1. «Рекурсивные функции». Стэнфордская энциклопедия философии . Лаборатория метафизических исследований, Стэнфордский университет. 2021.
2. Стэнфордская энциклопедия философии , статья Рекурсивные функции, раздел 1.7: «[Класс μ-рекурсивных функций] оказывается совпадающим с классом функций, вычислимых по Тьюрингу, введенным Аланом Тьюрингом, а также с классом λ-определимых функций, введенным Алонзо Чёрчем » .
3. Клини, Стивен С. (1936). «λ-определимость и рекурсивность». Duke Mathematical Journal . 2 (2): 340–352. doi :10.1215/s0012-7094-36-00227-2.
4. Тьюринг, Алан Матисон (декабрь 1937 г.). «Вычислимость и λ-определимость». Журнал символической логики . 2 (4): 153–163. doi :10.2307/2268280. JSTOR  2268280. S2CID  2317046.План доказательства на стр. 153: ^[3] ${\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 }}}$ ${\displaystyle \lambda {\mbox{-definable}}}$
5. Эндертон, Х.Б., Математическое введение в логику, Academic Press, 1972
6. Boolos, GS, Burgess, JP, Jeffrey, RC, Computability and Logic, Cambridge University Press, 2007
7. Jones, ND, Вычислимость и сложность: с точки зрения программирования, The MIT Press, Кембридж, Массачусетс, Лондон, Англия, 1997
8. Кфури, А. Дж., Р. Н. Молл и М. А. Арбиб, Программный подход к вычислимости, 2-е изд., Springer-Verlag, Берлин, Гейдельберг, Нью-Йорк, 1982
9. определено в Примитивно-рекурсивная функция#Соединители , Примитивно-рекурсивная функция#Предикат равенства и Примитивно-рекурсивная функция#Умножение
10. Стивен Коул Клини (январь 1943 г.). «Рекурсивные предикаты и квантификаторы» (PDF) . Труды Американского математического общества . 53 (1): 41–73. doi : 10.1090/S0002-9947-1943-0007371-8 .
11. Минский 1972, стр. 189.

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

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

• Булос, Джордж ; Берджесс, Джон ; Джеффри, Ричард (2002). "6.2 Минимизация". Вычислимость и логика (4-е изд.). Cambridge University Press. стр. 70–71. ISBN 9780521007580.

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

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