# Definition:Ackermann Function/Mistake 2

## Source Work

The Dictionary
$2^{65536}$
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.