How exactly does Knuth's Up-Arrow notation work?

Solution 1:

Close! The idea behind the up-arrow notation is the so called Hyperoperation Sequence, which goes like:

• Successor: add $1$. $S(a)= a+1$
• Addition: repeated successor. $b+a = \underset{b \text{ copies}}{\underbrace{ S ( S( \dots S(a)))}}$
• Multiplication: repeated addition. $b*a = \underset{b \text{ copies}}{\underbrace{ a + (a + (\cdots + a))}}$
• Exponentiation: repeated multiplication. $a^b = \underset{b \text{ copies}}{\underbrace{ a * ( a * ( \cdots *a))}}$. This is denoted as $a \uparrow b$, sort of looks like a^b on a calculator for computing $a^b$.
• Tetration: repeated exponentiation. $a\uparrow \uparrow b ={\ ^{b}a} =\underset{b \text{ copies}}{\underbrace{a^{a^{\dots^{a}}}}} = \underset{b \text{ copies}}{\underbrace{a\uparrow (a \uparrow (\cdots \uparrow a))}}. $ Note that the parentheses are vitally important! $ 2^{2^3} = 2^{(2^3)} = 2^8 = 256 \neq (2^2)^3 = 64$
• Pentation: repeated tetration.

So on and so forth until you get a stack overflow. The best way to think of this is as writing a recursive program for a computer. In principle, you could program a computer to compute $2^3$ the following way: $$2^3 = 2*(2*2) = 2+2 + 2+ 2 = 2+1+1+1+1+1+1.$$

As for your example: $$\ ^3 2= 2 \uparrow \uparrow 3= \underset{3 \text{ copies}}{\underbrace{2 \uparrow (2 \uparrow 2)}} = 2 \uparrow \underset{2 \text{ copies}}{\underbrace{(2*2)}} = 2 \uparrow 4 = \underset{4 \text{ copies}}{\underbrace{2*2*2*2}} = 16.$$ Notice that we could have been even more recursive in our expansion.

Moving on to pentation (repeated tetration (repeated exponentiation(...))): \begin{align*} 2 \uparrow \uparrow \uparrow 3 &= \underset{3 \text{ copies}}{\underbrace{ 2 \uparrow \uparrow ( 2 \uparrow \uparrow 2) }} \\ &= 2 \uparrow \uparrow ( \underset{2 \text{ copies}}{\underbrace{2^2}}) \\ &= 2 \uparrow \uparrow 4 \\ &= \underset{4 \text{ copies}}{\underbrace{2^{2^{2^2}} }} \\ &= 2^{2^4} \\ &= 2^{16} \\ &= 65536. \end{align*} Again, notice that we could be even more explicit and break the recursion all the way down to the successor function: $$2 \uparrow \uparrow \uparrow 3 = 2 + \underset{\text{many many copies}}{\underbrace{1 +1 \cdots + 1}}$$

Edited to add: more examples!

• $n^n = \ ^{2} n = n \uparrow \uparrow 2$ and $n^{n^n} = \ ^{3} n = n \uparrow \uparrow 3$.

• $2 \uparrow \uparrow \uparrow 2 = \underset{2\text{ copies}}{\underbrace{ 2 \uparrow \uparrow 2}} = \underset{2\text{ copies}}{\underbrace{ 2 \uparrow 2 }} = \underset{2\text{ copies}}{\underbrace{ 2*2}} = \underset{2\text{ copies}}{\underbrace{ 2+2}} = 4$. Up-arrows to the second is kind of weird. Consider that $a^2 = a*a$ for any $a$. Similarly, $a \uparrow \uparrow 2 = \underset{2\text{ copies}}{\underbrace{a \uparrow a}}$. What can we say, $2$ is weird as an exponent (tetraponent?).

• $3 \uparrow \uparrow \uparrow 3 = \underset{3\text{ copies}}{\underbrace{ 3 \uparrow \uparrow (3 \uparrow \uparrow 3)}} = 3 \uparrow \uparrow (\underset{3\text{ copies}}{\underbrace{3^{3^3} }}) = 3 \uparrow \uparrow 7625597484987$ which is $\underset{7625597484987\text{ copies}}{\underbrace{3^{3^{...^3}}}}$

• A googol is pretty big---$10^{100} = 10^{10^2}$. It's so big that writing it as $\underset{100\text{ copies}}{\underbrace{10*10 * \cdots *10}}$ doesn't even really make sense. As big as a googol is, it is absolutely positively miniscule compared to $\ ^{10} 10 = 10 \uparrow \uparrow 10= 10^{10^{10^{10^{10^{10^{10^{10^{10^{10}}}}}}}}}$. This is a number that is so big that it doesn't even make sense to write in terms of exponentiation. As gigantic as $10 \uparrow \uparrow 10$ is, it is a fraction of a fraction of a fraction ... of a percentage of $10 \uparrow \uparrow \uparrow 10$, which is so big that expressing it as repeated tetration is impractical and as repeated exponentiation is almost intractable.
• Graham's Number
• $1 \uparrow \uparrow \uparrow \dots \uparrow a= 1$. Lame, but consistent: $1^a = \underset{a\text{ copies}}{\underbrace{1*1* \cdots * 1}}= 1$ for any $a>0$.
• $0 \uparrow \uparrow \dots \uparrow a = 0$. Again, $0^a = 0$ for any $a>0$.
• $n!$ grows pretty fast: $1, 2, 6, 24, 120, 720, 5040, 40320, \dots$. But $n! \ll n^n = \ ^{2} n = n \uparrow \uparrow 2.$

Solution 2:

You're correct that $2↑↑3$ is $16$. It looks like you've miscalculated $2↑↑↑3$ though; it is larger than $256$.

$2↑↑↑3$ can be written as $2↑↑(2↑↑2)$. We have that $2↑↑2 = 2^2 = 4$, so we need to calculate $2↑↑4$.

This is a tower of four twos: $2^{2^{2^2}} = 2^{2^4} = 2^{16} = 65536$.

Just to get more of a feel for the arrow-notation and how rapidly the numbers can grow, let's extend the example one stage further in a couple of different ways.

First, what about $2↑↑↑4$? This is the same as $2↑↑(2↑↑(2↑↑2))$ which, using the working above, we know is $2↑↑65536$. In words, this is a tower of $65336$ twos!

Second, what if we had four arrows? It turns out that $2↑↑↑↑3$ is $2↑↑↑(2↑↑↑2)$ which is $2↑↑↑4$. Unravelling the arrows again, this is $2↑↑(2↑↑(2↑↑2))$. We're back to the first example: a tower of $65536$ twos.