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:

$\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


This article is complete as far as it goes, but it could do with expansion.
In particular: Determine exactly what categories it really belongs in
You 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.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Ackermann-Péter_Function&oldid=547946"