title: Ackermannfunctie
text: In de berekenbaarheidstheorie is de ackermannfunctie, genoemd naar Wilhelm Ackermann, die de functie in 1926 opstelde, een van de eenvoudigste en vroegst ontdekte voorbeelden van een totale berekenbare functie die niet primitief recursief is. Alle primitieve recursieve functies zijn totaal en berekenbaar, maar de ackermannfunctie illustreert dat niet alle totale berekenbare functies primitief recursief zijn. De ackermannfunctie is een extreem snel toenemende functie met behulp waarvan de grenzen aan computer- en rekenmodellen in de theoretische informatica kunnen worden aangetoond. Na Ackermanns publicatie van de functie (die drie natuurlijke getallen als argumenten had), hebben veel auteurs het concept aangepast voor verschillende doeleinden, zodat tegenwoordig "ackermannfunctie" kan verwijzen naar een van de vele varianten van de oorspronkelijke door Ackermann opgestelde functie. Deze hebben alle een vormingsregel vergelijkbaar met de oorspronkelijke ackermannfunctie en hebben ook een vergelijkbaar groeigedrag. Een veelgebruikte versie, de ackermann-péterfunctie, heeft twee argumenten en is hieronder gedefinieerd.
  
  Definitie
  De ackermann-péterfunctie, kort ackermannfunctie, heeft twee natuurlijke getallen  en  als argumenten en is als volgt (recursief) gedefinieerd:
  
  Eigenschappen
  Deze functie is voor alle waarden van  en  gedefinieerd, dat wil zeggen dat voor alle waarden van  en  de berekening ooit stopt. Dat is het geval omdat in elke recursieve aanroep van de functie ofwel het eerste argument  daalt, ofwel het eerste argument  gelijk blijft en het tweede argument  daalt. Ook in het tweede geval daalt het eerste argument uiteindelijk, namelijk als  tot 0 gedaald is. Daardoor treedt altijd ooit het basisgeval  op.
  
  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.
  
  Voorbeelden
  De waarde van de ackermannfunctie voor  en  is:
  
  Nu is
  
  dus
  
  Hieronder staat de berekening van
  
  Tussenresultaten zijn:
  
  Al snel worden de waarden groter:
  
  en
  
  Referenties
  
  Wiskundige functie