Ogólna funkcja rekurencyjna

W logice matematycznej i informatyce , ogólna funkcja rekurencyjna , częściowa funkcja rekurencyjna lub funkcja μ-rekurencyjna to funkcja częściowa od liczb naturalnych do liczb naturalnych, która jest „obliczalna” w sensie intuicyjnym - jak również formalnym . Jeśli funkcja jest całkowita, jest również nazywana całkowitą funkcją rekurencyjną (czasami skracaną do funkcji rekurencyjnej ). W teorii obliczalności , pokazano, że funkcje μ-rekurencyjne są dokładnie funkcjami, które mogą być obliczone przez maszyny Turinga (jest to jedno z twierdzeń wspierających tezę Churcha-Turinga ). Funkcje μ-rekurencyjne są blisko spokrewnione z prymitywnymi funkcjami rekurencyjnymi , a ich definicja indukcyjna (poniżej) opiera się na definicji prymitywnych funkcji rekurencyjnych. Jednak nie każda całkowita funkcja rekurencyjna jest prymitywną funkcją rekurencyjną — najbardziej znanym przykładem jest funkcja Ackermanna .

Innymi równoważnymi klasami funkcji są funkcje rachunku lambda i funkcje, które można obliczyć za pomocą algorytmów Markowa .

Podzbiór wszystkich całkowitych funkcji rekurencyjnych o wartościach w ${0,1}$ jest znany w teorii złożoności obliczeniowej jako klasa złożoności R .

Definicja

Funkcje μ-rekurencyjne (lub ogólne funkcje rekurencyjne ) to funkcje częściowe, które pobierają skończone krotki liczb naturalnych i zwracają pojedynczą liczbę naturalną. Są najmniejszą klasą funkcji częściowych, która obejmuje funkcje początkowe i jest zamknięta w złożeniu, prymitywnej rekurencji i operatorze μ .

Najmniejszą klasą funkcji obejmującą funkcje początkowe i domknięte pod złożeniem oraz pierwotną rekurencję (tj. bez minimalizacji) jest klasa prymitywnych funkcji rekurencyjnych . Chociaż wszystkie prymitywne funkcje rekurencyjne są całkowite, nie dotyczy to częściowych funkcji rekurencyjnych; na przykład minimalizacja funkcji następcy jest niezdefiniowana. Prymitywne funkcje rekurencyjne są podzbiorem całkowitych funkcji rekurencyjnych, które są podzbiorem częściowych funkcji rekurencyjnych. Na przykład można udowodnić, funkcja Ackermanna jest całkowicie rekurencyjna i nie jest prymitywna.

Funkcje prymitywne lub „podstawowe”:

Funkcje stałe $do k n k$ : Dla każdej liczby naturalnej $n$ i każdego $do$

$Displaystyle C_ {n} ^ {k} (x_ {1}, \ ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n}$

Alternatywne definicje używają zamiast funkcji zerowej jako funkcję pierwotną, która zawsze zwraca zero, i zbuduj funkcje stałe z funkcji zerowej, funkcji następcy i operatora kompozycji.
Następnik funkcji S:
${\ Displaystyle S (x) \ {\ stackrel {\ operatorname {def}} {=}} \ x + 1 \,}$
Funkcja projekcji $) :$ zwana także funkcją tożsamości ${\ displaystyle 1 \leq ja\leq k}$ wszystkich liczb naturalnych ${\ displaystyle i, k}$ , że :
${\ Displaystyle P_ {i} ^ {k} (x_ {1}, \ ldots, x_ {k}) \ {\ stackrel {\ operatorname {def}}} {=}} \ x_ {i} \,.}$

Operatory ( dziedziną funkcji zdefiniowaną przez operatora jest zbiór wartości argumentów takich, że każde zastosowanie funkcji, które musi być wykonane podczas obliczeń, daje dobrze zdefiniowany wynik):

Operator kompozycji ${\ Displaystyle \ circ \,}$ (nazywany także operatorem podstawienia ): Biorąc pod uwagę funkcję m-ary , ${\ Displaystyle h (x_ {1}, \ ldots, x_ { m})\,}$ i m k-funkcje ${\ 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}}).}$

Oznacza to, że ${\ Displaystyle f (x_ {1}, \ ldots, x_ {k})}$ jest zdefiniowany tylko wtedy, gdy ${\ Displaystyle g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m }(x_{1},\ldots ,x_{k}),}$ i ${\ Displaystyle h (g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k}) )}$ są zdefiniowane.
Prymitywny operator rekurencji $ρ$ : Biorąc pod uwagę funkcję k -ary sol ${\ Displaystyle g (x_ {1}, \ ldots, x_ {k}) \,}$ k + 2 - funkcja ${\ Displaystyle h (y, z, x_ {1}, \ ldots, x_ {k}) \,}$ :

${\ Displaystyle {\ rozpocząć {wyrównane} \ rho (g, h) & \ {\ 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{aligned}}}$

Oznacza to, że ${\ Displaystyle f (y, x_ {1}, \ ldots, x_ {k})}$ jest zdefiniowany tylko wtedy, gdy ${\ Displaystyle g (x_ {1} ,\ldots ,x_{k})}$ i ${\ Displaystyle h (z, f (z, x_ {1}, \ ldots, x_ {k}), x_ {1}, \ ldots, x_ {k})} są zdefiniowane$ dla wszystkich ${\ Displaystyle Z <y.}$
Operator minimalizacji $μ$ : Biorąc pod uwagę funkcję ar ( k + 1 ) ${\ Displaystyle f (y, x_ {1}, \ ldots, x_ {k}) \,}$ , funkcja k -ary
${\ Displaystyle {\ rozpocząć {wyrównane} \ mu (f) (x_ {1}, \ ldots, x_ {k}) = z {\ stackrel {\ operatorname {def}}} {\ if}} \ f (i, x_{1},\ldots,x_{k})&>0\quad {\text{for}}\quad i=0,\ldots,z-1\quad {\text{i}}\\f( z,x_{1},\ldots ,x_{k})&=0\quad \end{wyrównane}}}$
przez $_$

Intuicyjnie, minimalizacja szuka — rozpoczynając wyszukiwanie od 0 i kontynuując w górę — najmniejszego argumentu, który powoduje, że funkcja zwraca zero; $jest$ ma takiego argumentu lub jeśli napotka się argument, dla którego ${\ Displaystyle (x_ {1}, \ ldots, x_ {k}).}$ $nie$ jest zdefiniowane, to wyszukiwanie nigdy się nie kończy i zdefiniowane dla argumentu

Podczas gdy niektóre podręczniki używają operatora μ zgodnie z definicją tutaj, inne wymagają, aby operator μ był stosowany tylko do funkcji całkowitych $f$ . Chociaż ogranicza to operatora μ w porównaniu z podaną tutaj definicją, klasa funkcji μ-rekurencyjnych pozostaje taka sama, co wynika z twierdzenia o postaci normalnej Kleene'a (patrz poniżej ) . Jedyna różnica polega na tym, że staje się nierozstrzygalne, czy określona definicja funkcji definiuje funkcję μ-rekurencyjną, tak jak nierozstrzygalne jest, czy funkcja obliczalna (tj. μ-rekurencyjna) jest całkowita.

Operatora silnej równości $można$ do porównania częściowych funkcji μ-rekurencyjnych . Jest to zdefiniowane dla wszystkich funkcji cząstkowych f i g tak, że

{\ 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 albo obie funkcje są zdefiniowane, a ich wartości są równe, albo obie funkcje są niezdefiniowane.

Przykłady

Przykłady nieobejmujące operatora minimalizacji można znaleźć w Primitive recursive function#Examples .

Poniższe przykłady mają na celu tylko zademonstrowanie użycia operatora minimalizacji; można je również zdefiniować bez niego, choć w bardziej skomplikowany sposób, ponieważ wszystkie są prymitywnie rekurencyjne.

Całkowity pierwiastek kwadratowy z $x$ można zdefiniować jako najmniejszą $z$ taką, że ${\ Displaystyle (z + 1) ^ {2}> x}$ . Używając operatora minimalizacji, ogólną definicją rekurencyjną jest ${\ Displaystyle \ nazwa operatora {Isqrt} = \ mu (\ nazwa operatora {Nie} \ circ \ nazwa operatora {Gt} \ circ (\ nazwa operatora {Mul} \ circ (S \ circ P_ {1} ^ {2},S\circ P_{1}^{2}),P_{2}^{2}))}$ , gdzie $Not$ , $Gt$ i $Mul$ to odpowiednio logiczna negacja , większa niż i mnożenie. Faktycznie, 0 ${\ 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)}$ jest wtedy i tylko wtedy, gdy ${\ Displaystyle S (z) * S (z)> x}$ trzyma. Stąd ${\ Displaystyle \ operatorname {Isqrt} (x)}$ jest najmniejszą $z$ taką, że ${\ Displaystyle S (z) * S (z)> x}$ posiada. Złącze negacji $Not$ jest potrzebne, ponieważ $Gt$ koduje prawdę przez 1 0 , podczas gdy $μ$ szuka .

Poniższe przykłady definiują ogólne funkcje rekurencyjne, które nie są prymitywnymi funkcjami rekurencyjnymi; stąd nie mogą uniknąć użycia operatora minimalizacji.

^{[ potrzebny przykład ]}

Całkowita funkcja rekurencyjna

Ogólna funkcja rekurencyjna jest nazywana 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 możliwości obliczeniowego stwierdzenia, czy dana ogólna funkcja rekurencyjna jest całkowita — patrz problem z zatrzymaniem .

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

W równoważności modeli obliczalności rysuje się paralelę między maszynami Turinga , które nie kończą się dla pewnych danych wejściowych, a niezdefiniowanym wynikiem dla tego wejścia w odpowiedniej częściowej funkcji rekurencyjnej. Nieograniczonego operatora wyszukiwania nie można zdefiniować za pomocą reguł rekurencji pierwotnej, ponieważ nie zapewniają one mechanizmu „nieskończonych pętli” (niezdefiniowanych wartości).

Twierdzenie o postaci normalnej

Twierdzenie o postaci normalnej ze względu na Kleene mówi, że dla każdego $i$ $T (y,e,x_{1},\ldots ,x_{k})\!}$ prymitywne funkcje rekurencyjne y takie, że dla dowolnej funkcji μ-rekurencyjnej ${\ Displaystyle f (x_ {1}, \ ldots, x_ {k}) \!}$ z k wolnymi zmiennymi istnieje e takie, że

{\ Displaystyle f (x_ {1}, \ ldots, x_ {k}) \ simeq U(\mu y\,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 dowolną funkcję μ-rekurencyjną można zdefiniować za pomocą pojedynczego wystąpienia operatora μ zastosowanego do (całkowitej) pierwotnej funkcji rekurencyjnej.

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

Skonstruować U to zapisać definicję funkcji ogólnie rekurencyjnej U(n, x), która poprawnie interpretuje liczbę n i oblicza odpowiednią funkcję x. bezpośrednie zbudowanie U wymagałoby zasadniczo takiego samego wysiłku i zasadniczo tych samych pomysłów , ile zainwestowaliśmy w zbudowanie uniwersalnej maszyny Turinga

Symbolizm

W literaturze używa się wielu różnych symboli. Zaletą stosowania symboliki jest wyprowadzenie funkcji przez „zagnieżdżanie” operatorów jeden w drugim, co jest łatwiejsze do zapisania w zwartej formie. W dalszej części ciąg parametrów x ₁ , ..., x _n jest oznaczany skrótem x :

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

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

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

Funkcja następnika : Kleene używa x' i S dla określenia „Następca”. Ponieważ „następca” jest uważany za prymitywny, 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
ⁿ_i ” do wskazania funkcji tożsamości na zmiennych x _i ; BBJ użyj funkcji tożsamości id
ⁿ_i nad zmiennymi od x ₁ do x _n :

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

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

Operator składu (substytucji) : Kleene używa pogrubionej litery S
^m_n (nie mylić z jego S jak „następca” ! ). 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 mamy dane 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 napisz:

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 ), oraz
krok indukcyjny: 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 indukcyjny: 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, do, za ) ] }

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

Przykład : Kleene podaje przykład, jak wykonać rekurencyjne wyprowadzenie f(b, a) = b + a (zwróć uwagę na odwrócenie zmiennych aib). Zaczyna z 3 początkowymi funkcjami

S(a) = a'
U
¹₁ (a) = za
U
³₂ ( b, do, za ) = do
g(b, c, a) = S(U
³₂ ( b, c, a )) = c'
krok podstawowy: h( 0, a ) = U
¹₁ (a)

krok indukcyjny: h( b', a ) = g( b, h( b, a ), a )

Przyjeżdża o:

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

Przykłady

Zobacz też

Kleene, Stephen (1991) [1952]. Wprowadzenie do metamatematyki . Walters-Noordhoff i Holandia Północna. ISBN 0-7204-2103-9 .
Soare, R. (1999) [1987]. Rekurencyjnie przeliczalne zbiory i stopnie: badanie funkcji obliczalnych i zbiorów generowanych obliczeniowo . Springer-Verlag. ISBN 9783540152996 .
Minsky, Marvin L. (1972) [1967]. Obliczenia: maszyny skończone i nieskończone . Prentice Hall. s. 210–5. ISBN 9780131654495 .

Na stronach 210-215 Minsky pokazuje, jak stworzyć operatora μ za pomocą modelu maszyny rejestrowej , demonstrując w ten sposób jego równoważność z ogólnymi funkcjami rekurencyjnymi.

Boolos, George ; Burgess, Jan ; Jeffrey, Richard (2002). „6.2 Minimalizacja” . Obliczalność i logika (wyd. 4). Wydawnictwo Uniwersytetu Cambridge. s. 70–71. ISBN 9780521007580 .

Linki zewnętrzne