Funzione di Ackermann 📖 Wikipedia

In matematica, la funzione di Ackermann è una funzione ${\displaystyle 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:

${\displaystyle f(0,0,z)=z;}$

${\displaystyle f(0,y+1,z)=f(0,y,z)+1;}$

${\displaystyle f(1,0,z)=0;}$

${\displaystyle f(x+2,0,z)=1;}$

${\displaystyle f(x+1,y+1,z)=f(x,[f(x+1,y,z)],z).}$

Un caso particolare è la funzione di Ackermann a due argomenti ${\displaystyle A(m,n)}$, così definita:

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

La funzione di Ackermann è definita per ogni coppia ${\displaystyle (m,n)}$ di numeri naturali ed è sempre computabile.^[1]

Il valore cresce molto rapidamente anche per valori molto piccoli di ${\displaystyle m}$ e ${\displaystyle n}$. Per esempio, ${\displaystyle A(4,2)}$ è un numero intero di 19 729 cifre.^[2] Per confronto, la costante di Avogadro ha solo 24 cifre.

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, seguite dalla tetrazione, e successivamente si hanno funzioni sempre più complesse:

${\displaystyle f(0,y,z)=y+z}$

${\displaystyle f(1,y,z)=y\times z}$ (mediante iterazione di ${\displaystyle z+z+z+\ldots }$ per ${\displaystyle y}$ volte)

${\displaystyle f(2,y,z)=z^{y}}$ (mediante iterazione di ${\displaystyle z\times z\times z\times \ldots }$ per ${\displaystyle y}$ volte)

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

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

L'inversa della funzione di Ackermann, indicata con ${\displaystyle \alpha }$, compare in alcune dimostrazioni di scienze informatiche, come nell'algoritmo union-find.

La funzione di Ackermann è un classico esempio di funzione ricorsiva non ricorsiva primitiva. Questo risultato è un corollario diretto del seguente lemma di maggiorazione:

Per ogni funzione ricorsiva primitiva ${\displaystyle f\colon \mathbb {N} ^{d}\to \mathbb {N} }$ esiste ${\displaystyle M\in \mathbb {N} }$ tale che per ogni ${\displaystyle {\overline {x}}\in \mathbb {N} ^{d}}$ si ha ${\displaystyle f({\overline {x}})<A(M,\max({\overline {x}}))}$.

Infatti, se fosse ricorsiva primitiva, allora la funzione diagonale ${\displaystyle f(n):=A(n,n)}$ sarebbe ricorsiva primitiva. Per il lemma di maggiorazione, esisterebbe ${\displaystyle M\in \mathbb {N} }$ tale che ${\displaystyle f(n)<A(M,n)}$ per ogni ${\displaystyle n}$ naturale. Ma allora ${\displaystyle f(M)<A(M,M)}$, che è in contraddizione con la definizione di ${\displaystyle f}$.^[1]

• Wilhelm Ackermann
• Tetrazione
• Notazione a frecce di Knuth

• Ackermann, funzione di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Ackermann Function, su MathWorld, Wolfram Research.
• (EN) Ackermann function, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.

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