Ackermannfunctie

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

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