Ackermannfunctie

De ackermannfunctie (genoemd naar Wilhelm Ackermann) is een voorbeeld van een totale, berekenbare functie die niet primitief recursief is. Het is een van de bekendste voorbeelden van een functie die meer dan exponentieel stijgt.

Definitie

De ackermannfunctie heeft twee natuurlijke getallen $m$ en $n$ als argumenten en is als volgt (recursief) gedefinieerd:

${\begin{array}{lcl}\operatorname {A} (0,n)&=&n+1\\\operatorname {A} (m,0)&=&\operatorname {A} (m-1,1)&{\mbox{als }}m>0\\\operatorname {A} (m,n)&=&\operatorname {A} (m-1,A(m,n-1))&{\mbox{als }}m>0{\mbox{ en }}n>0\end{array}}$

Eigenschappen

Deze functie is voor alle waarden van $m$ en $n$ gedefinieerd, dat wil zeggen dat voor alle waarden van $m$ en $n$ de berekening ooit stopt. Dat is het geval omdat in elke recursieve aanroep van de functie ofwel het eerste argument $m$ daalt, ofwel het eerste argument $m$ gelijk blijft en het tweede argument $n$ daalt. Ook in het tweede geval daalt het eerste argument uiteindelijk, namelijk als $n$ tot 0 gedaald is. Daardoor treedt altijd ooit het basisgeval $A(0,n)$ op.

De ackermannfunctie neemt al bij kleine waarden van $m$ en $n$ zeer grote waarden aan: de waarden (4, 3) als invoer leveren een getal op met meer cijfers dan er elementaire deeltjes in het zichtbare heelal zijn.

Voorbeeld

De ackermannfunctie van $m=1$ en $n=1$ wordt als volgt berekend:

$A(1,1)=A(0,A(1,0))$

hierin is

$A(1,0)=A(0,1)=2$

dus

$A(0,A(1,0))=A(0,2)=3$

Referenties

WikiWoordenboek