# Definition:Ackermann Function/Mistake 2

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

- 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): $2^{65536}$ - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): $2^{65,536}$