Funzioni ricorsive

In questa tesi sono raggruppati i principali risultati sulle funzioni e relazioni ricorsive con un particolare approfondimento alle seguenti famiglie di funzioni: 1) elementari ricorsive 2) primitive ricorsive 3) generali ricorsive 4) generali ricorsive parziali L'obbiettivo è quello di dare alcuni esempi di funzioni calcolabili e le possibili caratterizzazioni delle quattro famiglie, partendo dalle elementari ed estendendo la famiglia fino alle funzioni primitive ricorsive (caratterizzate dal teorema di Raphael M. Robinson) aggiungendo lo schema di ricorsione primitiva e poi fino alle generali ricorsive (caratterizzate invece dal teorema di Julia Robinson) ammettendo la minimalizzazione, ma vincolandola a dare funzioni totali e arrivando, infine, alle ricorsive parziali (caratterizzate dal teorema della forma normale di Kleene) ottenute considerando la minimalizzazione senza il vincolo di totalità. In parallelo vengono mostrate le proprietà delle rispettive relazioni associate ad ogni famiglia di funzioni e lo strumento di aritmetizzazione sia per scomposizione in fattori primi che tramite la funzione beta di Gödel.