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

- $\map A {x, y} = \begin{cases} y + 1 & : x = 0 \\ \map A {x - 1, 1} & : x > 0, y = 0 \\ \map A {x - 1, \map A {x, y - 1} } & : \text{otherwise} \end{cases}$

## Also defined as

Further research is required in order to fill out the details.In particular: Work to be done to research and distinguish between the various different versions of this function.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by finding out more.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Research}}` from the code. |

Some sources define the **Ackermann function** as $A: \Z_{> 0} \times \Z_{> 0} \to \Z_{> 0}$ where:

- $\map A {x, y} = \begin{cases} 2 y & : x = 1 \\ x & : x > 1, y = 1 \\ \map A {x - 1, \map A {x, y - 1} } & : \text{otherwise} \end{cases}$

## Examples

- $\begin {array} {c|c|c|c} \map A {m, n} & m = 0 & m = 1 & m = 2 & m = 3 \\ \hline n = 0 & 1 & \map A {0, 1} & \map A {1, 1} & \map A {2, 1} \\ n = 1 & 2 & \map A {0, \map A {1, 0} } & \map A {1, \map A {2, 0} } & \map A {2, \map A {3, 0} } \\ n = 2 & 3 & \map A {0, \map A {1, 1} } & \map A {1, \map A {2, 1} } & \map A {2, \map A {3, 1} } \\ n = 3 & 4 & \map A {0, \map A {1, 2} } & \map A {1, \map A {2, 2} } & \map A {2, \map A {3, 2} } \\ n = 4 & 5 & \map A {0, \map A {1, 3} } & \map A {1, \map A {2, 3} } & \map A {2, \map A {3, 3} } \\ \end{array}$

which leads to:

- $\begin{array}{c|c|c|c} \map A {m, n} & 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 & \map A {2, 13} \\ n = 3 & 4 & 5 & 9 & \map A {2, \map A {3, 2} } \\ n = 4 & 5 & 6 & 11 & \map A {2, \map A {3, 3} } \\ \end{array}$

This needs considerable tedious hard slog to complete it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Finish}}` 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} \map A {m, n} & 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} } & \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, \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} \map A {m, n} & 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} & & \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}$

There is believed to be a mistake here, possibly a typo.In particular: This needs to be checked, because "in the book" it has that $\map A {3, 4}$ 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 page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Mistake}}` from the code.If you would welcome a second opinion as to whether your work is correct, add a call to `{{Proofread}}` the page. |

This needs considerable tedious hard slog to complete it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Finish}}` 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. https://mathworld.wolfram.com/AckermannFunction.html

This article is complete as far as it goes, but it could do with expansion.In particular: Determine exactly what categories it really belongs inYou can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Expand}}` from the code.`{{Proofread}}` the page. |