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.

Definizione

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 ${\mathcal {P}}$ 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: $\mathbb {N} ^{n}\rightarrow \mathbb {N}$. In generale prendono come argomenti una tupla di $n$ numeri naturali e restituiscono un numero naturale. Una funzione che prende $n$ argomenti si dice $n$-aria.

Funzioni base

Definiamo come funzioni base le seguenti:

• Le funzioni zero, che prendono $n$ argomenti (con $n\geq 0$), e che restituiscono sempre 0. Sono perciò funzioni costanti.

$Z(x_{1},x_{2},\ldots ,x_{n})=0.$

• La funzione successore $\mathrm {S}$, che prende un argomento e restituisce il numero successivo

$\mathrm {S} (x)=x+1.$

• Le funzioni di proiezione (dette anche funzioni selettive o funzioni identità), che prendono $n$ argomenti ($n\geq 1$) e restituiscono l'$i$-esimo tra essi ($1\leq i\leq n$).

$P_{i}^{n}(x_{1},x_{2},\ldots ,x_{n})=x_{i}.$

Prendiamo come tre assiomi il fatto che siano tutte ricorsive primitive.

Composizione e ricorsione

È possibile ottenere funzioni ricorsive primitive più complesse di quelle base, applicando a queste ultime i seguenti operatori:

• L'operatore di composizione (o sostituzione):

se $f$ è una funzione a $n$ argomenti, e $g_{1},\ldots ,g_{n}$ sono funzioni tutte a $m$ argomenti, allora la funzione $h$ a $m$ argomenti:

$h(x_{1},\ldots ,x_{m})=f(g_{1}(x_{1},\ldots ,x_{m}),\ldots ,g_{n}(x_{1},\ldots ,x_{m}))$

è ottenuta per composizione (o sostituzione) da $f$ e $g_{1},\ldots ,g_{n}$

• L'operatore di ricorsione primitiva:

se $f$ è una funzione a $n$ argomenti, e $g$ è una funzione a $n+2$ argomenti, allora la funzione $h$ a $n+1$ argomenti così definita:

1. $h(x_{1},\ldots ,x_{n},0)=f(x_{1},\ldots ,x_{n})$
2. $h(x_{1},\ldots ,x_{n},\mathrm {S} (y))=g(x_{1},\ldots ,x_{n},y,h(x_{1},\ldots ,x_{n},y))$

è ottenuta per ricorsione primitiva da $f$ e $g$

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.

Esempi

Addizione

La funzione addizione ($+$) in quanto funzione ricorsiva può essere definita mediante ricorsione primitiva a partire dalla funzione di base successore $(\mathrm {S} )$ nel seguente modo:

$+(x,0)=x;$

$+(x,\mathrm {S} (y))=\mathrm {S} (P_{3}^{3}(x,y,+(x,y)))=\mathrm {S} (+(x,y)).$

Sottrazione

Per definire la funzione sottrazione ($-$) come funzione ricorsiva, ci si appoggia alla definizione della funzione ricorsiva predecessore $(\mathrm {pred} )$, definita a sua volta per ricorsione primitiva a partire dalle funzioni di base identità $(P_{i}^{n})$:

$\mathrm {pred} (0)=0;$

$\mathrm {pred} (\mathrm {S} (y))=P_{1}^{2}\left(y,\mathrm {pred} (y)\right)=y.$

Si ricava quindi la funzione sottrazione ($-$):

$-(x,0)=x;$

$-(x,\mathrm {S} (y))=\mathrm {pred} (P_{3}^{3}(x,y,-(x,y)))=\mathrm {pred} (-(x,y)).$

Moltiplicazione

La funzione moltiplicazione ($\cdot$) in quanto funzione ricorsiva può essere definita mediante l'ausilio della già definita funzione addizione ($+$) e precisamente:

$\cdot (x,0)=0;$

$\cdot (x,\mathrm {S} (y))=+(P_{1}^{2}(x,y),\cdot (x,y))=+(x,\cdot (x,y)).$

Fattoriale

La funzione fattoriale ($!$) in quanto funzione ricorsiva può essere definita mediante l'ausilio della già definita funzione moltiplicazione ($\cdot$) e precisamente:

$!(0)=\mathrm {S} (0)$

$!(\mathrm {S} (y))=\cdot (\mathrm {S} (y),!(y)).$

Limitazioni

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.

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

Voci correlate

• L (linguaggio)

Collegamenti esterni

• (EN) primitive recursive function, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.