Functie recursiva

În logica matematică și informatică , funcțiile recursive sunt o clasă de funcții de la numere naturale la numere naturale care sunt „calculabile” în sens intuitiv. De fapt, în teoria calculabilității se arată că funcțiile recursive corespund exact acelor funcții care pot fi calculate prin intermediul unei mașini Turing .

Funcțiile recursive sunt un superset al funcțiilor recursive primitive și, de fapt, definiția lor inductivă (așa cum vom vedea mai jos) este construită pornind de la cea a acesteia din urmă. Prin urmare, există funcții recursive care nu sunt și recursive primitive, iar cel mai cunoscut exemplu este cel al funcției Ackermann . Alte clase de funcții echivalente cu cele ale funcțiilor recursive sunt funcțiile λ-recursive și funcțiile care pot fi calculate de un algoritm Markov .

Descriere

Definiție

Funcțiile recursive sunt definite pe baza funcțiilor recursive primitive .

Funcțiile recursive sunt cea mai mică clasă de funcții care conțin funcții recursive primitive închise în ceea ce privește operatorii de compoziție, operatorii recursivi primitivi și operatorul μ, numit și operator de minimizare.

Operatorul μ este definit după cum urmează:

Minimizare $\mu$ ${\ displaystyle \ mu}$ $\ mu$ : dată o funcție totală $f(y,x_{1},\ldots ,x_{n})$ ${\ displaystyle f (y, x_ {1}, \ ldots, x_ {n})}$ $f (y, x_ {1}, \ ldots, x_ {n})$ :

{\begin{aligned}\mu ,y:(f(y,x_{1},\ldots ,x_{n})=0)\ &{\stackrel {\mathrm {def} }{=}}{\text{ il più piccolo }}y{\text{ tale che }}f(y,x_{1},\ldots ,x_{n})=0\ \ {\text{ (se esiste)}}\end{aligned}}

{\ displaystyle {\ begin {align} \ mu, y: (f (y, x_ {1}, \ ldots, x_ {n}) = 0) \ & {\ stackrel {\ mathrm {def}} {=} } {\ text {the smallest}} y {\ text {astfel încât}} f (y, x_ {1}, \ ldots, x_ {n}) = 0 \ \ {\ text {(dacă există)}} \ end {align}}}

{\ begin {align} \ mu, y: (f (y, x_ {1}, \ ldots, x_ {n}) = 0) \ & {\ stackrel {\ mathrm {def}} {=}} {\ text {cel mai mic}} y {\ text {astfel încât}} f (y, x_ {1}, \ ldots, x_ {n}) = 0 \ \ {\ text {(dacă există)}} \ end { aliniat}}

Funcțiile recursive primitive sunt, prin urmare, un subset al funcțiilor recursive. Rețineți că, deși funcțiile recursive primitive sunt întotdeauna totale (NB: nu toate funcțiile totale sunt recursive primitive), funcțiile recursive pot fi parțiale, adică nu pot fi definite pentru unele valori de intrare: de fapt, operatorul de minimizare nu returnează valoare în cazul în care funcția la care este aplicată nu este anulată pentru nicio valoare a argumentului.

Cu toate acestea, amintiți-vă că operatorul de minimizare funcționează pe funcții totale. Se poate arăta că, dacă admitem aplicarea operatorului de minimizare pe funcții parțiale, atunci funcțiile recursive nu ar fi închise în ceea ce privește minimizarea.

Exemple de funcții recursive

Limitări: funcții nerecursive

Nu toate funcțiile sunt calculabile, adică recursive. Aici sunt cateva exemple.

Problema opririi

Teorema

Să luăm în considerare orice enumerare a funcțiilor recursive , în care funcția $\varphi _{i}$ ${\ displaystyle \ varphi _ {i}}$ $\ varphi _ {i}$ Corespunde la $i+1$ ${\ displaystyle i + 1}$ $i + 1$ -funcția recursivă. Adică, a spus $f$ ${\ displaystyle f}$ $f$ Acolo $i+1$ ${\ displaystyle i + 1}$ $i + 1$ -funcția recursivă, avem:

\varphi _{i}(y)=f(y)

{\ displaystyle \ varphi _ {i} (y) = f (y)}

\ varphi _ {i} (y) = f (y)

Apoi, nu există o funcție recursivă $g$ ${\ displaystyle g}$ $g$ astfel încât pentru fiecare $X$ ${\ displaystyle x}$ $X$ Și $y$ ${\ displaystyle y}$ $y$

g(x,y)={\begin{cases}1&{\mbox{se }}\varphi _{x}(y){\mbox{ è definita}}\\0&{\mbox{altrimenti }}\end{cases}}

{\ displaystyle g (x, y) = {\ begin {cases} 1 & {\ mbox {se}} \ varphi _ {x} (y) {\ mbox {este definit}} \\ 0 & {\ mbox { altfel}} \ end {cases}}}

g (x, y) = {\ begin {cases} 1 & {\ mbox {se}} \ varphi _ {x} (y) {\ mbox {este definit}} \\ 0 & {\ mbox {altfel}} \ end {cases}}

Această problemă este o formulare a problemei de oprire . Consultați secțiunea corespunzătoare din articolul despre seturi recursive pentru o formulare alternativă.

Demonstrație

Să presupunem prin ipoteză că $g$ ${\ displaystyle g}$ $g$ este recursiv. Atunci ar fi și o funcție $h$ ${\ displaystyle h}$ $h$ definit astfel:

h(x)={\begin{cases}1&{\mbox{se }}g(x,x)=0{\mbox{, cio}}{\grave {e}}{\mbox{ se }}\varphi _{x}(x){\mbox{ non }}{\grave {e}}{\mbox{ definita}}\\{\text{indefinita}}&{\mbox{altrimenti}}\end{cases}}

{\ displaystyle h (x) = {\ begin {cases} 1 & {\ mbox {se}} g (x, x) = 0 {\ mbox {, adică}} {\ grave {e}} {\ mbox {if}} \ varphi _ {x} (x) {\ mbox {not}} {\ grave {e}} {\ mbox {defined}} \\ {\ text {undefined}} și {\ mbox {altfel} } \ end {cases}}}

h (x) = {\ begin {cases} 1 & {\ mbox {se}} g (x, x) = 0 {\ mbox {, adică}} {\ grave {e}} {\ mbox {se} } \ varphi _ {x} (x) {\ mbox {non}} {\ grave {e}} {\ mbox {defined}} \\ {\ text {undefined}} și {\ mbox {else}} \ end {cazuri}}

Spunem că în enumerarea funcțiilor recursive pe care le-am dat, $Și$ ${\ displaystyle e}$ $Și$ este indicele funcției $h$ ${\ displaystyle h}$ $h$ și, prin urmare $h=\varphi _{e}$ ${\ displaystyle h = \ varphi _ {e}}$ $h = \ varphi _ {e}$ .
Dacă trecem indexul $Și$ ${\ displaystyle e}$ $Și$ (care este un număr natural ) ca parametru al funcției $h$ ${\ displaystyle h}$ $h$ , avem $h(e)=\varphi _{e}(e)$ ${\ displaystyle h (e) = \ varphi _ {e} (e)}$ $h (e) = \ varphi _ {e} (e)$ .
Pentru definirea $h$ ${\ displaystyle h}$ $h$ avem asta $h=1$ ${\ displaystyle h = 1}$ ${\ displaystyle h = 1}$ dacă și numai dacă $g(e,e)=0$ ${\ displaystyle g (e, e) = 0}$ $g (e, e) = 0$ .
Dar prin definiția lui $g$ ${\ displaystyle g}$ $g$ avem asta $g(e,e)=0$ ${\ displaystyle g (e, e) = 0}$ $g (e, e) = 0$ dacă și numai dacă $\varphi _{e}(e)$ ${\ displaystyle \ varphi _ {e} (e)}$ $\ varphi _ {e} (e)$ nu este definit.
În concluzie $\varphi _{e}(e)=h(e)=1$ ${\ displaystyle \ varphi _ {e} (e) = h (e) = 1}$ $\ varphi _ {e} (e) = h (e) = 1$ dacă și numai dacă $g(e,e)=0$ ${\ displaystyle g (e, e) = 0}$ $g (e, e) = 0$ , care este ca și cum ai spune asta $\varphi _{e}(e)=1$ ${\ displaystyle \ varphi _ {e} (e) = 1}$ $\ varphi _ {e} (e) = 1$ dacă și numai dacă $\varphi _{e}(e)$ ${\ displaystyle \ varphi _ {e} (e)}$ $\ varphi _ {e} (e)$ nu este definit, ceea ce este absurd .
Deci această dovadă prin absurditate arată că ipoteza inițială " $g$ ${\ displaystyle g}$ $g$ este recursiv "este fals.

Bibliografie

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

Elemente conexe

Inducţie

linkuri externe

( EN ) Funcție recursivă , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.
(EN) Zalta Edward N. (eds), funcție recursivă , în Stanford Encyclopedia of Philosophy , Centre for the Study of Language and Information (CSLI), Universitatea Stanford .

Controlul autorității	Tezaur BNCF 45388 · LCCN (EN) sh85112014 · BNF (FR) cb11977577z (data)

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