Hoofdmenu openen

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.

DefinitieBewerken

De ackermannfunctie heeft twee gehele getallen   en   als argumenten en is als volgt (recursief) gedefinieerd:

 

EigenschappenBewerken

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

VoorbeeldBewerken

De ackermannfunctie van   en   wordt als volgt berekend:

 

hierin is

 

dus