Funzione ricorsiva primitiva

Da Wikipedia, l'enciclopedia libera.

Questa voce è solo un abbozzo (stub). Se puoi, contribuisci adesso a migliorarla secondo le convenzioni di Wikipedia. Per l'elenco completo degli stub di informatica, vedi la relativa categoria.

Questa voce è solo un abbozzo (stub). Se puoi, contribuisci adesso a migliorarla secondo le convenzioni di Wikipedia. Per l'elenco completo degli stub di matematica, vedi la relativa categoria.

Nella teoria della calcolabilità, le funzioni ricorsive primitive sono una classe di funzioni totali che possono essere definite applicando, un numero finito di volte, la ricorsione e la composizione a delle particolari funzioni base molto elementari (funzioni zero, funzione successore e funzioni selettive).

Le funzioni ricorsive primitive costituiscono un elemento fondamentale nella costruzione di una completa formalizzazione della calcolabilità. Le funzioni ricorsive primitive sono un sottoinsieme stretto delle funzioni ricorsive, che 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 ma non primitiva ricorsiva, anche se se ne conoscono alcune, come la funzione di Ackermann. Percio 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, metre le funzioni ricorsive richiedono sistemi con la stessa potenza di calcolo delle macchine di Turing.

[modifica] Definizione

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.

Le funzioni ricorsive vanno dai naturali ai naturali: . In generale prendono come argomenti una tupla di n numeri naturali e restituiscono una tupla di m naturali. Una funzione che prende n argomenti si dice n-aria.

[modifica] Funzioni base

Definiamo come funzioni base le seguenti funzioni:

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

1. La funzione successore S, che prende un argomento e restituisce il numero successivo come dato dagli assiomi di Peano.

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

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

[modifica] Composizione e ricorsione

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

1. L'operatore di composizione:
   data f, funzione primitiva ricorsiva con k argomenti,
   e k funzioni ad un argomento g₀,...,g_k-1,
   la composizione di f con g₀,...,g_k-1,
   cioè la funzione h(x₀,...,x_l-1) = f(g₀(x₀,...,x_l-1),...,g_k-1(x₀,...,x_l-1)), è primitiva ricorsiva.
2. L'operatore di ricorsione primitiva:
   data f, funzione primitiva ricorsiva con k argomenti,
   e g funzione primitiva ricorsiva con k+2 argomenti,
   la funzione a k+2 argomenti definita come la ricorsione primitiva di f e g,
   cioè la funzione h tale che h(0,x₀,...,x_k-1) = f(x₀,...,x_k-1) and h(S(n),x₀,...,x_k-1) = g(h(n,x₀,...,x_k-1),n,x₀,...,x_k-1), è primitiva ricorsiva.

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.

[modifica] Esempi

[modifica] Addizione

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

[modifica] Sottrazione

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

Si ricava quindi la funzione Sottrazione (-):
-(x,0)=P_i(x)
-(x,S(y))=pred(-(x,y))

[modifica] Moltiplicazione

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

[modifica] Fattoriale

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

[modifica] Limitazioni

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