funzione ricorsiva primitiva

Nella teoria della calcolabilità, le funzioni ricorsive primitive sono una classe di funzioni che possono essere definite applicando un numero finito di volte la ricorsione e la composizione a partire da particolari funzioni base (funzioni zero, funzione successore e funzioni selettive o proiettive) e costituiscono un passo fondamentale nella costruzione di una completa formalizzazione della calcolabilità. Le funzioni ricorsive primitive sono un sottoinsieme stretto delle funzioni ricorsive (queste ultime corrispondono esattamente alle funzioni calcolabili). La classe più ampia delle funzioni ricorsive è definita aggiungendo la possibilità di avere funzioni parziali e introducendo un operatore di ricerca non limitato. Molte delle funzioni solitamente studiate nella teoria dei numeri, e le approssimazioni di funzioni a valori reali, sono primitive ricorsive, come l'addizione, la divisione, il fattoriale, l'esponenziale, la ricerca dell'ennesimo numero primo, e molte altre (Brainerd and Landweber, 1974). Infatti è difficile progettare una funzione che sia ricorsiva totale ma non primitiva ricorsiva, anche se se ne conoscono alcune, come la funzione di Ackermann. Perciò studiando questo particolare tipo di funzioni è possibile scoprire proprietà che hanno conseguenza di ampia portata. Le funzioni ricorsive primitive possono essere calcolate dalle macchine che terminano sempre, mentre le funzioni ricorsive richiedono sistemi con la stessa potenza di calcolo delle macchine di Turing.