Definition:Ackermann Function/Mistake 1

From ProofWiki
Jump to navigation Jump to search

Source Work

1997: David Wells: Curious and Interesting Numbers (2nd ed.):

The Dictionary
$65,536$


Mistake

The Ackermann function is one of the fastest increasing functions used in mathematics. Its values from $\map f 0$ to $\map f 5$ are $1$, $3$, $4$, $8$, $65,536$.


Correction

First note that this should read:

Its values from $\map f 0$ to $\map f 4$ are $1$, $3$, $4$, $8$, $65,536$.


Next it should be noted that David Wells has at this stage not specified what is meant by the Ackermann function. When later in Curious and Interesting Numbers, 2nd ed. he does define it, he does so as a function of $2$ variables.


It is probable that he was referring to the function:

$\map f n = \map {H_n} {2, n}$

where $H_n$ is the $n$th hyperoperation, defined as:

$\map {H_n} {x, y} = \begin{cases} y + 1 & : n = 0 \\ x & : n = 1, y = 0 \\ 0 & : n = 2, y = 0 \\ 1 & : n > 2, y = 0 \\ \map {H_{n - 1} } {x, \map {H_n} {x, y - 1} } & : n > 0, y > 0 \end{cases}$


This leads to the results:

\(\text {(0)}: \quad\) \(\ds \map {H_0} {2, 0}\) \(=\) \(\ds 0 + 1\) Zeroth Hyperoperation is Successor Function
\(\ds \) \(=\) \(\ds 1\)


\(\text {(1)}: \quad\) \(\ds \map {H_1} {2, 1}\) \(=\) \(\ds 2 + 1\) First Hyperoperation is Addition Operation
\(\ds \) \(=\) \(\ds 3\)


\(\text {(2)}: \quad\) \(\ds \map {H_2} {2, 2}\) \(=\) \(\ds 2 \times 2\) Second Hyperoperation is Multiplication Operation
\(\ds \) \(=\) \(\ds 4\)


\(\text {(3)}: \quad\) \(\ds \map {H_3} {2, 3}\) \(=\) \(\ds 2 \uparrow 3\) Third Hyperoperation is Integer Power Operation
\(\ds \) \(=\) \(\ds 2 \times 2 \times 2\) Definition of Integer Power, using Knuth Notation
\(\ds \) \(=\) \(\ds 8\)


\(\text {(4)}: \quad\) \(\ds \map {H_4} {2, 4}\) \(=\) \(\ds 2 \uparrow \uparrow 4\) Fourth Hyperoperation is Tetration Operation
\(\ds \) \(=\) \(\ds 2 \uparrow \paren {2 \uparrow \paren {2 \uparrow 2} }\) Definition of Tetration, using Knuth Notation
\(\ds \) \(=\) \(\ds 2 \uparrow \paren {2 \uparrow 4}\) $2 \uparrow 2 = 2^2 = 4$
\(\ds \) \(=\) \(\ds 2 \uparrow 16\) $2 \uparrow 4 = 2^4 = 16$
\(\ds \) \(=\) \(\ds 65 \, 536\) $2 \uparrow 16 = 2^{16} = 65 \, 536$

This sequence is A001695 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).


Sources