Ackermannfunktionen

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

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

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

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

För specifika värden på, då m<4 kan A(m,n) beskrivas med relativt enkla medel.

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

Med hjälp av denna beskrivning kan rekursionen av A(4,2) göras något enklare.

Och då

syns att detta tal utskrivet i decimal form skulle ha 19729 siffror.

Ackermannstal[redigera | redigera wikitext]

Värden på A(mn)
m\n 0 1 2 3 4 n
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]