Ackermannfunktionen är ett exempel på en beräkningsbar funktion som inte är primitivt rekursiv.

Ackermannfunktionen definieras för icke-negativa heltal och enligt:

Från definitionen syns tydligt att för växer väldigt snabbt, redan för låga värden på n. Exempelvis är skrivet i decimal form ett heltal med över 19 000 siffror.

För specifika värden på , då kan beskrivas med relativt enkla medel:

För större värden på växer funktionen alltför snabbt för att beskrivas med några av de elementära räknesätten. I stället kan Knuths pilnotation användas.

Generellt gäller att

Med hjälp av denna beskrivning kan rekursionen av göras något enklare.

Och då

förstås att detta tal utskrivet i decimal form har 19 729 siffror.

Ackermannstal redigera

Värden på  
 
0 1 2 3 4  
  0 1 2 3 4 5  
1 2 3 4 5 6  
2 3 5 7 9 11  
3 5 13 29 61 125  
4 13

= 
65533

= 
265536 − 3

= 
 

= 
 

= 
 
5 65533

= 
         
6            

Se även redigera