Ackermann Function - Ackermann Numbers

In The Book of Numbers, John Horton Conway and Richard K. Guy define the sequence of Ackermann numbers to be 1↑1, 2↑↑2, 3↑↑↑3, etc.; that is, the n-th Ackermann number is defined to be n↑nn (n = 1, 2, 3, ...), where m↑kn is Knuth's up-arrow version of the Ackermann function.

The first few Ackermann numbers are:

  • 1↑1 = 11 = 1,
  • 2↑↑2 = 2↑2 = 22 = 4,
  • 3↑↑↑3 = 3↑↑3↑↑3 = 3↑↑(3↑3↑3) =

The fourth Ackermann number, 4↑↑↑↑4, can be written in terms of tetration towers as follows:

4↑↑↑↑4 = 4↑↑↑4↑↑↑4↑↑↑4 = 4↑↑↑4↑↑↑(4↑↑4↑↑4↑↑4)

Explanation: in the middle layer, there is a tower of tetration whose full height is and the final result is the top layer of tetrated 4's whose full height equals the calculation of the middle layer. Note that by way of size comparison, the simple expression 44 already exceeds a googolplex, so the fourth Ackermann number is quite large.

Alternatively, this can be written in terms of exponentiation towers as

\left. \begin{matrix} 4^{4^{\cdot^{\cdot^{\cdot^{\cdot^{4}}}}}}\end{matrix} \right \} \left. \begin{matrix}4^{4^{\cdot^{\cdot^{\cdot^{4}}}}}\end{matrix} \right \} \dots \left. \begin{matrix}4^{4^{4^4}}\end{matrix} \right \} 4,
where the number of towers on the previous line (including the rightmost "4") is
\left. \begin{matrix}4^{4^{\cdot^{\cdot^{\cdot^{\cdot^{4}}}}}}\end{matrix} \right \} \left. \begin{matrix}4^{4^{\cdot^{\cdot^{\cdot^{4}}}}}\end{matrix} \right \} \dots \left. \begin{matrix}4^{4^{4^4}}\end{matrix} \right \} 4,
where the number of towers on the previous line (including the rightmost "4") is
\left. \begin{matrix}4^{4^{\cdot^{\cdot^{\cdot^{4}}}}}\end{matrix} \right \} \left. \begin{matrix}4^{4^{\cdot^{\cdot^{\cdot^{4}}}}}\end{matrix} \right \} \left. \begin{matrix}4^{4^{4^4}}\end{matrix} \right \} 4,

where the number of "4"s in each tower, on each of the lines above, is specified by the value of the next tower to its right (as indicated by a brace).

Read more about this topic:  Ackermann Function

Famous quotes containing the word numbers:

    “Our religion vulgarly stands on numbers of believers. Whenever the appeal is made—no matter how indirectly—to numbers, proclamation is then and there made, that religion is not. He that finds God a sweet, enveloping presence, who shall dare to come in?”
    —Ralph Waldo Emerson (1803–1882)