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: A(m, n) =
 \begin{cases}
 n+1 & \ m = 0 \\
 A(m-1, 1) & \ m > 0, n = 0 \\
 A(m-1, A(m, n-1)) & \ m > 0, n > 0.
 \end{cases}

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.

 A(m, n) =
 \begin{cases}
 n+1 & \ m = 0 \\
 n+2 & \ m = 1 \\
 2n+3 & \ m = 2 \\
 2^{n+3}-3 & \ m = 3 \\
  \end{cases}

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

A(m, n) = 2\uparrow^{m-2} (n+3) - 3.

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

A(4, 2) = 2\uparrow^{4-2}  (2+3) - 3 = 2\uparrow^{2}  (5) - 3 = 2\uparrow 2\uparrow2\uparrow2\uparrow2 - 3 = 2^{2^{2^{2^{2}}}} - 3 = 2^{65536} - 3

Och då

 \log(2^{65536}) = 65536(\log(2))

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 n + 1
1 2 3 4 5 6 n + 2 = 2 + (n + 3) - 3
2 3 5 7 9 11 2n + 3 = 2\cdot(n + 3) - 3
3 5 13 29 61 125 2^{(n + 3)} - 3
4 13

={2^{2^{2}}}-3
65533

={2^{2^{2^{2}}}}-3
265536 − 3

={2^{2^{2^{2^{2}}}}}-3
{2^{2^{65536}}} - 3

={2^{2^{2^{2^{2^{2}}}}}}-3
{2^{2^{2^{65536}}}} - 3

={2^{2^{2^{2^{2^{2^{2}}}}}}}-3
\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3\\n+3\end{matrix}
5 65533

=2\uparrow\uparrow\uparrow 3 - 3
2\uparrow\uparrow\uparrow 4 - 3 2\uparrow\uparrow\uparrow 5 - 3 2\uparrow\uparrow\uparrow 6 - 3 2\uparrow\uparrow\uparrow 7 - 3 2\uparrow\uparrow\uparrow (n+3) - 3
6 2\uparrow\uparrow\uparrow\uparrow 3 - 3 2\uparrow\uparrow\uparrow\uparrow 4 - 3 2\uparrow\uparrow\uparrow\uparrow 5 - 3 2\uparrow\uparrow\uparrow\uparrow 6 - 3 2\uparrow\uparrow\uparrow\uparrow 7 - 3 2\uparrow\uparrow\uparrow\uparrow (n+3) - 3

Se även[redigera | redigera wikitext]