Ackermann Function - Expansion

Expansion

To see how the Ackermann function grows so quickly, it helps to expand out some simple expressions using the rules in the original definition. For example, we can fully evaluate in the following way:

\begin{align}
A(1,2) & = A(0, A(1, 1)) \\
& = A(0, A(0, A(1, 0))) \\
& = A(0, A(0, A(0, 1))) \\
& = A(0, A(0, 2)) \\
& = A(0, 3) \\
& = 4.
\end{align}

To demonstrate how 's computation results in many steps and in a large number:

\begin{align}
A(4, 3) & = A(3, A(4, 2)) \\
& = A(3, A(3, A(4, 1))) \\
& = A(3, A(3, A(3, A(4, 0)))) \\
& = A(3, A(3, A(3, A(3, 1)))) \\
& = A(3, A(3, A(3, A(2, A(3, 0))))) \\
& = A(3, A(3, A(3, A(2, A(2, 1))))) \\
& = A(3, A(3, A(3, A(2, A(1, A(2, 0)))))) \\
& = A(3, A(3, A(3, A(2, A(1, A(1, 1)))))) \\
& = A(3, A(3, A(3, A(2, A(1, A(0, A(1, 0))))))) \\
& = A(3, A(3, A(3, A(2, A(1, A(0, A(0, 1))))))) \\
& = A(3, A(3, A(3, A(2, A(1, A(0, 2)))))) \\
& = A(3, A(3, A(3, A(2, A(1, 3))))) \\
& = A(3, A(3, A(3, A(2, A(0, A(1, 2)))))) \\
& = A(3, A(3, A(3, A(2, A(0, A(0, A(1, 1))))))) \\
& = A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(1, 0)))))))) \\
& = A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(0, 1)))))))) \\
& = A(3, A(3, A(3, A(2, A(0, A(0, A(0, 2)))))) \\
& = A(3, A(3, A(3, A(2, A(0, A(0, 3))))) \\
& = A(3, A(3, A(3, A(2, A(0, 4))))) \\
& = A(3, A(3, A(3, A(2, 5)))) \\
& = ... \\
& = A(3, A(3, A(3, 13))) \\
& = ... \\
& = A(3, A(3, 65533)) \\
& = ... \\
& = A(3, 2^{65536} - 3) \\
& = ... \\
& = 2^{2^{ \overset{65536}{} }} - 3. \\
\end{align}

Written as a power of 10, this is roughly equivalent to 106.031×1019,727.

Read more about this topic:  Ackermann Function

Famous quotes containing the word expansion:

    The fundamental steps of expansion that will open a person, over time, to the full flowering of his or her individuality are the same for both genders. But men and women are rarely in the same place struggling with the same questions at the same age.
    Gail Sheehy (20th century)

    We are caught up Mr. Perry on a great wave whether we will or no, a great wave of expansion and progress. All these mechanical inventions—telephones, electricity, steel bridges, horseless vehicles—they are all leading somewhere. It’s up to us to be on the inside in the forefront of progress.
    John Dos Passos (1896–1970)

    Artistic genius is an expansion of monkey imitativeness.
    W. Winwood Reade (1838–1875)