Definition:Ackermann-Péter Function
Contents
Definition
The Ackermann-Péter function $A: \Z_{\ge 0} \times \Z_{\ge 0} \to \Z_{> 0}$ is an integer-valued function defined on the set of ordered pairs of positive integers as:
- $A \left({x, y}\right) = \begin{cases} y + 1 & : x = 0 \\ A \left({x - 1, 1}\right) & : x > 0, y = 0 \\ A \left({x - 1, A \left({x, y - 1}\right)}\right) & : \text{otherwise} \end{cases}$
Also defined as
Work to be done to research and distinguish between the various different versions of this function.
Until this has been finished, please leave {{refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
Some sources define the Ackermann function as $A: \Z_{> 0} \times \Z_{> 0} \to \Z_{> 0}$ where:
- $A \left({x, y}\right) = \begin{cases} 2 y & : x = 1 \\ x & : x > 1, y = 1 \\ A \left({x - 1, A \left({x, y - 1}\right)}\right) & : \text{otherwise} \end{cases}$
Examples
- $\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}$
To discuss it in more detail, feel free to use the talk page.
When this has been done, {{Finish}} should be removed from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.
Examples
No, you're right, I really don't know what I'm doing, at all.
- $\begin{array}{c|c|c|c} A \left({m, n}\right) & m = 1 & m = 2 & m = 3 & m = 4 & \cdots & m = k \\ \hline n = 1 & 2 & 2 & 3 & 4 & & k \\ n = 2 & 4 & \map A {1, \map A {2, 1} } & \map A {2, \map A {3, 1} } & \map A {3, \map A {4, 1} } & & \map A {k - 1, \map A {k, 1} } \\ n = 3 & 6 & \map A {1, \map A {2, 2} } & A \map A {2, \map A {3, 2} } & \map A {3, \map A {4, 2} } & & \map A {k - 1, \map A {k, 2} } \\ n = 4 & 8 & \map A {1, \map A {2, 3} } & \map A {2, A \map A {3, 3} } & \map A {3, \map A {4, 3} } & & \map A {k - 1, \map A {k, 3} } \\ n = 5 & 10 & \map A {1, \map A {2, 4} } & \map A {2, \map A {3, 4} }\ & \map A {3, \map A {4, 4} } & & \map A {k - 1, \map A {k, 4} } \\ \vdots & & & & & & \\ n = j & 2 j & \map A {1, \map A {2, j - 1} } & \map A {2, \map A {3, j - 1} } & \map A {3, \map A {4, j - 1} } & & \map A {k - 1, \map A {k, j - 1} } \\ \end{array}$
which leads to:
- $\begin{array}{c|c|c|c} A \left({m, n}\right) & m = 1 & m = 2 & m = 3 & m = 4 & \cdots & m = k \\ \hline n = 1 & 2 & 2 & 3 & 4 & & k \\ n = 2 & 4 & 4 & 8 & \map A {3, 4} & & A \map A {k - 1, k} \\ n = 3 & 6 & 8 & 2^8 & \map A {3, \map A {4, 2} } & & \map A {k - 1, \map A {k, 2} } \\ n = 4 & 8 & 16 & 2^{2^8} & \map A {3, \map A {4, 3} } & & \map A {k - 1, \map A {k, 3} } \\ n = 5 & 10 & 32 & \map A {2, \map A {3, 4} } & \map A {3, \map A {4, 4} } & & \map A {k - 1, \map A {k, 4} } \\ \vdots & & & & \\ n = j & 2 j & 2^j & \map A {2, \map A {3, j - 1} } & \map A {3, \map A {4, j - 1} } & & \map A {k - 1, \map A {k, j - 1} } \\ \end{array}$
This needs to be checked, because "in the book" it has that $A \left({3, 4}\right)$ works out at $2^{65,536} = 2^{2^{16} }$ not $2^{2^8}$.
You can help ProofWiki by reviewing it, and either correcting it or adding some explanatory material as to why you believe it is actually correct after all.
To discuss this point in more detail, feel free to use the talk page.
If you are able to resolve this, then when you have done so you can remove this instance of {{Mistake}} from the code.
If you would welcome a second opinion as to whether your explanation is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
To discuss it in more detail, feel free to use the talk page.
When this has been done, {{Finish}} should be removed from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.
Also known as
The Ackermann-Péter function is also known as the Ackermann function.
However, there are a number of different similar functions which go by this name, so the full appellation can be argued as being more useful.
Source of Name
This entry was named for Wilhelm Friedrich Ackermann and Rózsa Péter.
Sources
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $2^{65536}$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $2^{65,536}$
- Weisstein, Eric W. "Ackermann Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/AckermannFunction.html
Determine exactly what categories it really belongs in
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information.
To discuss it in more detail, feel free to use the talk page.
If you are able to do this, then when you have done so you can remove this instance of {{Expand}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
