Ackermannfunktionen

Från Wikipedia
(Omdirigerad från Ackermanntalen)
Hoppa till navigering Hoppa till sök

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 | redigera wikitext]

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 | redigera wikitext]