Definition:Ackermann-Péter Function
Jump to navigation
Jump to search
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
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}$
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}$
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