Naar inhoud springen

Ackermannfunctie

Zoek dit woord op in WikiWoordenboek
Uit Wikipedia, de vrije encyclopedie

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.

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

Eigenschappen

[bewerken | brontekst bewerken]

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.

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


  1. versie van Rózsa Péter