Funzione ricorsiva
Da Wikipedia, l'enciclopedia libera.
Questa voce è solo un abbozzo (stub). Se puoi, contribuisci adesso a migliorarla secondo le convenzioni di Wikipedia. Per l'elenco completo degli stub di matematica, vedi la relativa categoria.
Nella logica matematica e nell'informatica, le funzioni ricorsive sono una classe di funzioni dai numeri naturali ai numeri naturali che sono "calcolabili" in un qualche senso intuitivo. Infatti nella teoria della calcolabilità si mostra che le funzioni ricorsive corrispondono precisamente a quelle funzioni che possono essere calcolate tramite una macchina di Turing.
La funzioni ricorsive sono un sovrainsieme delle funzioni ricorsive primitive, ed infatti la loro definizione induttiva (come vedremo nel seguito) è costruita a partire da quella di queste ultime. Esistono quindi funzioni ricorsive che non sono anche ricorsive primitive, e l'esempio più noto è quello della funzione di Ackermann.
Altre classi di funzioni equivalenti a quella delle funzioni ricorsive sono le funzioni λ-ricorsive e le funzioni che possono essere calcolate da un algoritmo di Markov.
Indice |
[modifica] Definizione
[modifica] Esempi di funzioni ricorsive
[modifica] Limitazioni: funzioni non ricorsive
Non tutte le funzioni sono calcolabili, cioè ricorsive. Ecco alcuni esempi.
[modifica] Il problema della fermata
[modifica] Teorema
Consideriamo una qualunque enumerazione delle funzioni ricorsive, in cui la funzione 
corrisponde alla i + 1-esima funzione ricorsiva. Cioè detta f la i + 1-esima funzione ricorsiva, abbiamo:
Allora, non esiste nessuna funzione ricorsiva g tale che per ogni x e y
Questo problema è una formulazione del problema della fermata. Si veda l'apposita sezione nell'articolo sugli insiemi ricorsivi per una formulazione alternativa.
[modifica] Dimostrazione
Supponiamo per ipotesi che g sia ricorsiva. Allora lo sarebbe anche una funzione h così definita:
Diciamo che nell'enumerazione delle funzioni ricorsive che abbiamo dato, e sia l'indice della funzione h, e che quindi 
.
Se passiamo l'indice e (che è un numero naturale) come parametro alla funzione h, abbiamo 
.
Per la definizione di h abbiamo che h = 1 se e solo se g(e,e) = 0.
Ma per la definizione di g abbiamo che g(e,e) = 0 se e solo se 
non è definita.
Ricapitolado 
se e solo se g(e,e) = 0, che è come dire che 
se e solo se non è definita, che è assurdo.
Quindi questa dimostrazione per assurdo mostra che l'ipotesi iniziale "g è ricorsiva" è falsa.
[modifica] Altre funzioni non ricorsive
[modifica] Riferimenti esterni
[modifica] Bibliografia
- Giorgio Ausiello, Fabrizio d’Amore, Giorgio Gambosi; FrancoAngeli Editore: Linguaggi, Modelli, Complessità (2003) (ISBN 88-464-4470-1)
- Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0471095850
