Zoek dit woord op in WikiWoordenboek

Ackermannfunctie

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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 ackermannfunctie heeft twee gehele getallen en als argumenten en is als volgt (recursief) gedefinieerd:

Eigenschappen[bewerken]

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.

Voorbeeld[bewerken]

De ackermannfunctie van en wordt als volgt berekend:

hierin is

dus