Ackermann
De Ackermannfunctie, vernoemd naar Wilhelm Ackermann, is een van de simpelste maar meest snel stijgende functies die serieus in de wiskunde gebruikt worden. De definitie is als volgt:
$$\begin{aligned} A(0, n) &= n + 1,\\ A(m + 1, 0) &= A(m, 1),\\ A(m + 1, n + 1) &= A(m, A(m + 1, n)). \end{aligned}$$
Dit is opnieuw een recursieve functie: de Ackermannfunctie roept zichzelf op om de uitkomst te bepalen. De meest eenvoudige manier om deze functie te implementeren, is dan ook via recursie.
De Ackermannfunctie groeit zodanig snel dat er geen uitdrukking mogelijk is van deze functie in termen van elementaire operaties zoals optelling en vermenigvuldiging. Je kan \(A(m,n)\) echter wel berekenen op een computer voor kleine waarden van \(m\) en \(n\). Bijvoorbeeld:
$$\begin{aligned} A(1, 2) &= A(0, A(1, 1))\\ &= A(0, A(0, A(1, 0)))\\ &= A(0, A(0, A(0, 1)))\\ &= A(0, A(0, 2))\\ &= A(0, 3)\\ &= 4. \end{aligned}$$
Dit gaat nog. Als we echter dit proberen:
$$\begin{aligned} A(4, 3) &= A(3, A(4, 2))\\ &= A(3, A(3, A(4, 1)))\\ &= A(3, A(3, A(3, A(4, 0))))\\ &= ...\\ &= A(3, A(3, A(3, 13)))\\ &= ...\\ &= A(3, A(3, 65533))\\ &= ...\\ &= 2^{2^{65536}} - 3. \end{aligned}$$
De Ackermannfunctie escaleert nogal snel.
Opgave
Schrijf een programma dat de Ackermannfunctie implementeert. De invoer bestaat telkens uit een bestand met twee regels: eentje voor \(m\) en eentje voor \(n\).
Voorbeeld
Invoer:
1
2
Uitvoer:
4