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:

    “What culture lacks is the taste for anonymous, innumerable germination. Culture is smitten with counting and measuring; it feels out of place and uncomfortable with the innumerable; its efforts tend, on the contrary, to limit the numbers in all domains; it tries to count on its fingers.”
    —Jean Dubuffet (1901–1985)