Definition:Ackermann-Péter Function

From ProofWiki
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