μ-рекурзивна функција

U matematičkoj logici i informatici, μ-rekurzivne funkcije su klase parcijalnih funkcija od prirodnih brojeva do prirodnih brojeva koji su "kompatibilni" na intuitivan način. U stvari, u teoriji izračunljivosti je pokazano da su μ rekurzivne funkcije zapravo funkcije koje mogu da se izračunaju Tjuringovim mašinama. μ-rekurzivne funkcije su blisko povezane sa primitivnim rekurzivnim funkcijama, a njihova induktivna definicija se oslanja na primitivne rekurzivne funkcije. Međutim, nije svaka μ-rekurzivna funkcija primitivna rekurzivna funkcija—najpoznatiji primer je Akermanova funkcija.

Ostali ekvivalente klase funkcija su λ-rekurzivne funkcije i funkcije koje mogu biti izračunate preko Markov algoritama.

Skup svih rekurzivnih funkcija poznat je kao R u računarskoj teoriji kompleksnosti.

Definicija

μ-rekurzivne funkcije (ili parcijalna μ-rekurzivna funkcija) su parcijalne funkcije koje uzimaju konačne zapise prirodnih brojeva i vrate jedan prirodan broj. One su najmanja klasa parcijalnih funkcija koje uključuju početne funkcije i zatvorene su pod sastavom, primitivne rekurzije, i operacije μ.

Najmanja klasa funkcija, uključujući početne funkcije i zatvorene pod sastavom i primitivnom rekurzijom (tj. bez minimiziranja) je klasa primitivnih rekurzivnih funkcija. Dok su sve primitivne rekurzivne funkcije potpune, to nije tačno kod parcijalnih rekurzivnih funkcija; na primer, minimiziranje nasleđene funkcije je nedefinisano. Primitivne rekurzivne funkcije su podskup ukupnih rekurzivnih funkcija, koje su odvojene od parcijalnih rekurzivnih funkcija. Na primer, Akermanova funkcija može dokazati da je ukupan broj rekurzivan, ali ne i primitivan.

Inicijalne  ili "osnovne" funkcije: (Sledi indeksiranje po Klinu (1952) pp. 219. Za više informacija o različitim simbolizmima koji se nalaze u literaturi videti ispod Simbolika)

1. Konstantna funkcija: Za svaki prirodan broj $n\,$ i svako $k\,$:

   $f(x_{1},\ldots ,x_{k})=n\,$.

   Alternativne definicije koriste kompozicije u funkciji nasleđivanja i koriste nula funkciju, da se uvek vraća na nulu, na mestu stalne funkcije.

2.   Funkcija nasleđivanja S:

   $S(x){\stackrel {\mathrm {def} }{=}}f(x)=x+1\,$

3. Projekcija funkcija $P_{i}^{k}$ (takođe se naziva identitet funkcije $I_{i}^{k}$): Za sve prirodne brojeve $i,k\,$ takve da je $1\leq i\leq k$:

   $P_{i}^{k}{\stackrel {\mathrm {def} }{=}}f(x_{1},\ldots ,x_{k})=x_{i}$.

Operacije:

1. Operacija slaganja $\circ \,$ (takođe se zove operacija zamene): Data je m-arna funkcija $h(x_{1},\ldots ,x_{m})\,$ i m k-arne funkcije $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(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))\,$.

2.   Primitivna rekurzivna operacija $\rho \,$: Data je k-arna funkcija $g(x_{1},\ldots ,x_{k})\,$ i k+2 -arna funkcija $h(y,z,x_{1},\ldots ,x_{k})\,$:

   ${\begin{aligned}\rho (g,h)&{\stackrel {\mathrm {def} }{=}}f(y,x_{1},\ldots ,x_{k})\quad {\rm {where}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(y+1,x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,\end{aligned}}$.

3. Operacija minimizacije $\mu \,$: Data je (k+1)-arna potpuna funkcija $f(y,x_{1},\ldots ,x_{k})\,$:

   ${\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(z,x_{1},\ldots ,x_{k})&=0\quad {\text{and}}\\f(i,x_{1},\ldots ,x_{k})&>0\quad {\text{for}}\ i=0,\ldots ,z-1.\end{aligned}}$

   Intuitivno, minimiziranje traži—početak potrage od 0 i nastavlja nagore—najmanji argument uzrokuje funkciju da se vrati na nulu; ako takav argument ne postoji, potraga nikad prestaje.

Operacija jake jednakosti $\simeq$ može da se koristi za poređenje parcijalne μ-rekurzivne funkcije. Ovo je definisano za sve parcijalne funkcije f i g tako da je

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

važi ako i samo ako za bilo koji izbor argumenata bilo koje od dve funkcije su definisane i njihove vrednosti su jednake ili obe funkcije su nedefinisane.

Ekvivalentnost sa drugim modelima izračunljivosti

U ekvivalentnosti modela izračunljivosti, paralelno je nacrtan između Tjuringovih mašina koje ne završavaju za određene ulaze i neodređeni rezultat za taj ulaz u odgovarajućoj parcijalnoj rekurzivnoj funkciji. Neograničena pretraga operacija nije definicana pravilima primitivne rekurzije i oni ne pružaju mehanizam za "beskonačne petlje" (nedefinisane vrednosti).

Normalna forma teorema

Normalan oblik teorema kako Klini kaže da je za svaki k postoje primitivne rekurzivne funkcije $U(y)\!$ i $T(y,e,x_{1},\ldots ,x_{k})\!$ tako za svaku μ-rekurzivnu funkciju $f(x_{1},\ldots ,x_{k})\!$ sa k slobodnom varijablom takvom da postoji e takvo da

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

Broj e naziva se indeks ili Gedelov broj za funkciju f. Posledica ovog rezultata je da bilo koja μ-rekurzivna funkcija bude definisana upotrebom jedne instance operacije μ primenjene na (ukupne) primitivne rekurzivne funkcije.

Minski (1967) je primetio (kao što to čini Bulos-Burges-Džefri (2002) pp. 94–95) da je U  definisano u suštini μ-rekurzivno ekvivalento univerzalnoj Tjuringovoj mašini:

Izgraditi U da napiše definiciju opšte-rekurzivne funkcije U(n, x) koja ispravno tumači broj n i izračunava odgovarajuću funkciju od x. Pod izgradnjom u suštini se  podrazumeva istu količina truda, u suštini iste ideje, kao što smo investirali u izgradnju univerzalne Tjuringove mašine. (italik u originalu, Minski (1967). str. 189.)

Simbolika

Jedan broj različitih simbola se koristi u literaturi. Prednost korišćenja simbola je izvođenje funkcija "ugnežđenja" operacija jedne u drugu radi lakšeg pisanja u kompaktnoj formi. U nastavku ćemo skratiti niz parametara x₁, ..., x_n kao x:

• Konstantna funkcija: Klini koristi " C_qⁿ(x) = q " i Bulos-Burges-Džefri (2002) (B-B-J) koristi skraćenicu " const_n( x) = n ":

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

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

• Funkcija nasleđivanja: Klini koristi x' i S za "nalseđivanje". Kako se "nasleđivanje" smatra primitivnim, u većini tekstova se koristi apostrof na sledeći način:

S(a) = a +1 =_def a', gde je 1 =_def 0', 2 =_def 0 ' ', etc.

• Funkcija identiteta: Klini (1952) koristi " U_iⁿ " za indikaciju identiteta funkcije nad promenljivom x_i; B-B-Dž koristi funkciju identiteta id_iⁿ od promenljive x₁ do x_n:

U_iⁿ( x ) = id_iⁿ( x ) = x_i

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

• Operacija slaganja (zamena): Klini koristi S_n^m (ne treba mešati sa njegovim S za "nasleđivanje" ! ). Indeks "m" se odnosi na m^th funkcije "f_m",  "n" se odnosi na n^th promenljive "x_n":

Dato je h( x )= g( f₁(x), ... , f_m(x) )

h(x) = S_mⁿ(g, f₁, ... , f_m )

Na sličan način, ali bez indeksa i stepena, B-B-Dž piše:

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

• Primitivna rekurzija: Klini koristi simbol " Rⁿ(osnovni korak, induktivni korak) "gde n pokazuje broj promenljivih, B-B-Dž koristi " Pr(osnovni korak, induktivni korak)(x)". Dato je:

• osnovni korak: h( 0, x )= f( x ), i

• induktivni korak: h( y+1, x ) = g( y, h(y, x),x )

Primer: definicija primitivne rekurzije a + b:

• osnovni korak: f( 0, a ) = a = U₁¹(a)
• induktivni korak: 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 ) ] }

Primer: Klini daje primer kako da se izvrši rekurzivna derivacija od f(b, a) = b + a (preokret promenljivih a i b). On počinje sa 3 početne funkcije

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. osnovni korak: h( 0, a ) = U₁¹(a)

induktivni korak: h( b', a ) = g( b, h( b, a ), a )

Svodi se na:

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

Primeri

• Fibonačijev niz
  
• Makarti 91 funkcija
  

Vidi još

• Teorija izračunljivosti
  
• Rekurzija
• Rekurzija (kompjuterske nauke)
  

Literatura

• Stephen Kleene (1952) Introduction to Metamathematics. Walters-Noordhoff & North-Holland, with corrections (6th imprint 1971); Tenth impression. 1991. ISBN 978-0-7204-2103-3..
• Soare, R. Recursively enumerable sets and degrees. Springer-Verlag 1987.
• Marvin L. Minsky (1967), Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J.

On pages 210-215 Minsky shows how to create the μ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.

• George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70–71.

Spoljašnje veze

• Stanford Encyclopedia of Philosophy entry
• A compiler for transforming a recursive function into an equivalent Turing machine