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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

Целочисленный квадратный корень из $x$ можно определить как наименьшее значение $z$ такое, что $(z+1)^{2}>x$ . Используя оператор минимизации, общее рекурсивное определение имеет вид $\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}))$ , где $Not$ , $Gt$ и $Mul$ — логическое отрицание , «больше» и умножение, ^[9] соответственно. Фактически, $(\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 тогда и только тогда, когда $S(z)*S(z)>x$ держит. Следовательно $\operatorname {Isqrt} (x)$ является наименьшим $z$ таким, что $S(z)*S(z)>x$ держит. отрицания Юнктор $Not$ необходим, поскольку $Gt$ кодирует истину с помощью 1 , а $μ$ ищет 0 .

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

^{[ нужен пример ]}

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

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

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

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

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

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

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

.

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

Минский наблюдает за $U$ Определенное выше, по сути, является μ-рекурсивным эквивалентом универсальной машины Тьюринга :

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

Символизм

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

Постоянная функция : Клини использует «C ^н
_q ( x ) = q" и Булос-Берджесс-Джеффри (2002) (BBJ) используют аббревиатуру "const _n ( x ) = n":

например С ⁷
₁₃ ( р, с, т, ты, v, ш, х) = 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 ^н
_i ", чтобы указать функцию тождества над переменными x _i ; BBJ использует идентификатор функции тождества ^н
_i над переменными от x ₁ до x _n :

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

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

Оператор композиции (замены) : Клини использует жирный шрифт S. ^м
_n (не путать с его S, обозначающим «преемник» ! ). Верхний индекс «м» относится к м. ^й функции «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 ³
₂ ( б, в, а ) ] }

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

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

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

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

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

а+б = Р ²[У ¹
₁ , С ³
₁ (С, У ³
₂) ]

Примеры

См. также

Ссылки

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

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

[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: $\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 }}$ ^[3] $\lambda {\mbox{-definable}}$

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

[Boolos.Burgess.Jeffrey.2007-6] Jump up to: ^а ^б Булос, Г.С., Берджесс, Дж.П., Джеффри, Р.К., Вычислимость и логика, Cambridge University Press, 2007 г.

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

[8] Кфури, А.Дж., Р.Н. Молл и М.А. Арбиб, Программный подход к вычислимости, 2-е изд., Springer-Verlag, Берлин, Гейдельберг, Нью-Йорк, 1982 г.

[9] определено в Примитивная рекурсивная функция#Соединители , Примитивная рекурсивная функция#Предикат равенства и Примитивная рекурсивная функция#Умножение

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

[FOOTNOTEMinsky1972189-11] Минский 1972 , стр. 189.

[1]

[2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[3]