Funcție recursivă generală - General recursive function

În logica matematică și informatică , o funcție recursivă generală , o funcție recursivă parțială sau o funcție μ-recursivă este o funcție parțială de la numere naturale la numere naturale care este „calculabilă” într-un sens intuitiv. Dacă funcția este totală, se mai numește și funcție recursivă totală (uneori scurtată la funcție recursivă ). În teoria calculabilității , se arată că funcțiile μ-recursive sunt exact funcțiile care pot fi calculate de mașinile Turing (aceasta este una dintre teoremele care susțin teza Biserica-Turing ). Funcțiile μ-recursive sunt strâns legate de funcțiile recursive primitive , iar definiția lor inductivă (de mai jos) se bazează pe cea a funcțiilor recursive primitive. Cu toate acestea, nu fiecare funcție recursivă totală este o funcție recursivă primitivă - cel mai faimos exemplu este funcția Ackermann .

Alte clase echivalente de funcții sunt funcțiile calculului lambda și funcțiile care pot fi calculate de algoritmi Markov .

Subsetul tuturor totalul funcțiilor recursive cu valori in {0,1} este cunoscută în teoria complexității computaționale ca clasă de complexitate R .

Definiție

Funcțiile μ-recursive (sau funcții recursive generale ) sunt funcții parțiale care iau tupluri finite de numere naturale și returnează un singur număr natural. Ele sunt cea mai mică clasă de funcții parțiale care include funcțiile inițiale și este închisă sub compoziție, recursivitate primitivă și operatorul μ .

Cea mai mică clasă de funcții, inclusiv funcțiile inițiale și închise sub compoziție și recursivitate primitivă (adică fără minimizare) este clasa funcțiilor recursive primitive . În timp ce toate funcțiile recursive primitive sunt totale, acest lucru nu este valabil pentru funcțiile recursive parțiale; de exemplu, minimizarea funcției succesor este nedefinită. Funcțiile recursive primitive sunt un subset al funcțiilor recursive totale, care sunt un subset al funcțiilor recursive parțiale. De exemplu, funcția Ackermann se poate dovedi recursivă totală și neprimitivă.

Funcții primitive sau „de bază”:

1. Funcții constante C^k
   _n: Pentru fiecare număr natural și fiecare definiție alternativă se utilizează în schimb o funcție zero ca funcție primitivă care întotdeauna returnează zero și a construit funcțiile constante din funcția zero, funcția succesor și operatorul de compoziție.${\ displaystyle n \,}$${\ displaystyle k \,}$
       ${\ displaystyle C_ {n} ^ {k} (x_ {1}, \ ldots, x_ {k}) {\ stackrel {\ mathrm {def}} {=}} n}$
   
2. Funcția succesorului S:
       ${\ displaystyle S (x) {\ stackrel {\ mathrm {def}} {=}} x + 1 \,}$
3. Funcția de proiecție (numită și funcția Identitate ): Pentru toate numerele naturale, astfel încât :${\ displaystyle P_ {i} ^ {k}}$${\ displaystyle i, k}$${\ displaystyle 1 \ leq i \ leq k}$
       ${\ displaystyle P_ {i} ^ {k} (x_ {1}, \ ldots, x_ {k}) {\ stackrel {\ mathrm {def}} {=}} x_ {i} \ ,.}$

Operatori ( domeniul unei funcții definit de un operator este setul de valori ale argumentelor astfel încât fiecare aplicație de funcție care trebuie realizată în timpul calculului oferă un rezultat bine definit):

1. Operator de compoziție (numit și operator de substituție ): Având o funcție m-ari și funcții m-ari : Acest lucru înseamnă că este definit doar dacă și sunt definite toate.${\ 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 {\ mathrm {def}} {=}} f, \ quad {\ text {where}} \ 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 de recursie primitiv : Având în vedere funcția k -ary și k +2 -ary funcție : Aceasta înseamnă că este definit numai dacă și sunt definite pentru toate${\ displaystyle \ rho \,}$${\ displaystyle g (x_ {1}, \ ldots, x_ {k}) \,}$${\ displaystyle h (y, z, x_ {1}, \ ldots, x_ {k}) \,}$
       ${\ displaystyle {\ begin {align} \ rho (g, h) & {\ stackrel {\ mathrm {def}} {=}} f \ quad {\ text {unde funcția k + 1 -ary}} f { \ text {este definit de}} \\ 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 {align}}}$
   ${\ 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 de minimizare : dată fiind o funcție ( k +1) -ary , funcția k -ary este definită prin: Intuitiv, minimizarea caută - începând căutarea de la 0 și continuând în sus - cel mai mic argument care determină funcția să returneze zero; dacă nu există un astfel de argument sau dacă se întâlnește un argument pentru care f nu este definit, atunci căutarea nu se termină niciodată și nu este definită pentru argument ( Notă : În timp ce unele manuale folosesc operatorul μ așa cum este definit aici, altele ca cerem ca operatorul μ să fie aplicat numai funcțiilor totale . Deși acest lucru restricționează operatorul μ în comparație cu definiția dată aici, clasa funcțiilor μ-recursive rămâne aceeași, care rezultă din teorema formei normale a lui Kleene (vezi mai jos ) Singura diferență constă în faptul că devine nedecidabil dacă o definiție specifică a funcției definește o funcție μ-recursivă, deoarece este nedecidabilă dacă o funcție calculabilă (adică μ-recursivă) este totală.)${\ displaystyle \ mu \,}$${\ displaystyle f (y, x_ {1}, \ ldots, x_ {k}) \,}$${\ displaystyle \ mu (f)}$
       ${\ displaystyle {\ begin {align} \ mu (f) (x_ {1}, \ ldots, x_ {k}) = z {\ stackrel {\ mathrm {def}} {\ iff}} \ f (i, 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 {align}}}$
   ${\ displaystyle \ mu (f)}$${\ displaystyle (x_ {1}, \ ldots, x_ {k}).}$
   ${\ displaystyle f}$

Puternică egalitate Operatorul poate fi folosit pentru a compara funcțiile parțiale p-recursiv. Aceasta este definită pentru toate funcțiile parțiale f și g astfel încât ${\ displaystyle \ simeq}$

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

este valabil dacă și numai dacă pentru orice alegere de argumente ambele funcții sunt definite și valorile lor sunt egale sau ambele funcții sunt nedefinite.

Funcție recursivă totală

O funcție recursivă generală se numește funcție recursivă totală dacă este definită pentru fiecare intrare sau, în mod echivalent, dacă poate fi calculată de o mașină Turing totală . Nu există nicio modalitate de a spune în mod calculabil dacă o anumită funcție recursivă generală este totală - vezi Problema opririi .

Echivalența cu alte modele de calculabilitate

În echivalența modelelor de calculabilitate , se trasează o paralelă între mașinile Turing care nu se termină pentru anumite intrări și un rezultat nedefinit pentru acea intrare în funcția recursivă parțială corespunzătoare. Operatorul de căutare nelimitat nu este definibil de regulile recursivității primitive, deoarece acestea nu oferă un mecanism pentru „bucle infinite” (valori nedefinite).

Teorema formei normale

O teoremă a formei normale datorată lui Kleene spune că pentru fiecare k există funcții recursive primitive și astfel încât pentru orice funcție μ-recursivă cu k variabile libere există un e astfel încât ${\ 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 y \, T (y, e, x_ {1}, \ ldots, x_ {k}))}$.

Numărul e se numește index sau număr Gödel pentru funcția f . O consecință a acestui rezultat este că orice funcție μ-recursivă poate fi definită folosind o singură instanță a operatorului μ aplicată unei funcții recursive primitive (totale).

Minsky observă că definiția de mai sus este în esență echivalentul μ-recursiv al mașinii universale Turing : ${\ displaystyle U}$

A construi U înseamnă a nota definiția unei funcții general-recursive U (n, x) care interpretează corect numărul n și calculează funcția corespunzătoare a lui x. a construi U direct ar presupune în esență aceeași cantitate de efort și în esență aceleași idei , așa cum am investit în construirea mașinii universale Turing

Simbolism

O serie de simboluri diferite sunt utilizate în literatură. Un avantaj al utilizării simbolismului este derivarea unei funcții prin „cuibărirea” operatorilor unul în celălalt, este mai ușor de scris într-o formă compactă. În cele ce urmează vom abrevia șirul de parametri x ₁ , ..., x _n ca x :

• Funcția constantă : Kleene folosește „Cⁿ
  _q( x ) = q "și Boolos-Burgess-Jeffrey (2002) (BBJ) utilizează abrevierea" const _n ( x ) = n ":

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

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

• Funcția succesorală : Kleene folosește x 'și S pentru „Succesor”. Deoarece „succesorul” este considerat a fi primitiv, majoritatea textelor folosesc apostroful după cum urmează:

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

• Funcția de identitate : Kleene (1952) folosește „Uⁿ
  _i"pentru a indica funcția de identitate peste variabilele x _i ; BBJ utilizează funcția de identitate idⁿ
  _ipeste variabilele de la ₁ la x _n :

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

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

• Operator de compoziție (înlocuire) : Kleene folosește un S cu caractere aldine^m
  _n(nu trebuie confundat cu S-ul său pentru „succesor” ! ). Superscriptul "m" se referă la a m- ^a funcției "f _m ", în timp ce subscriptul "n" se referă la a n- ^a variabilă "x _n ":

Dacă ni se dă h ( x ) = g (f ₁ ( x ), ..., f _m ( x ))

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

Într-o manieră similară, dar fără subindice și superindice, BBJ scrie:

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

• Recursivitate primitivă : Kleene folosește simbolul " R ⁿ (pas de bază, pas de inducție)" unde n indică numărul de variabile, BBJ utilizează "Pr (pas de bază, pas de inducție) ( x )". Dat:

• pasul de bază: h (0, x ) = f ( x ) și
• pas de inducție: h (y + 1, x ) = g (y, h (y, x ), x )

Exemplu: definiție recursivă primitivă a + b:

• pas de bază: f (0, a) = a = U¹
  ₁(A)
• pas de inducție: 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)]}

Exemplu : Kleene oferă un exemplu despre cum se realizează derivarea recursivă a f (b, a) = b + a (observați inversarea variabilelor a și b). El începe cu 3 funcții inițiale

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. pas de bază: h (0, a) = U¹
   ₁(A)

pas de inducție: h (b ', a) = g (b, h (b, a), a)

El ajunge la:

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

Exemple

• Numărul Fibonacci
• Funcția McCarthy 91

Vezi si

• Teoria recursivității
• Recursivitate
• Recursivitate (informatică)

Referințe

linkuri externe

• Intrarea Stanford Encyclopedia of Philosophy
• Un compilator pentru transformarea unei funcții recursive într-o mașină Turing echivalentă