Definition:Ackermann-Péter Function/Examples

From ProofWiki
Jump to navigation Jump to search

Examples of Ackermann-Péter Function

The Ackermann-Péter function $A: \Z_{\ge 0} \times \Z_{\ge 0} \to \Z_{> 0}$ is defined as:

$A \left({m, n}\right) = \begin{cases} n + 1 & : m = 0 \\ A \left({m - 1, 1}\right) & : m > 0, n = 0 \\ A \left({m - 1, A \left({m, n - 1}\right)}\right) & : \text{otherwise} \end{cases}$


$\begin{array}{c|c|c|c} A \left({m, n}\right) & m = 0 & m = 1 & m = 2 & m = 3 \\ \hline n = 0 & 1 & A \left({0, 1}\right) & A \left({1, 1}\right) & A \left({2, 1}\right) \\ n = 1 & 2 & A \left({0, A \left({1, 0}\right)}\right) & A \left({1, A \left({2, 0}\right)}\right) & A \left({2, A \left({3, 0}\right)}\right) \\ n = 2 & 3 & A \left({0, A \left({1, 1}\right)}\right) & A \left({1, A \left({2, 1}\right)}\right) & A \left({2, A \left({3, 1}\right)}\right) \\ n = 3 & 4 & A \left({0, A \left({1, 2}\right)}\right) & A \left({1, A \left({2, 2}\right)}\right) & A \left({2, A \left({3, 2}\right)}\right) \\ n = 4 & 5 & A \left({0, A \left({1, 3}\right)}\right) & A \left({1, A \left({2, 3}\right)}\right) & A \left({2, A \left({3, 3}\right)}\right) \\ \end{array}$

which leads to:

$\begin{array}{c|c|c|c} A \left({m, n}\right) & m = 0 & m = 1 & m = 2 & m = 3 \\ \hline n = 0 & 1 & 2 & 3 & 5 \\ n = 1 & 2 & 3 & 5 & 13 \\ n = 2 & 3 & 4 & 7 & A \left({2, 13}\right) \\ n = 3 & 4 & 5 & 9 & A \left({2, A \left({3, 2}\right)}\right) \\ n = 4 & 5 & 6 & 11 & A \left({2, A \left({3, 3}\right)}\right) \\ \end{array}$