Funcția recursivă primitivă

În teoria calculabilității , funcțiile recursive primitive sunt o clasă de funcții care pot fi definite prin aplicarea unui număr finit de ori de recursivitate și compoziție din anumite funcții de bază (funcții zero, funcție succesor și funcții selectabile sau proiective) și constituie un pas fundamental în construirea unei formalizări complete a calculabilității.

Funcțiile recursive primitive sunt un subset restrâns de funcții recursive (acestea din urmă corespund exact funcțiilor calculabile ). Clasa mai largă de funcții recursive este definită prin adăugarea posibilității de a avea funcții parțiale și introducerea unui operator de căutare nerestricționat.

Multe dintre funcțiile studiate de obicei în teoria numerelor și aproximările funcțiilor cu valoare reală sunt primitive recursive, cum ar fi adunarea , diviziunea , factorialul , exponențialul , găsirea celui de-al n-lea număr primar și multe altele (Brainerd și Landweber, 1974). De fapt, este dificil să proiectăm o funcție care este recursivă totală, dar nu recursivă primitivă, chiar dacă unele dintre ele sunt cunoscute, cum ar fi funcția Ackermann . Prin urmare, studiind acest tip special de funcții, este posibil să descoperim proprietăți care au consecințe de anvergură.

Funcțiile recursive primitive pot fi calculate de mașini care se termină întotdeauna , în timp ce funcțiile recursive necesită sisteme cu aceeași putere de calcul ca mașinile Turing .

Definiție

Definim primitivul recursiv o funcție care face parte din funcțiile de bază sau poate fi obținută pornind de la acestea prin aplicarea compoziției și recursivității primitive de un număr finit de ori; echivalent, întregul ${\mathcal {P}}$ ${\ displaystyle {\ mathcal {P}}}$ ${\ mathcal {P}}$ funcțiilor recursive primitive este definit ca cel mai mic set care conține funcțiile recursive de bază și care este închis prin compoziție și recursivitate primitivă.

Funcțiile recursive variază de la natural la natural: $\mathbb {N} ^{n}\rightarrow \mathbb {N}$ ${\ displaystyle \ mathbb {N} ^ {n} \ rightarrow \ mathbb {N}}$ ${\ displaystyle \ mathbb {N} ^ {n} \ rightarrow \ mathbb {N}}$ . În general, iau un tuplu de ca argumente $n$ ${\ displaystyle n}$ $n$ numerele naturale și returnează un număr natural. O funcție care necesită $n$ ${\ displaystyle n}$ $n$ argumente pe care le spune $n$ ${\ displaystyle n}$ $n$ - aer .

Funcții de bază

Definiți următoarele ca funcții de bază :

Funcțiile zero , care iau n argumente (cu $n\geq \;0$ ${\ displaystyle n \ geq \; 0}$ ${\ displaystyle n \ geq \; 0}$ ), și care returnează întotdeauna 0. Ele sunt deci funcții constante .

Z(x_{1},x_{2},\ldots ,x_{n})=0.

{\ displaystyle Z (x_ {1}, x_ {2}, \ ldots, x_ {n}) = 0.}

{\ displaystyle Z (x_ {1}, x_ {2}, \ ldots, x_ {n}) = 0.}

Funcția succesorală $S.$ ${\ displaystyle S}$ $S.$ , care ia un argument și returnează următorul număr

S(x)=x+1.

{\ displaystyle S (x) = x + 1.}

{\ displaystyle S (x) = x + 1.}

Funcțiile de proiecție (numite și funcții selective sau funcții de identitate), pe care le iau $n$ ${\ displaystyle n}$ $n$ subiecte ( $n\geq 1$ ${\ displaystyle n \ geq 1}$ $n \ ge 1$ ) și returnează $the$ ${\ displaystyle i}$ $the$ -alea dintre ele ( $1\leq i\leq n$ ${\ displaystyle 1 \ leq i \ leq n}$ ${\ displaystyle 1 \ leq i \ leq n}$ ).

P_{i}^{n}(x_{1},x_{2},\ldots ,x_{n})=x_{i}.

{\ displaystyle P_ {i} ^ {n} (x_ {1}, x_ {2}, \ ldots, x_ {n}) = x_ {i}.}

{\ displaystyle P_ {i} ^ {n} (x_ {1}, x_ {2}, \ ldots, x_ {n}) = x_ {i}.}

Luăm ca trei axiome faptul că toate sunt recursive primitive.

Compoziție și recursivitate

Este posibil să se obțină funcții recursive primitive care sunt mai complexe decât cele de bază, prin aplicarea următorilor operatori la acesta din urmă:

Operatorul de compoziție (sau substituție ):

de sine

f

{\ displaystyle f}

f

este o funcție a

n

{\ displaystyle n}

n

argumente, e

g_{1},\ldots ,g_{n}

{\ displaystyle g_ {1}, \ ldots, g_ {n}}

{\ displaystyle g_ {1}, \ ldots, g_ {n}}

toate sunt funcții a

m

{\ displaystyle m}

m

argumente, apoi funcția

h

{\ displaystyle h}

h

la

m

{\ displaystyle m}

m

subiecte:

h(x_{1},\ldots ,x_{m})=f(g_{1}(x_{1},\ldots ,x_{m}),\ldots ,g_{n}(x_{1},\ldots ,x_{m}))

{\ displaystyle h (x_ {1}, \ ldots, x_ {m}) = f (g_ {1} (x_ {1}, \ ldots, x_ {m}), \ ldots, g_ {n} (x_ { 1}, \ ldots, x_ {m}))}}

{\ displaystyle h (x_ {1}, \ ldots, x_ {m}) = f (g_ {1} (x_ {1}, \ ldots, x_ {m}), \ ldots, g_ {n} (x_ { 1}, \ ldots, x_ {m}))}}

se obține prin compoziție (sau substituție ) din

f

{\ displaystyle f}

f

Și

g_{1},\ldots ,g_{n}

{\ displaystyle g_ {1}, \ ldots, g_ {n}}

{\ displaystyle g_ {1}, \ ldots, g_ {n}}

Operatorul de recursiune primitiv :

de sine

f

{\ displaystyle f}

f

este o funcție a

n

{\ displaystyle n}

n

argumente, e

g

{\ displaystyle g}

g

este o funcție a

n+2

{\ displaystyle n + 2}

n + 2

argumente, apoi funcția

h

{\ displaystyle h}

h

la

n+1

{\ displaystyle n + 1}

n + 1

argumente definite după cum urmează:

$h(x_{1},\ldots ,x_{n},0)=f(x_{1},\ldots ,x_{n})$ ${\ displaystyle h (x_ {1}, \ ldots, x_ {n}, 0) = f (x_ {1}, \ ldots, x_ {n})}$ ${\ displaystyle h (x_ {1}, \ ldots, x_ {n}, 0) = f (x_ {1}, \ ldots, x_ {n})}$
$h(x_{1},\ldots ,x_{n},{\mbox{S}}(y))=g(x_{1},\ldots ,x_{n},y,h(x_{1},\ldots ,x_{n},y))$ ${\ displaystyle h (x_ {1}, \ ldots, x_ {n}, {\ mbox {S}} (y)) = g (x_ {1}, \ ldots, x_ {n}, y, h (x_ {1}, \ ldots, x_ {n}, y))}$ ${\ displaystyle h (x_ {1}, \ ldots, x_ {n}, {\ mbox {S}} (y)) = g (x_ {1}, \ ldots, x_ {n}, y, h (x_ {1}, \ ldots, x_ {n}, y))}$

se obține prin recursivitate primitivă din

f

{\ displaystyle f}

f

Și

g

{\ displaystyle g}

g

Rețineți că, datorită funcțiilor de proiecție, putem ocoli rigiditatea aparentă a numărului de argumente ale funcțiilor menționate mai sus, deoarece, datorită compoziției, putem trece orice subset de argumente.

Exemple

Plus

Funcția Adăugați ( $+$ ${\ displaystyle +}$ $+$ ) ca funcție recursivă poate fi definită prin recursivitate primitivă pornind de la funcția de bază Succesor $(\mathrm {S} )$ ${\ displaystyle (\ mathrm {S})}$ ${\ displaystyle (\ mathrm {S})}$ În felul următor:

+(x,0)=x;

{\ displaystyle + (x, 0) = x;}

{\ displaystyle + (x, 0) = x;}

+(x,\mathrm {S} (y))=\mathrm {S} (P_{3}^{3}(x,y,+(x,y)))=\mathrm {S} (+(x,y)).

{\ displaystyle + (x, \ mathrm {S} (y)) = \ mathrm {S} (P_ {3} ^ {3} (x, y, + (x, y))) = \ mathrm {S} (+ (x, y)).}

{\ displaystyle + (x, \ mathrm {S} (y)) = \ mathrm {S} (P_ {3} ^ {3} (x, y, + (x, y))) = \ mathrm {S} (+ (x, y)).}

Scădere

Pentru a defini funcția de scădere ( $-$ ${\ displaystyle -}$ $-$ ) ca funcție recursivă ne bazăm pe definiția funcției recursive Predecesor $(\mathrm {pred} )$ ${\ displaystyle (\ mathrm {pred})}$ ${\ displaystyle (\ mathrm {pred})}$ , la rândul său definit de recursivitate primitivă pornind de la funcția de bază Identitate $(P_{i})$ ${\ displaystyle (P_ {i})}$ ${\ displaystyle (P_ {i})}$ :

\mathrm {pred} (0)=0;

{\ displaystyle \ mathrm {pred} (0) = 0;}

{\ displaystyle \ mathrm {pred} (0) = 0;}

\mathrm {pred} (\mathrm {S} (y))=P_{1}^{2}\left(y,\mathrm {pred} (y)\right)=y.

{\ displaystyle \ mathrm {pred} (\ mathrm {S} (y)) = P_ {1} ^ {2} \ left (y, \ mathrm {pred} (y) \ right) = y.}

{\ displaystyle \ mathrm {pred} (\ mathrm {S} (y)) = P_ {1} ^ {2} \ left (y, \ mathrm {pred} (y) \ right) = y.}

Apoi obținem funcția Subtraction ( $-$ ${\ displaystyle -}$ $-$ ):

-(x,0)=x;

{\ displaystyle - (x, 0) = x;}

{\ displaystyle - (x, 0) = x;}

-(x,\mathrm {S} (y))=\mathrm {pred} (P_{3}^{3}(x,y,-(x,y)))=\mathrm {pred} (-(x,y)).

{\ displaystyle - (x, \ mathrm {S} (y)) = \ mathrm {pred} (P_ {3} ^ {3} (x, y, - (x, y))) = \ mathrm {pred} (- (X y)).}

{\ displaystyle - (x, \ mathrm {S} (y)) = \ mathrm {pred} (P_ {3} ^ {3} (x, y, - (x, y))) = \ mathrm {pred} (- (X y)).}

Multiplicare

Funcția de multiplicare ( $\cdot$ ${\ displaystyle \ cdot}$ $\ cdot$ ) ca funcție recursivă poate fi definită cu ajutorul funcției de adăugare deja definite ( $+$ ${\ displaystyle +}$ $+$ ) și precis:

\cdot (x,0)=0;

{\ displaystyle \ cdot (x, 0) = 0;}

{\ displaystyle \ cdot (x, 0) = 0;}

\cdot (x,\mathrm {S} (y))=+(P_{1}^{2}(x,y),\cdot (x,y))=+(x,\cdot (x,y)).

{\ displaystyle \ cdot (x, \ mathrm {S} (y)) = + (P_ {1} ^ {2} (x, y), \ cdot (x, y)) = + (x, \ cdot ( X y)).}

{\ displaystyle \ cdot (x, \ mathrm {S} (y)) = + (P_ {1} ^ {2} (x, y), \ cdot (x, y)) = + (x, \ cdot ( X y)).}

Factorială

Funcția factorială ( $!$ ${\ displaystyle!}$ ${\ displaystyle!}$ ) ca funcție recursivă poate fi definită cu ajutorul funcției deja definite Multiplicare ( $\cdot$ ${\ displaystyle \ cdot}$ $\ cdot$ ) și precis:

!(0)=\mathrm {S} (0)

{\ displaystyle! (0) = \ mathrm {S} (0)}

{\ displaystyle! (0) = \ mathrm {S} (0)}

!(\mathrm {S} (y))=\cdot (\mathrm {S} (y),!(y)).

{\ displaystyle! (\ mathrm {S} (y)) = \ cdot (\ mathrm {S} (y) ,! (y)).}

{\ displaystyle! (\ mathrm {S} (y)) = \ cdot (\ mathrm {S} (y) ,! (y)).}

Limitări

Deși toate funcțiile primitive recursive sunt totale, există funcții totale care nu sunt primitive recursive: un exemplu este funcția Ackermann , care este calculabilă, totală, dar nu primitivă recursivă.

Prin urmare, deoarece există funcții care nu pot fi descrise de acest formalism, nu este adecvat să se reprezinte care sunt funcțiile computabile intuitiv. Extinderea funcțiilor primitive recursive care reprezintă toate funcțiile calculabile (adică are aceeași expresivitate a mașinii Turing ), este cea a funcțiilor recursive .

Bibliografie

Giorgio Ausiello, Fabrizio d'Amore, Giorgio Gambosi; FrancoAngeli Editor: Limbi, modele, complexitate (2003) ( ISBN 88-464-4470-1 )
Brainerd, WS, Landweber, LH (1974), Theory of Computation , Wiley, ISBN 0471095850

Elemente conexe

L (limba)

linkuri externe

( EN ) Funcție recursivă primitivă , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.