Ackermannfunctie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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

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

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

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
Bronnen, noten en/of referenties