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
+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 Wilhelm Ackermann
Kategori:Funktioner Kategori:Rekursion