Funzione di Ackermann

Da Wikipedia, l'enciclopedia libera.

La funzione di Ackermann è una funzione f(x,y,z) che ha come dominio l'insieme delle terne di numeri naturali e come codominio i numeri naturali. Essa è definita per ricorrenza nel seguente modo:

 A(m, n) =
 \begin{cases}
 n+1 & \mbox{se } m = 0 \\
 A(m-1, 1) & \mbox{se } m > 0 \mbox{ e } n = 0 \\
 A(m-1, A(m, n-1)) & \mbox{se } m > 0 \mbox{ e } n > 0.
 \end{cases}

oppure:

f(0,0,z) = z
f(0,y+1,z) = f(0,y,z)+1
f(1,0,z) = 0
f(x+2,0,z) = 1
f(x+1,y+1,z) = f(x,[f(x+1,y,z)],z)



La funzione di Ackermann è un esempio di funzione ricorsiva che non è primitiva ricorsiva poiché cresce più velocemente di qualsiasi funzione ricorsiva primitiva.

Il meccanismo di calcolo della funzione è estremamente semplice quanto pesante dal punto di vista computazionale. La definizione data può essere vista come quella di una famiglia di funzioni al variare di un parametro individuato dalla prima variabile. Per ogni valore del parametro si ha una funzione che è ottenuta iterando la funzione precedente per un numero di volte individuato dalla seconda variabile. In quest'ottica le prime funzioni della famiglia sono funzioni familiari come l'addizione, la moltiplicazione e la potenza, e successivamente si hanno funzioni sempre più complesse:

f(0,y,z) = y+z
f(1,y,z) = y\times z (mediante iterazione di z+z+z+... per y volte)
f(2,y,z) = z^{y} (mediante iterazione di z\times z\times z\times... per y volte)
f(3,y,z) = z^{z^{z^{.^{.^{.}}}}} (y volte)(mediante iterazione di z^{z^{z^{.^{.^{.}}}}} per y volte e quindi mediante iterazione di y \times z e quindi mediante iterazione di y+z)

Risulta quindi una funzione con una complessità estremamente elevata anche per valori di input semplici.

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica