Definition:Ackermann Function/Mistake 2

From ProofWiki
Jump to navigation Jump to search

Source Work

1986: David Wells: Curious and Interesting Numbers:

The Dictionary
$2^{65536}$


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

The Dictionary
$2^{65,536}$


Mistake

Ackermann's function is defined by $\map f {a, b} = \map f {a - 1, \map f {a, b - 1} }$ where $\map f {1, b} = 2 b$ and $\map f {a, 1} = a$ for $a$ greater than $1$.
$\map f {3, 4} = 2^{65,536}$, which has more than $19,000$ digits.


In fact, what we find is as follows.

Let us define $f$ as above:

$\map f {a, b} = \begin{cases} 2 b & : a = 1 \\ a & : a > 1, b = 1 \\ \map f {a - 1, \map f {a, b - 1} } & : \text{otherwise} \end{cases}$


Then we have:

\(\displaystyle \map f {2, 3}\) \(=\) \(\displaystyle \map f {1, \map f {2, 2} }\)
\(\displaystyle \) \(=\) \(\displaystyle 2 \map f {2, 2}\) $\map f {a, b} = 2 b$ when $a = 1$
\(\displaystyle \) \(=\) \(\displaystyle 2 \map f {1, \map f {2, 1} }\)
\(\displaystyle \) \(=\) \(\displaystyle 2 \times 2 \map f {2, 1}\) $\map f {a, b} = 2 b$ when $a = 1$
\(\displaystyle \) \(=\) \(\displaystyle 2 \times 2 \times 2\) $\map f {a, b} = a$ when $b = 1$
\(\displaystyle \) \(=\) \(\displaystyle 8\)


By induction:

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



\(\displaystyle \map f {3, 4}\) \(=\) \(\displaystyle \map f {2, \map f {3, 3} }\)
\(\displaystyle \map f {3, 3}\) \(=\) \(\displaystyle \map f {2, \map f {3, 2} }\)
\(\displaystyle \map f {3, 2}\) \(=\) \(\displaystyle \map f {2, \map f {3, 1} }\)
\(\displaystyle \) \(=\) \(\displaystyle \map f {2, 3}\) $\map f {a, b} = a$ when $b = 1$
\(\displaystyle \) \(=\) \(\displaystyle 8\) from above
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f {3, 3}\) \(=\) \(\displaystyle \map f {2, 8}\) from above
\(\displaystyle \) \(=\) \(\displaystyle 2^8\) from above
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f {3, 4}\) \(=\) \(\displaystyle \map f {2, 2^8}\) from above
\(\displaystyle \) \(=\) \(\displaystyle 2^{\map f {2^8} }\) from above
\(\displaystyle \) \(=\) \(\displaystyle 2^{256}\)

and not $2^{65 \, 536}$ after all.


Sources