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.

Definitie

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

A ⁡ ( 0 , n ) = n + 1 A ⁡ ( m , 0 ) = A ⁡ ( m − 1 , 1 ) als  m > 0 A ⁡ ( m , n ) = A ⁡ ( m − 1 , A ( m , n − 1 ) ) als  m > 0  en  n > 0 {\displaystyle {\begin{array}{lcl}\operatorname {A} (0,n)&=&n+1\\\operatorname {A} (m,0)&=&\operatorname {A} (m-1,1)&{\mbox{als }}m>0\\\operatorname {A} (m,n)&=&\operatorname {A} (m-1,A(m,n-1))&{\mbox{als }}m>0{\mbox{ en }}n>0\end{array}}}

Eigenschappen

Deze functie is voor alle waarden van m {\displaystyle m} en n {\displaystyle n} gedefinieerd, dat wil zeggen dat voor alle waarden van m {\displaystyle m} en n {\displaystyle n} de berekening ooit stopt. Dat is het geval omdat in elke recursieve aanroep van de functie ofwel het eerste argument m {\displaystyle m} daalt, ofwel het eerste argument m {\displaystyle m} gelijk blijft en het tweede argument n {\displaystyle n} daalt. Ook in het tweede geval daalt het eerste argument uiteindelijk, namelijk als n {\displaystyle n} tot 0 gedaald is. Daardoor treedt altijd ooit het basisgeval A ( 0 , n ) {\displaystyle A(0,n)} op.

De ackermannfunctie neemt al bij kleine waarden van m {\displaystyle m} en n {\displaystyle n} 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 m = 1 {\displaystyle m=1} en n = 1 {\displaystyle n=1} is:

A ( 1 , 1 ) = A ( 0 , A ( 1 , 0 ) ) {\displaystyle A(1,1)=A(0,A(1,0))}

Nu is

A ( 1 , 0 ) = A ( 0 , 1 ) = 2 {\displaystyle A(1,0)=A(0,1)=2}

dus

A ( 1 , 1 ) = A ( 0 , A ( 1 , 0 ) ) = A ( 0 , 2 ) = 3 {\displaystyle A(1,1)=A(0,A(1,0))=A(0,2)=3}

Hieronder staat de berekening van

A ( 3 , 2 ) = 29 {\displaystyle A(3,2)=29}

Tussenresultaten zijn:

A ( 3 , 0 ) = 5 {\displaystyle A(3,0)=5}
A ( 3 , 1 ) = 13 {\displaystyle A(3,1)=13}
A ( 2 , n ) = 2 n + 3 , n = 0 , 1 … , 13 {\displaystyle A(2,n)=2n+3,\quad n=0,1\ldots ,13}
A ( 1 , n ) = n + 2 , n = 0 , 1 … , 27 {\displaystyle A(1,n)=n+2,\quad n=0,1\ldots ,27}
Berekeningenn 
  A ( 3 , 2 ) = A ( 2 , A ( 3 , 1 ) ) {\displaystyle \ A(3,2)=A(2,A(3,1))}
−   A ( 3 , 1 ) = A ( 2 , A ( 3 , 0 ) ) {\displaystyle -\ A(3,1)=A(2,A(3,0))}
− −   A ( 3 , 0 ) = A ( 2 , 1 ) {\displaystyle --\ A(3,0)=A(2,1)}
− − −   A ( 2 , 1 ) = A ( 1 , A ( 2 , 0 ) ) {\displaystyle ---\ A(2,1)=A(1,A(2,0))}
− − − −   A ( 2 , 0 ) = A ( 1 , 1 ) {\displaystyle ----\ A(2,0)=A(1,1)}
− − − − −   A ( 1 , 1 ) = A ( 0 , A ( 1 , 0 ) ) {\displaystyle -----\ A(1,1)=A(0,A(1,0))}
− − − − − −   A ( 1 , 0 ) = A ( 0 , 1 ) = 2 {\displaystyle ------\ A(1,0)=A(0,1)=2}
− − − − −   A ( 1 , 1 ) = A ( 0 , 2 ) = 3 {\displaystyle -----\ A(1,1)=A(0,2)=3}
− − − −   A ( 2 , 0 ) = 3 {\displaystyle ----\ A(2,0)=3}
− − −   A ( 2 , 1 ) = A ( 1 , 3 ) {\displaystyle ---\ A(2,1)=A(1,3)}
− − − −   A ( 1 , 3 ) = A ( 0 , A ( 1 , 2 ) ) {\displaystyle ----\ A(1,3)=A(0,A(1,2))}
− − − − −   A ( 1 , 2 ) = A ( 0 , 3 ) = 4 {\displaystyle -----\ A(1,2)=A(0,3)=4}
− − − −   A ( 1 , 3 ) = A ( 0 , 4 ) = 5 {\displaystyle ----\ A(1,3)=A(0,4)=5}
− − −   A ( 2 , 1 ) = 5 {\displaystyle ---\ A(2,1)=5}
− −   A ( 3 , 0 ) = 5 {\displaystyle --\ A(3,0)=5}
−   A ( 3 , 1 ) = A ( 2 , 5 ) {\displaystyle -\ A(3,1)=A(2,5)}
− −   A ( 2 , 5 ) = A ( 1 , A ( 2 , 4 ) ) {\displaystyle --\ A(2,5)=A(1,A(2,4))}
− − −   A ( 2 , 4 ) = A ( 1 , A ( 2 , 3 ) ) {\displaystyle ---\ A(2,4)=A(1,A(2,3))}
− − − −   A ( 2 , 3 ) = A ( 1 , A ( 2 , 2 ) ) {\displaystyle ----\ A(2,3)=A(1,A(2,2))}
− − − − −   A ( 2 , 2 ) = A ( 1 , 5 ) {\displaystyle -----\ A(2,2)=A(1,5)}
− − − − − −   A ( 1 , 5 ) = A ( 0 , A ( 1 , 4 ) ) {\displaystyle ------\ A(1,5)=A(0,A(1,4))}
− − − − − − −   A ( 1 , 4 ) = A ( 0 , 5 ) = 6 {\displaystyle -------\ A(1,4)=A(0,5)=6}
− − − − − −   A ( 1 , 5 ) = A ( 0 , 6 ) = 7 {\displaystyle ------\ A(1,5)=A(0,6)=7}
− − − − −   A ( 2 , 2 ) = 7 {\displaystyle -----\ A(2,2)=7}
− − − −   A ( 2 , 3 ) = A ( 1 , 7 ) {\displaystyle ----\ A(2,3)=A(1,7)}
− − − − −   A ( 1 , 7 ) = A ( 0 , A ( 1 , 6 ) ) {\displaystyle -----\ A(1,7)=A(0,A(1,6))}
− − − − − −   A ( 1 , 6 ) = A ( 0 , 7 ) = 8 {\displaystyle ------\ A(1,6)=A(0,7)=8}
− − − − −   A ( 1 , 7 ) = A ( 0 , 8 ) = 9 {\displaystyle -----\ A(1,7)=A(0,8)=9}
− − − −   A ( 2 , 3 ) = 9 {\displaystyle ----\ A(2,3)=9}
− − −   A ( 2 , 4 ) = A ( 1 , 9 ) {\displaystyle ---\ A(2,4)=A(1,9)}
− − − −   A ( 1 , 9 ) = A ( 0 , A ( 1 , 8 ) ) {\displaystyle ----\ A(1,9)=A(0,A(1,8))}
− − − − −   A ( 1 , 8 ) = A ( 0 , 9 ) = 10 {\displaystyle -----\ A(1,8)=A(0,9)=10}
− − − −   A ( 1 , 9 ) = A ( 0 , 10 ) = 11 {\displaystyle ----\ A(1,9)=A(0,10)=11}
− − −   A ( 2 , 4 ) = 11 {\displaystyle ---\ A(2,4)=11}
− −   A ( 2 , 5 ) = A ( 1 , 11 ) {\displaystyle --\ A(2,5)=A(1,11)}
− − −   A ( 1 , 11 ) = A ( 0 , A ( 1 , 10 ) ) {\displaystyle ---\ A(1,11)=A(0,A(1,10))}
− − − −   A ( 1 , 10 ) = A ( 0 , 11 ) = 12 {\displaystyle ----\ A(1,10)=A(0,11)=12}
− − −   A ( 1 , 11 ) = A ( 0 , 12 ) = 13 {\displaystyle ---\ A(1,11)=A(0,12)=13}
− −   A ( 2 , 5 ) = 13 {\displaystyle --\ A(2,5)=13}
−   A ( 3 , 1 ) = 13 {\displaystyle -\ A(3,1)=13}
  A ( 3 , 2 ) = A ( 2 , 13 ) {\displaystyle \ A(3,2)=A(2,13)}
−   A ( 2 , 13 ) = A ( 1 , A ( 2 , 12 ) ) {\displaystyle -\ A(2,13)=A(1,A(2,12))}
− −   A ( 2 , 12 ) = A ( 1 , A ( 2 , 11 ) ) {\displaystyle --\ A(2,12)=A(1,A(2,11))}
− − −   A ( 2 , 11 ) = A ( 1 , A ( 2 , 10 ) ) {\displaystyle ---\ A(2,11)=A(1,A(2,10))}
− − − −   A ( 2 , 10 ) = A ( 1 , A ( 2 , 9 ) ) {\displaystyle ----\ A(2,10)=A(1,A(2,9))}
− − − − −   A ( 2 , 9 ) = A ( 1 , A ( 2 , 8 ) ) {\displaystyle -----\ A(2,9)=A(1,A(2,8))}
− − − − − −   A ( 2 , 8 ) = A ( 1 , A ( 2 , 7 ) ) {\displaystyle ------\ A(2,8)=A(1,A(2,7))}
− − − − − − −   A ( 2 , 7 ) = A ( 1 , A ( 2 , 6 ) ) {\displaystyle -------\ A(2,7)=A(1,A(2,6))}
− − − − − − − −   A ( 2 , 6 ) = A ( 1 , 13 ) {\displaystyle --------\ A(2,6)=A(1,13)}
− − − − − − − − −   A ( 1 , 13 ) = A ( 0 , A ( 1 , 12 ) ) {\displaystyle ---------\ A(1,13)=A(0,A(1,12))}
− − − − − − − − − −   A ( 1 , 12 ) = A ( 0 , 13 ) = 14 {\displaystyle ----------\ A(1,12)=A(0,13)=14}
− − − − − − − − −   A ( 1 , 13 ) = A ( 0 , 14 ) = 15 {\displaystyle ---------\ A(1,13)=A(0,14)=15}
− − − − − − − −   A ( 2 , 6 ) = 15 {\displaystyle --------\ A(2,6)=15}
− − − − − − −   A ( 2 , 7 ) = A ( 1 , 15 ) {\displaystyle -------\ A(2,7)=A(1,15)}
− − − − − − − −   A ( 1 , 15 ) = A ( 0 , A ( 1 , 14 ) ) {\displaystyle --------\ A(1,15)=A(0,A(1,14))}
− − − − − − − − −   A ( 1 , 14 ) = A ( 0 , 15 ) = 16 {\displaystyle ---------\ A(1,14)=A(0,15)=16}
− − − − − − − −   A ( 1 , 15 ) = A ( 0 , 16 ) = 17 {\displaystyle --------\ A(1,15)=A(0,16)=17}
− − − − − − −   A ( 2 , 7 ) = 17 {\displaystyle -------\ A(2,7)=17}
− − − − − −   A ( 2 , 8 ) = A ( 1 , 17 ) {\displaystyle ------\ A(2,8)=A(1,17)}
− − − − − − −   A ( 1 , 17 ) = A ( 0 , A ( 1 , 16 ) ) {\displaystyle -------\ A(1,17)=A(0,A(1,16))}
− − − − − − − −   A ( 1 , 16 ) = A ( 0 , 17 ) = 18 {\displaystyle --------\ A(1,16)=A(0,17)=18}
− − − − − − −   A ( 1 , 17 ) = A ( 0 , 18 ) = 19 {\displaystyle -------\ A(1,17)=A(0,18)=19}
− − − − − −   A ( 2 , 8 ) = 19 {\displaystyle ------\ A(2,8)=19}
− − − − −   A ( 2 , 9 ) = A ( 1 , 19 ) {\displaystyle -----\ A(2,9)=A(1,19)}
− − − − − −   A ( 1 , 19 ) = A ( 0 , A ( 1 , 18 ) ) {\displaystyle ------\ A(1,19)=A(0,A(1,18))}
− − − − − − −   A ( 1 , 18 ) = A ( 0 , 19 ) = 20 {\displaystyle -------\ A(1,18)=A(0,19)=20}
− − − − − −   A ( 1 , 19 ) = A ( 0 , 20 ) = 21 {\displaystyle ------\ A(1,19)=A(0,20)=21}
− − − − −   A ( 2 , 9 ) = 21 {\displaystyle -----\ A(2,9)=21}
− − − −   A ( 2 , 10 ) = A ( 1 , 21 ) {\displaystyle ----\ A(2,10)=A(1,21)}
− − − − −   A ( 1 , 21 ) = A ( 0 , A ( 1 , 20 ) ) {\displaystyle -----\ A(1,21)=A(0,A(1,20))}
− − − − − −   A ( 1 , 20 ) = A ( 0 , 21 ) = 22 {\displaystyle ------\ A(1,20)=A(0,21)=22}
− − − − −   A ( 1 , 21 ) = A ( 0 , 22 ) = 23 {\displaystyle -----\ A(1,21)=A(0,22)=23}
− − − −   A ( 2 , 10 ) = 23 {\displaystyle ----\ A(2,10)=23}
− − −   A ( 2 , 11 ) = A ( 1 , 23 ) {\displaystyle ---\ A(2,11)=A(1,23)}
− − − −   A ( 1 , 23 ) = A ( 0 , A ( 1 , 22 ) ) {\displaystyle ----\ A(1,23)=A(0,A(1,22))}
− − − − − −   A ( 1 , 22 ) = A ( 0 , 23 ) = 24 {\displaystyle ------\ A(1,22)=A(0,23)=24}
− − − −   A ( 1 , 23 ) = A ( 0 , 24 ) = 25 {\displaystyle ----\ A(1,23)=A(0,24)=25}
− − −   A ( 2 , 11 ) = 25 {\displaystyle ---\ A(2,11)=25}
− −   A ( 2 , 12 ) = A ( 1 , 25 ) {\displaystyle --\ A(2,12)=A(1,25)}
− − −   A ( 1 , 25 ) = A ( 0 , A ( 1 , 24 ) ) {\displaystyle ---\ A(1,25)=A(0,A(1,24))}
− − − −   A ( 1 , 24 ) = A ( 0 , 25 ) = 26 {\displaystyle ----\ A(1,24)=A(0,25)=26}
− − −   A ( 1 , 25 ) = A ( 0 , 26 ) = 27 {\displaystyle ---\ A(1,25)=A(0,26)=27}
− −   A ( 2 , 12 ) = 27 {\displaystyle --\ A(2,12)=27}
−   A ( 2 , 13 ) = A ( 1 , 27 ) {\displaystyle -\ A(2,13)=A(1,27)}
− −   A ( 1 , 27 ) = A ( 0 , A ( 1 , 26 ) ) {\displaystyle --\ A(1,27)=A(0,A(1,26))}
− − −   A ( 1 , 26 ) = A ( 0 , A ( 1 , 25 ) ) = A ( 0 , 27 ) = 28 {\displaystyle ---\ A(1,26)=A(0,A(1,25))=A(0,27)=28}
− −   A ( 1 , 27 ) = A ( 0 , 28 ) = 29 {\displaystyle --\ A(1,27)=A(0,28)=29}
−   A ( 2 , 13 ) = 29 {\displaystyle -\ A(2,13)=29}
  A ( 3 , 2 ) = 29 {\displaystyle \ A(3,2)=29}

Door gebruik te maken van de identiteiten:

A ( 1 , n ) = n + 2 {\displaystyle A(1,n)=n+2}

en

A ( 2 , n ) = 2 n + 3 {\displaystyle A(2,n)=2n+3} ,

die direct met inductie volgen uit:

A ( 1 , n + 1 ) = A ( 0 , A ( 1 , n ) = A ( 0 , n + 2 ) = n + 3 = ( n + 1 ) + 2 {\displaystyle A(1,n+1)=A(0,A(1,n)=A(0,n+2)=n+3=(n+1)+2}

en

A ( 2 , n + 1 ) = A ( 1 , A ( 2 , n ) ) = A ( 1 , 2 n + 3 ) = 2 n + 5 = 2 ( n + 1 ) + 3 {\displaystyle A(2,n+1)=A(1,A(2,n))=A(1,2n+3)=2n+5=2(n+1)+3} ,

is de berekening:

A ( 3 , 2 ) = A ( 2 , A ( 3 , 1 ) ) = 2 A ( 3 , 1 ) + 3 {\displaystyle A(3,2)=A(2,A(3,1))=2A(3,1)+3}
A ( 3 , 1 ) = A ( 2 , A ( 3 , 0 ) ) = 2 A ( 3 , 0 ) + 3 {\displaystyle A(3,1)=A(2,A(3,0))=2A(3,0)+3}
A ( 3 , 0 ) = A ( 2 , 1 ) = 2 + 3 = 5 {\displaystyle A(3,0)=A(2,1)=2+3=5}
A ( 3 , 1 ) = 13 {\displaystyle A(3,1)=13}
A ( 3 , 2 ) = 29 {\displaystyle A(3,2)=29}

Verder is

A ( 4 , 1 ) = A ( 3 , A ( 4 , 0 ) ) {\displaystyle A(4,1)=A(3,A(4,0))}
A ( 4 , 0 ) = A ( 3 , 1 ) = 13 {\displaystyle A(4,0)=A(3,1)=13}
A ( 4 , 1 ) = A ( 3 , 13 ) {\displaystyle A(4,1)=A(3,13)}
A ( 3 , 13 ) = A ( 2 , A ( 3 , 12 ) ) = 2 A ( 3 , 12 ) + 3 {\displaystyle A(3,13)=A(2,A(3,12))=2A(3,12)+3}
A ( 3 , 12 ) = A ( 2 , A ( 3 , 11 ) ) = 2 A ( 3 , 11 ) + 3 {\displaystyle A(3,12)=A(2,A(3,11))=2A(3,11)+3}
A ( 3 , 13 ) = 4 A ( 3 , 11 ) + 9 {\displaystyle A(3,13)=4A(3,11)+9}

etc.

A ( 3 , 13 ) = 2 13 A ( 3 , 0 ) + 3 ( 1 + 2 + 4 + 8 + … ) = 2 13 A ( 3 , 0 ) + 3 ( 2 13 − 1 ) = {\displaystyle A(3,13)=2^{13}A(3,0)+3(1+2+4+8+\ldots )=2^{13}A(3,0)+3(2^{13}-1)=}
= 2 13 [ A ( 3 , 0 ) + 3 ] − 3 ) = 2 16 − 3 = 65536 − 3 = 65533 {\displaystyle =2^{13}[A(3,0)+3]-3)=2^{16}-3=65536-3=65533}

Al snel worden de waarden groter:

A ( 4 , 1 ) = 65533 {\displaystyle A(4,1)=65533}

en

A ( 4 , 2 ) = 2 65533 − 3 {\displaystyle A(4,2)=2^{65533}-3}


Bronnen, noten en/of referenties
  • Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Ackermann_function op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.

Referenties

  1. ↑ versie van Rózsa Péter
WikiWoordenboek