Ackermannfunctie

De Ackermannfunctie (genoemd naar Wilhelm Ackermann) is een voorbeeld van een niet-primitief recursieve functie. Het is een van de bekendste voorbeelden van een functie die meer dan exponentieel stijgt.

Definitie

De functie heeft twee gehele getallen m en n als argumenten en is als volgt (recursief) gedefinieerd:

$A(m,n)= \left\{ \begin{array}{ll} n+1 &\mbox{als }m=0;\ \ \qquad\qquad \\ A(m-1, 1) &\mbox{als }m>0\mbox{ en }n=0; \\ A(m-1, A(m, n-1)) &\mbox{anders.} \end{array} \right.$

Eigenschappen

Merk op dat deze functie voor alle waarden van m en n gedefinieerd is. Dit komt doordat in elke stap n afneemt, of n stijgt en m daalt. Als n nul bereikt, daalt m, dus m moet uiteindelijk ook nul worden. 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