# Definition:Ackermann-Péter Function

Jump to navigation
Jump to search

## 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

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