Funzione ricorsiva primitiva

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

Definiamo primitiva ricorsiva una funzione che o fa parte delle funzioni base, oppure può essere ottenuta a partire dalle funzioni base 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[modifica | modifica sorgente]

Definiamo come funzioni base le seguenti funzioni:

  • Le funzioni zero, che prendono n argomenti (con n\ge \;0), e che restituiscono sempre 0. Sono perciò funzioni costanti.
Z(x_1, x_2, ..., x_n)= 0
  • La funzione successore S, che prende un argomento e restituisce il numero successivo
S(x)= x + 1
  • Le funzioni di proiezione (dette anche funzioni selettive o funzioni identità), che prendono n argomenti (n\ge 1) e restituiscono l'i-esimo tra essi (1\le i\le n).
P_i^n(x_1, x_2, ..., x_n)= x_i

e prendiamo come tre assiomi il fatto che siano tutte ricorsive primitive.

Composizione e ricorsione[modifica | modifica sorgente]

È 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, ..., g_n sono funzioni tutte a m argomenti, allora la funzione h a m argomenti:
h(x_1, ..., x_m) = f(g_1(x_1, ..., x_m), ..., g_n(x_1, ..., x_m))
è ottenuta per composizione (o sostituzione) da f e g_1, ..., 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, ..., x_n, 0) = f(x_1, ..., x_n)
  2. h(x_1, ..., x_n, y+1) = g(x_1, ..., x_n, y, h(x_1, ..., 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[modifica | modifica sorgente]

Addizione[modifica | modifica sorgente]

La funzione Addizione (+) in quanto funzione ricorsiva può essere definita mediante ricorsione primitiva a partire dalla funzione di base Successore (\mbox{S}) nel seguente modo:
+(x,0)=x
+(x,\mbox{S}(y))=\mbox{S}(+(x,y))

Sottrazione[modifica | modifica sorgente]

Per definire la funzione Sottrazione (-) come funzione ricorsiva ci si appoggia alla definizione della funzione ricorsiva Predecessore (\mbox{pred}), definita a sua volta per ricorsione primitiva a partire dalla funzione di base Identità (P_i):
\mbox{pred}(0)=0
\mbox{pred}(y+1)=P_{1,1}(y)

Si ricava quindi la funzione Sottrazione (-):
-(x,0)=x
-(x,\mbox{S}(y))=-(\mbox{pred}(x),y)

Moltiplicazione[modifica | modifica sorgente]

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,\mbox{S}(y))=+(x,\cdot(x,y))

Fattoriale[modifica | modifica sorgente]

La funzione Fattoriale(!) in quanto funzione ricorsiva può essere definita mediante l'ausilio della già definita funzione Moltiplicazione (·) e precisamente:
(0)=S(0)
(x)=·(!(pred(x)),x)

Chiamando: "S" la funzione successore, "I" la funzione identità, "p" la funzione proiezione, "Z" la funzione zero, e
"E" l'esponenziazione, "R" la ripetizione, "o" la composizione e "x" la combinazione
Pd = funzione predecessore (prende x in input e ritorna x-1),
D1 = funzione diagonalizzazione (prende x e torna la coppia x,x)
M = funzione moltiplicazione

la funzione fattoriale risulta quindi definibile come:

Fattoriale(x) = (I x p) ( (M x Pd) (I x D1) ) E o (I x D1) o (I x Pd) o (D1) (x)

Limitazioni[modifica | modifica sorgente]

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[modifica | modifica sorgente]

  • 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[modifica | modifica sorgente]