Ackermannfunctie

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.