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

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

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

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

Определение

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

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

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

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

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

  1. Оператор композиции (также называемый оператором подстановки ): Дана m-ичная функция и m k-ичных функций : ∘ {\displaystyle \circ \,} час ( х 1 , … , х м ) {\displaystyle h(x_{1},\ldots ,x_{m})\,} г 1 ( х 1 , … , х к ) , … , г м ( х 1 , … , х к ) {\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}
    час ∘ ( г 1 , … , г м )   = г е ф   ф , где ф ( х 1 , … , х к ) = час ( г 1 ( х 1 , … , х к ) , … , г м ( х 1 , … , х к ) ) . {\displaystyle h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{где}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})).}
    Это означает, что определено только в том случае, если определены и . ф ( х 1 , … , х к ) {\displaystyle f(x_{1},\ldots ,x_{k})} г 1 ( х 1 , … , х к ) , … , г м ( х 1 , … , х к ) , {\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),} час ( г 1 ( х 1 , … , х к ) , … , г м ( х 1 , … , х к ) ) {\displaystyle h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))}
  2. Примитивный оператор рекурсии ρ : Даны k -арная функция и k +2-арная функция : г ( х 1 , … , х к ) {\displaystyle g(x_{1},\ldots ,x_{k})\,} h ( y , z , x 1 , … , x k ) {\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}
    ρ ( g , h )   = d e f   f where the k+1 -ary function  f  is defined by f ( 0 , x 1 , … , x k ) = g ( x 1 , … , x k ) f ( S ( y ) , x 1 , … , x k ) = h ( y , f ( y , x 1 , … , x k ) , x 1 , … , 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}}}
    Это означает, что определено только тогда, когда и определены для всех f ( y , x 1 , … , x k ) {\displaystyle f(y,x_{1},\ldots ,x_{k})} g ( x 1 , … , x k ) {\displaystyle g(x_{1},\ldots ,x_{k})} h ( z , f ( z , x 1 , … , x k ) , x 1 , … , x k ) {\displaystyle h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})} z < y . {\displaystyle z<y.}
  3. Оператор минимизации μ : Для ( k +1)-арной функции k -арная функция определяется как: f ( y , x 1 , … , x k ) {\displaystyle f(y,x_{1},\ldots ,x_{k})\,} μ ( f ) {\displaystyle \mu (f)}
    μ ( f ) ( x 1 , … , x k ) = z ⟺ d e f   f ( i , x 1 , … , x k ) > 0 for i = 0 , … , z − 1 and f ( z , x 1 , … , x k ) = 0 {\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 не определен, то поиск никогда не заканчивается и не определен для аргумента μ ( f ) {\displaystyle \mu (f)} ( x 1 , … , x k ) . {\displaystyle (x_{1},\ldots ,x_{k}).}

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

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

f ( x 1 , … , x k ) ≃ g ( x 1 , … , x l ) {\displaystyle f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})}

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

Примеры

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

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

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

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

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

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

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

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

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

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

f ( x 1 , … , x k ) ≃ U ( μ ( T ) ( e , x 1 , … , x k ) ) {\displaystyle f(x_{1},\ldots ,x_{k})\simeq U(\mu (T)(e,x_{1},\ldots ,x_{k}))} .

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

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

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

Символизм

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

  • Постоянная функция : Клини использует "Cн
    д    ( x ) = q " и Boolos-Burgess-Jeffrey (2002) (BBJ) используют сокращение " const n ( x ) = n ":
например С7
13( р, с, т, у, в, ш, х ) = 13
например, const 13 ( 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 1 до x n :
Ун
я( х ) = идентификаторн
я( х ) = х я
например U7
3= идентификатор7
3( р, с, т, у, в, ш, х ) = т
  • Оператор композиции (подстановки) : Клини использует жирный шрифт Sм
    н    (не путать с его S для «преемника» ! ). Верхний индекс «m» относится к m - й функции «f m », тогда как нижний индекс «n» относится к n -й переменной «x n »:
Если нам дано h( x )= g( f 1 ( x ), ... , f m ( x ) )
ч( х ) = Sн
м(г, ж 1 , ... , ж м )
Аналогичным образом, но без нижних и верхних индексов, BBJ пишет:
h( x' )= Cn[g, f 1 ,..., f m ]( x )
  • Примитивная рекурсия : Клини использует символ « R n (базовый шаг, шаг индукции)», где 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 = U1
    1    (а)
  • шаг индукции: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U3
    2    ( б, в, а ))
Р 2 { У1
1(а), С [ (U3
2( б, в, а ) ] }
Пр{ У1
1(а), S[ (U3
2( б, в, а ) ] }

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

  1. С(а) = а'
  2. У1
    1    (а) = а
  3. У3
    2    ( б, в, а ) = с
  4. г(б, с, а) = С(U3
    2    ( б, в, а )) = с'
  5. базовый шаг: h( 0, a ) = U1
    1    (а)
шаг индукции: h( b', a ) = g( b, h( b, a ), a )

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

а+б = Р2 [ У1
1, С3
1(С, У3
2) ]

Примеры

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

Ссылки

  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] λ -definable {\displaystyle \lambda {\mbox{-definable}}} ⟹ t r i v {\displaystyle {\stackrel {triv}{\implies }}} λ - K -definable {\displaystyle \lambda {\mbox{-}}K{\mbox{-definable}}} ⟹ 160 {\displaystyle {\stackrel {160}{\implies }}} Turing computable {\displaystyle {\mbox{Turing computable}}} ⟹ 161 {\displaystyle {\stackrel {161}{\implies }}} μ -recursive {\displaystyle \mu {\mbox{-recursive}}} ⟹ K l e e n e {\displaystyle {\stackrel {Kleene}{\implies }}} λ -definable {\displaystyle \lambda {\mbox{-definable}}}
  5. ^ Эндертон, Х.Б., Математическое введение в логику, Academic Press, 1972
  6. ^ ab Boolos, GS, Burgess, JP, Jeffrey, RC, Computability and Logic, Cambridge University Press, 2007
  7. ^ ab 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 Мински показывает, как создать μ-оператор с использованием модели регистровой машины , тем самым демонстрируя его эквивалентность общим рекурсивным функциям.
  • Запись в Стэнфордской энциклопедии философии
  • Компилятор для преобразования рекурсивной функции в эквивалентную машину Тьюринга
Retrieved from "https://en.wikipedia.org/w/index.php?title=General_recursive_function&oldid=1250783941"