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

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

В математической логике и информатике общая рекурсивная функция , частично рекурсивная функция или μ-рекурсивная функция — это частичная функция преобразования натуральных чисел в натуральные числа, которая «вычислима» как в интуитивном, так и в формальном смысле . Если функция тотальная, ее также называют тотальной рекурсивной функцией (иногда сокращают до рекурсивной функции ). ^[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})}$

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

Примеры

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

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

• Целочисленный квадратный корень из 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^п
  _q( x ) = q " и Булос-Берджесс-Джеффри (2002) (BBJ) используют аббревиатуру " const _n ( x ) = n ":

например С⁷
₁₃( р, с, т, ты, v, ш, 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 ' ' и т. д.

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

ты^н
_я( х ) = идентификатор^н
_я( Икс ) знак равно Икс _я

например, У⁷
₃= идентификатор⁷
₃( р, с, т, ты, v, ш, Икс) = т

• Оператор композиции (замены) : Клини использует жирный шрифт 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³
  ₂( б, в, а ))

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

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

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

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

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

Он приезжает:

а+b = R2 ^[ U¹
₁, С³
₁(С, У³
₂) ]

Примеры

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

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

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

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

1. «Рекурсивные функции». Стэнфордская энциклопедия философии . Лаборатория метафизических исследований Стэнфордского университета. 2021.
2. Стэнфордская энциклопедия философии , Рекурсивные функции входа, раздел 1.7: «[Класс µ-рекурсивных функций] совпадает с классом функций, вычислимых по Тьюрингу, введенными Аланом Тьюрингом, а также с классом λ -определяемые функции, введенные Алонсо Чёрчем » .
3. Клини, Стивен С. (1936). «λ-определимость и рекурсивность». Математический журнал Дьюка . 2 (2): 340–352. дои : 10.1215/s0012-7094-36-00227-2.
4. Тьюринг, Алан Мэтисон (декабрь 1937 г.). «Вычислимость и λ-определимость». Журнал символической логики . 2 (4): 153–163. дои : 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. Эндертон, HB, Математическое введение в логику, Academic Press, 1972
6. Булос, Г.С., Берджесс, Дж.П., Джеффри, Р.К., Вычислимость и логика, Cambridge University Press, 2007 г.
7. Джонс, Н.Д., Вычислимость и сложность: с точки зрения программирования, MIT Press, Кембридж, Массачусетс, Лондон, Англия, 1997.
8. Кфури, А.Дж., Р.Н. Молл и М.А. Арбиб, Программный подход к вычислимости, 2-е изд., Springer-Verlag, Берлин, Гейдельберг, Нью-Йорк, 1982 г.
9. определено в Примитивная рекурсивная функция#Соединители , Примитивная рекурсивная функция#Предикат равенства и Примитивная рекурсивная функция#Умножение
10. Стивен Коул Клини (январь 1943 г.). «Рекурсивные предикаты и кванторы» (PDF) . Труды Американского математического общества . 53 (1): 41–73. дои : 10.1090/S0002-9947-1943-0007371-8 .
11. Минский 1972, стр. 189.

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

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

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

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

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