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:
![{\displaystyle 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f288c21828b34617a480011e7e8494331c880c3)
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
![{\displaystyle A(m,n)=2\uparrow ^{m-2}(n+3)-3.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be11675406f79084afaa29ab9d0f467e7f749d63)
Med hjälp av denna beskrivning kan rekursionen av
göras något enklare.
![{\displaystyle A(4,2)=2\uparrow ^{4-2}(2+3)-3=2\uparrow ^{2}(5)-3=2\uparrow 2\uparrow 2\uparrow 2\uparrow 2-3=2^{2^{2^{2^{2}}}}-3=2^{65536}-3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b76e1ba64576afe1338debfe206ed3d5630843cd)
Och då
![{\displaystyle \log(2^{65536})=65536\cdot \log(2)\approx 19728{,}3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee97f6ebf4827c9a49380ca12b72f11f2f73c2a8)
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
=![{\displaystyle {2^{2^{2}}}-3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/329005f949bc9b6559a404e944e1480df9f7ec3f) | 65533
= | 265536 − 3
= |
= |
= | |
5 | 65533
= | | | | | |
6 | | | | | | |
Se även
Mycket stora tal |
---|
| I storleksordning | | | Uttrycksmetoder | Notationer | | | Operatorer | Hyperoperator ( Tetraering · Pentaering) · Ackermannfunktionen · Grzegorczyks hierarki · Snabbväxande hierarki |
| | Relaterade artiklar | | | Namn · Histora |
|