Funcția recursivă (teoria calculabilității)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 4 iunie 2021; verificările necesită 2 modificări .

Termenul de funcție recursivă în teoria computabilității este folosit pentru a se referi la trei clase de funcții:

funcții recursive primitive ;
funcții recursive generale ;
funcții parțial recursive .

Acestea din urmă coincid cu clasa de funcții calculabile Turing . Definițiile acestor trei clase sunt strâns legate. Ele au fost introduse de Kurt Gödel pentru a oficializa noțiunea de computabilitate.

Setul de funcții recursive parțial include setul de funcții recursive generale, iar funcțiile recursive generale includ funcții recursive primitive. Funcțiile parțial recursive sunt uneori denumite pur și simplu funcții recursive.

Funcție recursivă primitivă

Definiție

Definiția conceptului de funcție recursivă primitivă este inductivă . Constă în specificarea unei clase de funcții recursive primitive de bază și a doi operatori ( suprapunere și recursivitate primitivă ) care permit construirea de noi funcții recursive primitive pe baza celor existente.

Funcțiile recursive primitive de bază includ următoarele trei tipuri de funcții:

O funcție nulă este o funcție fără argumente care returnează întotdeauna 0 . $O$
O funcție de succesiune cu o singură variabilă care atribuie oricărui număr natural numărul natural imediat următor . De exemplu, . $S$ $X$ $x+1$ $S(41)=42$
Funcții , unde , a n variabile, care atribuie oricărui set ordonat de numere naturale un număr din această mulțime. De exemplu, . $eu_{n}^{m}$ $0<m\leqslant n$ $x_{1},\dots ,x_{n}$ $x_{m}$ $I_{3}^{2}(10,20,30)=20$

Operatorii de substituție și recursivitate primitivă sunt definiți după cum urmează:

Operatorul de suprapunere (uneori operatorul de substituție ). Fie o funcție a m variabile și fie un set ordonat de funcții ale variabilelor fiecare. Atunci rezultatul suprapunerii funcțiilor într-o funcție este o funcție de variabile care atribuie oricărui set ordonat de numere naturale numărul $f$ $g_{1},\dots ,g_{m}$ $n$ $g_{k}$ $f$ $h$ $n$ $x_{1},\dots ,x_{n}$ $h(x_{1},\ldots,x_{n})=f{\big (}g_{1}(x_{1},\ldots,x_{n}),\ldots,g_{m }(x_{1},\ldots ,x_{n}){\big )}.$
Operatorul recursiv primitiv . Fie o funcție de variabile și fie o funcție de variabile. Atunci rezultatul aplicării operatorului recursiv primitiv la o pereche de funcții este o funcție a unei variabile de forma $f$ $n$ $g$ $n+2$ $f$ $g$ $h$ $n+1$ $h(x_{1},\ldots,x_{n},0)=f(x_{1},\ldots,x_{n});$ $h(x_{1},\ldots,x_{n},y+1)=g(x_{1},\ldots,x_{n},y,h(x_{1},\ldots, x_{n},y)).$

În această definiție, o variabilă poate fi înțeleasă ca un numărător de iterații, — ca o funcție inițială la începutul procesului de iterație, emitând o anumită secvență de funcții ale variabilelor, începând cu , și — ca un operator care acceptă ca variabile de intrare , numărul pasului de iterație , o funcție la un pas de iterație dat și funcția de revenire la pasul următor al iterației. $y$ $f$ $n$ $f$ $g$ $n$ $x_{1},\ldots ,x_{n}$ $y$ $h(x_{1},\ldots,x_{n},y)$

Setul de funcții recursive primitive este setul minim care conține toate funcțiile de bază și este închis sub operatorii de substituție și recursivitate primitive specificați.

În ceea ce privește programarea imperativă , funcțiile recursive primitive corespund blocurilor de program care utilizează numai operații aritmetice, precum și un operator condiționat și un operator de buclă aritmetică (un operator de buclă în care numărul de iterații este cunoscut în momentul începerii buclei). Dacă programatorul începe să folosească operatorul buclă while, în care numărul de iterații nu este cunoscut în prealabil și, în principiu, poate fi infinit, atunci trece în clasa funcțiilor parțial recursive.

Exemple

Să subliniem o serie de funcții aritmetice binecunoscute care sunt primitiv recursive.

Funcția Adunarea a două numere naturale ( ) poate fi considerată ca o funcție recursivă primitivă a două variabile obținută prin aplicarea operatorului recursiv primitiv la funcțiile și , al doilea dintre care se obține prin înlocuirea funcției principale în funcția principală : $Suma(a,\;b)=a+b$ $eu_{1}^{1}$ $F$ $eu_{3}^{3}$ $S$

Suma(x,\;0)=I_{1}^{1}(x)

;

Suma(x,\;y+1)=F(x,\;y,\;Suma(x,\;y))

;

F(x,\;y,\;z)=S(I_{3}^{3}(x,\;y,\;z))

Înmulțirea a două numere naturale ( ) poate fi considerată ca o funcție recursivă primitivă a două variabile, obținută ca urmare a aplicării operatorului recursiv primitiv la funcțiile și , al doilea dintre care se obține prin înlocuirea funcțiilor principale și în adunare. funcţie: $Mul(a,\;b)=a\times b$ $O$ $G$ $eu_{3}^{1}$ $eu_{3}^{3}$

Mul(x,\;0)=O(x)

;

Mul(x,\;y+1)=G(x,\;y,\;Mul(x,y))

;

G(x,\;y,\;z)=Suma(I_{3}^{1}(x,\;y,\;z),I_{3}^{3}(x,\;y, \;z))

Diferența simetrică (valoarea absolută a diferenței) a două numere naturale ( ) poate fi considerată ca o funcție recursivă primitivă a două variabile, obținută prin aplicarea următoarelor substituții și recursiuni primitive: $Sub(a,\;b)=|ab|$

Sub(x,\;y)=Suma(Sub_{1}(x,\;y),\;Sub_{2}(x,\;y))

;

Sub_{2}(x,\;y)=Sub_{1}(I_{2}^{2}(x,\;y),\;I_{2}^{1}(x,\;y) )

;

\left\{{\begin{array}{l}Sub_{1}(x,\;0)=I_{1}^{1}(x)\\Sub_{1}(x,\;y+1 )=f(x,\;y,\;Sub_{1}(x,\;y))\end{array}}\dreapta.

;

f(x,\;y,\;z)=p(I_{3}^{3}(x,\;y,\;z))

;

\left\{{\begin{array}{l}p(0)=0\\p(y+1)=I_{2}^{1}(y,\;p(y))\end{array }}\dreapta.

;

Funcție parțial recursivă

O funcție parțial recursivă este definită în mod similar cu una primitivă recursivă, doar la doi operatori, suprapunere și recursiune primitivă, se adaugă un al treilea operator - minimizarea argumentului.

Operator de minimizare a argumentului . Fie o funcție a n variabile naturale. Atunci rezultatul aplicării operatorului argument minim unei funcții este o funcție a unei variabile, dată de următoarea definiție: $f$ $f$ $h$ $n-1$

h(x_{1},\ldots ,x_{n-1})=\min y

, cu conditia

f(x_{1},\ldots,x_{n-1},\,y)=0

Adică, funcția returnează valoarea minimă a ultimului argument al funcției , la care valoarea sa este 0.

h

f

Este posibil ca funcțiile parțial recursive pentru unele valori ale argumentului să nu fie definite, deoarece operatorul de minimizare a argumentului nu este întotdeauna definit corect, deoarece funcția poate să nu fie egală cu zero pentru orice valoare a argumentului. Din punct de vedere al programării imperative, rezultatul unei funcții parțial recursive poate fi nu doar un număr, ci și o excepție sau o buclă infinită corespunzătoare unei valori nedefinite. $f$

Funcție recursivă generală

O funcție recursivă generală este o funcție parțial recursivă definită pentru toate valorile argumentului. Problema de a determina dacă o funcție parțial recursivă cu o descriere dată este recursivă generală sau nu este algoritmic indecidabilă .

Proprietăți

Este ușor de înțeles că orice funcție recursivă primitivă este parțial recursivă, deoarece prin definiție operatorii pentru construirea de funcții parțial recursive includ operatorii pentru construirea funcțiilor recursive primitive.

De asemenea, este clar că o funcție recursivă primitivă este definită peste tot și, prin urmare, este o funcție recursivă generală (o funcție recursivă primitivă nu are niciun motiv să se „atârneze”, deoarece construcția sa folosește operatori care definesc funcții definite peste tot).

Este destul de dificil să dovedești existența și să dai un exemplu de funcție recursivă generală care nu este recursivă primitiv. Un exemplu popular este funcția Ackermann . Un alt exemplu de funcție recursivă generală care nu este recursivă primitivă este construit prin metoda diagonală a lui Cantor dintr-o funcție universală pentru un set de funcții recursive primitive unare.

După cum a arătat Gödel , funcțiile parțial recursive coincid cu setul de funcții calculabile .

Istoricul numelui

Termenii „funcție recursivă parțial” și „funcție recursivă generală” au prins rădăcini din motive istorice și sunt în esență rezultatul unei traduceri inexacte a termenilor englezi „funcție recursivă parțială ” și „funcție recursivă totală” , care sunt traduși mai corect ca „funcții recursive definite”. pe părți ale setului de argumente posibile” și „funcții recursive definite pe întregul setul de argumente posibile”. Adverbul „parțial” nu se referă la adjectivul „recursiv”, ci la sfera funcției. Poate că un nume mai corect ar fi „funcții recursive parțial definite” și pur și simplu „funcții recursive definite oriunde”. Dar numele lungi nu au prins rădăcini.

Vezi și

Algoritmul Markov ( programarea producției )
Mașină Turing ( programare automată )
Aparatul posta ( programare automata )
Calcul lambda ( programare funcțională )
Brainfuck ( programare imperativă )
Unlambda ( calcul funcțional )

Literatură

Hilbert D, Bernays P. Fundamentele matematicii. T. 1. - M .: Nauka, 1979.
Kleene S.K. Introducere în metamatematică. - M., 1957.
Algoritmi Maltsev AI și funcții recursive. Moscova: Nauka, 1986.
Peter R. Funcții recursive - IL, 1954.
Vereshchagin N. K., Shen A. Prelegeri despre logica matematică și teoria algoritmilor . Partea 3. Funcții calculabile, ed. a 2-a, revizuită. — M.: MTsNMO, 2002.