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:

    “The principle of majority rule is the mildest form in which the force of numbers can be exercised. It is a pacific substitute for civil war in which the opposing armies are counted and the victory is awarded to the larger before any blood is shed. Except in the sacred tests of democracy and in the incantations of the orators, we hardly take the trouble to pretend that the rule of the majority is not at bottom a rule of force.”
    —Walter Lippmann (1889–1974)