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.

DefinitieBewerken

De ackermann-péterfunctie, kort ackermannfunctie, heeft twee natuurlijke getallen   en   als argumenten en is als volgt[1] (recursief) gedefinieerd:

 

EigenschappenBewerken

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.

VoorbeeldenBewerken

De waarde van de ackermannfunctie voor   en   is:

 

Nu is

 

dus

 

Hieronder staat de berekening van

 

Tussenresultaten zijn:

 
 
 
 
Berekeningenn
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Door gebruik te maken van de identiteiten:

 

en

 ,

die direct met inductie volgen uit:

 

en

 ,

is de berekening:

 
 
 
 
 

Verder is

 
 
 
 
 
 

etc.

 
 

Al snel worden de waarden groter:

 

en

 




ReferentiesBewerken

  1. versie van Rózsa Péter