Teorema recursivității lui Kleene

În teoria calculabilității , teoremele recursive ale lui Kleene sunt două rezultate fundamentale referitoare la aplicarea de funcții calculabile asupra lor. Teoremele au fost dovedite pentru prima dată de Stephen Kleene în 1938.

Cele două teoreme ale recursivității pot fi aplicate pentru a construi puncte fixe ale anumitor operații pe funcții calculabile, pentru a genera quines și pentru a construi funcții definite prin definiție recursivă .

A doua teoremă a recursiunii

A doua teoremă a recursiunii este strâns legată de definițiile funcțiilor calculabile date de recursivitate. Deoarece este mai cunoscut decât prima teoremă a recursiunii, se numește pur și simplu teorema recursivității . Teza sa se referă la numerotarea standard Gödel φ a funcțiilor parțiale recursive , în care funcția corespunzătoare indicelui e este $\varphi _{e}$ ${\ displaystyle \ varphi _ {e}}$ $\ varphi_e$ .

A doua teoremă a recursiunii : Dacă F este o funcție recursivă, atunci există un index și astfel încât

\varphi _{e}\simeq \varphi _{F(e)}

{\ displaystyle \ varphi _ {e} \ simeq \ varphi _ {F (e)}}

{\ displaystyle \ varphi _ {e} \ simeq \ varphi _ {F (e)}}

.

Unde este $\varphi _{e}\simeq \varphi _{F(e)}$ ${\ displaystyle \ varphi _ {e} \ simeq \ varphi _ {F (e)}}$ ${\ displaystyle \ varphi _ {e} \ simeq \ varphi _ {F (e)}}$ înseamnă că, pentru fiecare n , să fie $\varphi _{e}(n)$ ${\ displaystyle \ varphi _ {e} (n)}$ ${\ displaystyle \ varphi _ {e} (n)}$ acea $\varphi _{F(e)}(n)$ ${\ displaystyle \ varphi _ {F (e)} (n)}$ ${\ displaystyle \ varphi _ {F (e)} (n)}$ sunt definite și valorile lor sunt aceleași sau ambele sunt nedefinite.

Exemplu

Să presupunem că g și h sunt funcții totale recursive care sunt utilizate pentru definiția recursivă a unei funcții f :

f(0,y)\simeq g(y)

{\ displaystyle f (0, y) \ simeq g (y)}

{\ displaystyle f (0, y) \ simeq g (y)}

f(x+1,y)\simeq h(f(x,y),x,y)

{\ displaystyle f (x + 1, y) \ simeq h (f (x, y), x, y)}

{\ displaystyle f (x + 1, y) \ simeq h (f (x, y), x, y)}

Această definiție recursivă poate fi convertită într-o funcție calculabilă F (e) care ia indexul unui program e și returnează un index F (e) astfel încât

\varphi _{F(e)}(0,y)\simeq g(y)

{\ displaystyle \ varphi _ {F (e)} (0, y) \ simeq g (y)}

{\ displaystyle \ varphi _ {F (e)} (0, y) \ simeq g (y)}

\varphi _{F(e)}(x+1,y)\simeq h(\varphi _{e}(x,y),x,y)

{\ displaystyle \ varphi _ {F (e)} (x + 1, y) \ simeq h (\ varphi _ {e} (x, y), x, y)}

{\ displaystyle \ varphi _ {F (e)} (x + 1, y) \ simeq h (\ varphi _ {e} (x, y), x, y)}

În acest context, un punct fix al lui F este un indice și astfel încât $\varphi _{e}\simeq \varphi _{F(e)}$ ${\ displaystyle \ varphi _ {e} \ simeq \ varphi _ {F (e)}}$ ${\ displaystyle \ varphi _ {e} \ simeq \ varphi _ {F (e)}}$ ; funcția calculată de un astfel de e va fi o soluție a ecuației recursive originale. Teorema recursiunii stabilește existența unui astfel de punct fix, presupunând că F este calculabil și este uneori numită teorema punctului fix (a lui Kleene ) din acest motiv. Teorema nu garantează că e este indicele pentru cel mai mic punct fix din ecuația recursivă; aceasta este sarcina primei teoreme a recursiunii, descrisă mai jos.

Cerere de a chine

O interpretare informală a celei de-a doua teoreme a recursiunii este că orice funcție parțială recursivă poate oferi un indice de sine. Aceasta rezultă din următorul corolar al teoremei.

Corolar . Pentru fiecare funcție parțială recursivă Q ( x , y ) există un index p astfel încât

\varphi _{p}\simeq \lambda y.Q(p,y)

{\ displaystyle \ varphi _ {p} \ simeq \ lambda yQ (p, y)}

{\ displaystyle \ varphi _ {p} \ simeq \ lambda y.Q (p, y)}

.

Corolarul este prezentat prin plasare $F(p)$ ${\ displaystyle F (p)}$ $F (p)$ o funcție care returnează un index pentru $\lambda y.Q(p,y)$ ${\ displaystyle \ lambda yQ (p, y)}$ ${\ displaystyle \ lambda y.Q (p, y)}$ .

Corolarul arată că pentru fiecare funcție calculabilă Q a două argumente, există un program care ia un argument și calculează Q cu acel program ca prim argument și parametrul trecut ca al doilea. Rețineți că acest program este capabil să își genereze indexul pornind de la informațiile conținute în program; nu are nevoie de resurse externe pentru a găsi indexul.

Un exemplu clasic este funcția Q ( x , y ) = x . Indicele corespunzător p în acest caz produce o funcție calculabilă care produce propriul indice pentru fiecare valoare la care se aplică. Atunci când sunt înțelese ca programe de calculator, astfel de indici sunt numiți quines .

Funcții fără puncte fixe

O funcție F astfel încât $\varphi _{e}\not \simeq \varphi _{F(e)}$ ${\ displaystyle \ varphi _ {e} \ not \ simeq \ varphi _ {F (e)}}$ ${\ displaystyle \ varphi _ {e} \ not \ simeq \ varphi _ {F (e)}}$ pentru fiecare e se spune fără puncte fixe . Teorema recursivității arată că nicio funcție calculabilă nu are puncte fixe, dar există multe funcții necomputabile fără puncte fixe. Criteriul de completitudine al lui Arslanov afirmă că singurul set recursiv enumerabil (în teoria calculabilității ) care calculează o funcție fără puncte fixe este setul de programe care se termină pe ele însele (K).

Bibliografie

Kleene, Stephen , „On notation for ordinal numbers”, Journal of Symbolic Logic , 3 (1938), 150-155.
Rogers, H. Theory of Recursive Functions and Effective Computability , MIT Press. ISBN 0-262-68052-1 ; ISBN 0-07-053522-1

Elemente conexe

Semantica denotațională , în care o altă teoremă de punct fix minim este utilizată în același scop ca și prima teoremă a recursiunii.
Combinatoare de puncte fixe , care sunt utilizate în calculul lambda în anumite scopuri, cum ar fi prima teoremă a recursiunii.

linkuri externe

( EN ) Piergiorgio Odifreddi și S. Barry Cooper, Recursive Functions , în Edward N. Zalta (ed.), Stanford Encyclopedia of Philosophy , Centre for the Study of Language and Information (CSLI), Universitatea Stanford , 2012 ..

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică