Funzione ricorsiva: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 3:
Le funzioni ricorsive sono un sovrainsieme delle [[funzione ricorsiva primitiva|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 [[turing equivalenza|equivalenti a quella delle funzioni ricorsive]] sono le [[funzioni lambda-ricorsive|funzioni λ-ricorsive]] e le funzioni che possono essere calcolate da un [[algoritmo di Markov]].caolo
== Definizione ==
| |||