Ogólna funkcja rekurencyjna - General recursive function

W logice matematycznej i informatyki , w ogólnej funkcji rekurencyjnej , częściowego funkcji rekurencyjnej lub funkcja rekurencyjna jest częściowe funkcja z liczb naturalnych do liczb naturalnych, że to „obliczalny” w intuicyjnym sensie. Jeśli funkcja jest całkowita, nazywana jest również całkowitą funkcją rekurencyjną (czasami skracana do funkcji rekurencyjnej ). W teorii obliczalności wykazano, że funkcje rekurencyjne μ są dokładnie tymi funkcjami, które mogą być obliczone przez maszyny Turinga (jest to jedno z twierdzeń, które wspierają tezę Churcha-Turinga ). Funkcje rekurencyjne μ są ściśle związane z prymitywnymi funkcjami rekurencyjnymi , a ich indukcyjna definicja (poniżej) opiera się na pierwotnych funkcjach rekurencyjnych. Jednak nie każda całkowita funkcja rekurencyjna jest pierwotną funkcją rekurencyjną — najbardziej znanym przykładem jest funkcja Ackermanna .

Inne równoważne klasy funkcji to funkcje rachunku lambda i funkcje, które można obliczyć za pomocą algorytmów Markowa .

Podzbiór wszystkich sumy funkcji rekurencyjnej z wartościami {0,1} jest znana w teorii złożoności obliczeniowej , jako klasa złożoności R .

Definicja

Funkcje rekurencyjne μ (lub ogólne funkcje rekurencyjne ) są funkcjami częściowymi, które pobierają skończone krotki liczb naturalnych i zwracają pojedynczą liczbę naturalną. Są to najmniejsza klasa funkcji częściowych, która zawiera funkcje początkowe i jest zamknięta pod składem, rekurencją pierwotną i operatorem μ .

Najmniejsza klasa funkcji zawierająca funkcje inicjalne i zamknięte w ramach składu i pierwotnej rekurencji (tj. bez minimalizacji) to klasa pierwotnych funkcji rekurencyjnych . Chociaż wszystkie pierwotne funkcje rekurencyjne są całkowite, nie dotyczy to częściowych funkcji rekurencyjnych; na przykład minimalizacja funkcji następnika jest niezdefiniowana. Pierwotne funkcje rekurencyjne są podzbiorem wszystkich funkcji rekurencyjnych, które są podzbiorem częściowych funkcji rekurencyjnych. Na przykład można udowodnić , że funkcja Ackermanna jest całkowicie rekurencyjna i nie jest prymitywna.

Funkcje pierwotne lub „podstawowe”:

1. Funkcje stałe C^k
   _n: Dla każdej liczby naturalnej i każdej alternatywnej definicji zamiast tego używaj funkcji zerowej jako funkcji pierwotnej, która zawsze zwraca zero i buduje funkcje stałe z funkcji zerowej, funkcji następnika i operatora składu.${\displaystyle n\,}$${\displaystyle k\,}$
       ${\ Displaystyle C_ {n} ^ {k} (x_ {1}, \ ldots, x_ {k}) {\ stackrel {\ operatorname {def}} {=}} n}$
   
2. Funkcja następcy S:
       ${\ Displaystyle S (x) {\ stackrel {\ operatorname {def}} {=}} x + 1 \,}$
3. Funkcja projekcji (zwana również funkcją tożsamości ): Dla wszystkich liczb naturalnych, takich jak :${\ Displaystyle P_ {i} ^ {k}}$${\displaystyle ja,k}$${\displaystyle 1\leq i\leq k}$
       ${\ Displaystyle P_ {i} ^ {k} (x_ {1}, \ ldots, x_ {k}) {\ stackrel {\ operatorname {def}} {=}} x_ {i} \,.}$

Operatory ( dziedziną funkcji zdefiniowaną przez operator jest zbiór wartości argumentów w taki sposób, że każda aplikacja funkcji, która musi być wykonana podczas obliczeń, zapewnia dobrze zdefiniowany wynik):

1. Operator kompozycji (zwany także operatorem podstawienia ): Biorąc pod uwagę funkcję m-ary i funkcje m-k-ary : Oznacza to, że jest zdefiniowany tylko wtedy, gdy i wszystkie są zdefiniowane.${\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 {\ operatorname {def}} {=}} f, \ quad {\ tekst {gdzie}} \ 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. Operator rekurencji pierwotnej : Biorąc pod uwagę funkcję k -ary i funkcję k +2 -ary : Oznacza to, że jest zdefiniowany tylko wtedy, gdy i są zdefiniowane dla wszystkich${\ Displaystyle \ rho \,}$${\displaystyle g(x_{1},\ldots,x_{k})\,}$${\displaystyle h(y,z,x_{1},\ldots,x_{k})\,}$
       ${\ Displaystyle {\ zacząć {wyrównany} \ rho (g, h) i {\ stackrel {\ operatorname {def}} {=}} f \ quad {\ tekst {gdzie funkcja k + 1 -ary}} f { \text{ jest zdefiniowany przez}}\\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{wyrównany}}}$
   ${\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. Operator minimalizacji : Przy danej funkcji ( k +1)-ary, funkcja k- ary jest zdefiniowana przez: Intuicyjnie, minimalizacja szuka — zaczynając wyszukiwanie od 0 i kontynuując w górę — najmniejszego argumentu, który powoduje, że funkcja zwraca zero; jeśli nie ma takiego argumentu lub jeśli napotka się argument, dla którego f nie jest zdefiniowane, to wyszukiwanie nigdy się nie kończy i nie jest zdefiniowane dla tego argumentu ( Uwaga : Podczas gdy niektóre podręczniki używają zdefiniowanego tutaj operatora μ, inne lubią żądać μ-operator stosuje się do ogółu funkcji tylko. Mimo, że ogranicza to μ-operator w porównaniu z definicją podaną tutaj, klasa funkcji ľ-rekurencyjne pozostaje ten sam, co wynika z KLEENE w postaci normalnej twierdzenia (patrz poniżej ) Jedyna różnica polega na tym, że staje się nierozstrzygnięte, czy określona definicja funkcji definiuje funkcję μ-rekurencyjną, ponieważ nie można rozstrzygnąć, czy funkcja obliczalna (tj. μ-rekurencyjna) jest całkowita.)${\ Displaystyle \ mu \,}$${\displaystyle f(y,x_{1},\ldots,x_{k})\,}$${\ Displaystyle \ mu (f)}$
       ${\ Displaystyle {\ zacząć {wyrównany} \ mu (f) (x_ {1}, \ ldots, x_ {k}) = z {\ stackrel {\ operatorname {def}} {\ iff}} \ f (ja, 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}}}$
   ${\ Displaystyle \ mu (f)}$${\displaystyle (x_{1},\ldots,x_{k}).}$
   ${\displaystyle f}$

Silny równość operator może być użyty do porównania cząstkowe funkcji ľ-rekurencyjne. Jest to zdefiniowane dla wszystkich funkcji cząstkowych f i g tak, że ${\displaystyle \simeq}$

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

obowiązuje wtedy i tylko wtedy, gdy dla dowolnego wyboru argumentów obie funkcje są zdefiniowane i ich wartości są równe lub obie funkcje są niezdefiniowane.

Całkowita funkcja rekurencyjna

Ogólna funkcja rekurencyjna nazywa się całkowitą funkcją rekurencyjną, jeśli jest zdefiniowana dla każdego wejścia lub, równoważnie, jeśli może być obliczona przez całkowitą maszynę Turinga . Nie ma sposobu, aby w sposób obliczeniowy stwierdzić, czy dana ogólna funkcja rekurencyjna jest całkowita — patrz problem zatrzymania .

Równoważność z innymi modelami obliczalności

W równoważności modeli obliczalności rysuje się paralela między maszynami Turinga , które nie kończą się dla pewnych danych wejściowych, a nieokreślonym wynikiem dla tego wejścia w odpowiedniej częściowej funkcji rekurencyjnej. Nieograniczony operator wyszukiwania nie jest definiowany przez reguły pierwotnej rekurencji, ponieważ nie zapewniają one mechanizmu „nieskończonych pętli” (niezdefiniowanych wartości).

Twierdzenie o postaci normalnej

Normalna forma twierdzenie powodu Kleene mówi, że dla każdego k istnieją prymitywne rekurencyjne funkcje i takie, że dla każdej funkcja rekurencyjna z k zmiennych wolnych istnieje e takie, ż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 r \, T (y, e, x_ {1}, \ ldots, x_ {k}))}$.

Liczba e jest nazywana indeksem lub liczbą Gödla dla funkcji f . Konsekwencją tego wyniku jest to, że każda funkcja rekurencyjna μ może być zdefiniowana przy użyciu pojedynczego wystąpienia operatora μ zastosowanego do (całkowitej) pierwotnej funkcji rekurencyjnej.

Minsky zauważa, że zdefiniowany powyżej jest w istocie μ-rekurencyjnym odpowiednikiem uniwersalnej maszyny Turinga : ${\ Displaystyle U}$

Aby skonstruować U, należy napisać definicję ogólnej funkcji rekurencyjnej U(n, x), która poprawnie interpretuje liczbę n i oblicza odpowiednią funkcję x. skonstruowanie U bezpośrednio wymagałoby zasadniczo takiego samego wysiłku i zasadniczo tych samych pomysłów , jakie zainwestowaliśmy w skonstruowanie uniwersalnej maszyny Turinga

Symbolizm

W literaturze stosuje się wiele różnych symboli. Zaletą korzystania z symboliki jest wyprowadzenie funkcji przez „zagnieżdżenie” operatorów jeden w drugim, co jest łatwiejsze do zapisania w zwartej formie. Poniżej skrócimy ciąg parametrów x ₁ , ..., x _n jako x :

• Funkcja stała : Kleene używa „Cⁿ
  _q( x ) = q " i Boolos-Burgess-Jeffrey (2002) (BBJ) używają skrótu " const _n ( x ) = n ":

np. C⁷
₁₃ ( r, s, t, u, v, w, x ) = 13

np. const ₁₃ ( r, s, t, u, v, w, x ) = 13

• Funkcja następcy : Kleene używa x' i S jako „następca”. Ponieważ „następca” jest uważany za prymitywnego, większość tekstów używa apostrofu w następujący sposób:

S(a) = a +1 = _def a', gdzie 1 = _def 0', 2 = _def 0 ' ', itd.

• Funkcja tożsamości : Kleene (1952) używa „Uⁿ
  _ja" w celu wskazania funkcji tożsamości nad zmiennymi x _i ; BBJ używa funkcji tożsamości idⁿ
  _janad zmiennymi od x ₁ do x _n :

Uⁿ
_ja( x ) = idⁿ
_ja( x ) = x _i

np. U⁷
₃ = identyfikator⁷
₃ ( r, s, t, u, v, w, x ) = t

• Operator kompozycji (podstawiania) : Kleene używa pogrubionego S^m
  _n(nie mylić z jego S dla „następcy” ! ). Indeks górny „m” odnosi się do m- ^tej funkcji „f _m ”, podczas gdy indeks dolny „n” odnosi się do n- ^tej zmiennej „x _n ”:

Jeśli otrzymamy h( x )= g( f ₁ ( x ), ... , f _m ( x ) )

h( x ) = Sⁿ
_m(g, f ₁ , ... , f _m )

W podobny sposób, ale bez indeksów dolnych i górnych, BBJ pisze:

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

• Rekurencja pierwotna : Kleene używa symbolu „ R ⁿ (krok podstawowy, krok indukcyjny)”, gdzie n oznacza liczbę zmiennych, BBJ używa „Pr(krok podstawowy, krok indukcyjny)( x )”. Dany:

• krok podstawowy: h( 0, x )= f( x ), and
• krok indukcji: h( y+1, x ) = g( y, h(y, x ), x )

Przykład: prymitywna definicja rekurencji a + b:

• krok podstawowy: f( 0, a ) = a = U¹
  ₁(a)
• krok indukcji: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U³
  ₂(b,c,a))

R ² { U¹
₁(a), S [ (U³
₂( b, c, a ) ] }

Pr{ U¹
₁(a), S[ (U³
₂( b, c, a ) ] }

Przykład : Kleene podaje przykład, jak wykonać rekurencyjne wyprowadzenie f(b, a) = b + a (zauważ odwrócenie zmiennych aib). Zaczyna od 3 początkowych funkcji

1. S(a) = a'
2. U¹
   ₁(a) = a
3. U³
   ₂( b, c, a ) = c
4. g(b, c, a) = S(U³
   ₂(b, c, a)) = c'
5. krok podstawowy: h( 0, a ) = U¹
   ₁(a)

stopień indukcji: h( b', a ) = g( b, h( b, a ), a )

Przyjeżdża o:

a+b = R ² [ U¹
₁, S³
₁(S, U³
₂) ]

Przykłady

• Liczba Fibonacciego
• Funkcja McCarthy 91

Zobacz też

• Teoria rekurencji
• Rekurencja
• Rekurencja (informatyka)

Bibliografia

Zewnętrzne linki

• Wpis Stanford Encyclopedia of Philosophy
• Kompilator do przekształcania funkcji rekurencyjnej w równoważną maszynę Turinga