Ackermannfunktionen

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.