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.
Definiamo primitiva ricorsiva una funzione che fa parte delle funzioni base, oppure può essere ottenuta a partire da queste applicando la composizione e la ricorsione primitiva un numero finito di volte; equivalentemente, l'insieme delle funzioni ricorsive primitive è definito come il più piccolo insieme contenente le funzioni ricorsive di base e che sia chiuso per composizione e ricorsione primitiva.
Le funzioni ricorsive vanno dai naturali ai naturali: . In generale prendono come argomenti una tupla di numeri naturali e restituiscono un numero naturale. Una funzione che prende argomenti si dice -aria.
Definiamo come funzioni base le seguenti:
Prendiamo come tre assiomi il fatto che siano tutte ricorsive primitive.
È possibile ottenere funzioni ricorsive primitive più complesse di quelle base, applicando a queste ultime i seguenti operatori:
Si noti che, grazie alle funzioni di proiezione, possiamo aggirare l'apparente rigidità del numero di argomenti delle funzioni suddette, dato che, grazie alla composizione, possiamo passare qualunque sottoinsieme degli argomenti.
La funzione addizione () in quanto funzione ricorsiva può essere definita mediante ricorsione primitiva a partire dalla funzione di base successore nel seguente modo:
Per definire la funzione sottrazione () come funzione ricorsiva, ci si appoggia alla definizione della funzione ricorsiva predecessore , definita a sua volta per ricorsione primitiva a partire dalle funzioni di base identità :
Si ricava quindi la funzione sottrazione ():
La funzione moltiplicazione () in quanto funzione ricorsiva può essere definita mediante l'ausilio della già definita funzione addizione () e precisamente:
La funzione fattoriale () in quanto funzione ricorsiva può essere definita mediante l'ausilio della già definita funzione moltiplicazione () e precisamente:
Sebbene tutte le funzioni primitive ricorsive siano totali, esistono funzioni totali che non sono primitive ricorsive: un esempio è la funzione di Ackermann, che è calcolabile, totale, ma non ricorsiva primitiva.
Esistendo quindi delle funzioni non descrivibili da questo formalismo, esso non è adeguato a rappresentare quelle che intuitivamente sono le funzioni calcolabili. L'estensione delle funzioni primitive ricorsive che rappresenta tutte le funzioni calcolabili (ovvero ha la stessa espressività della macchina di Turing), è quella delle funzioni ricorsive.