Knuth up arrow notation

$\displaystyle{\begin{matrix}a\times b&=&\underbrace {a+a+\dots +a} \\&&b{\mbox{ copies of }}\end{matrix}}$

$\displaystyle{\begin{matrix}a\uparrow b=a^{b}=& \underbrace {a\times a\times \dots \times a} \\&b{\mbox{ copies of }}a\end{matrix}}$

$\displaystyle{\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &= &\underbrace {a\uparrow (a\uparrow (\dots \uparrow a))} \\ &&b{\mbox{ copies of }}a&&b{\mbox{ copies of }}a\end{matrix}}$

What's good once is even better twice

Let's keep going

$\displaystyle{\begin{matrix}a\uparrow \uparrow \uparrow b&= &\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} \\&&&{\mbox{b-1 towers of N high}}\end{matrix}}$

$a\uparrow ^{n}b$ Things are getting out of hand

Some Numbers

$3\uparrow \uparrow 2=3^{3}=27$

${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987}$

$3\uparrow\uparrow 4=3^{3^{3^3}}=3^{3^{27}}=3^{7625597484987}\approx 1.2580143\times 10^{3638334640024}$

$3\uparrow\uparrow 5=3^{3^{3^{3^3}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}$

From before: ${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987}$

Now: ${\displaystyle 3\uparrow \uparrow \uparrow 3 = 3\uparrow \uparrow (3 \uparrow \uparrow 3) = 3\uparrow \uparrow 7,625,597,484,987}$

A tower of 3's 7,625,597,484,987 high

That's a big number, it has about 3.6 trillion digits.

${\displaystyle 3\uparrow \uparrow \uparrow \uparrow 3 = 3\uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3)}$

A number with a 3.6 trillion digit exponent.

A program is just a set of symbols

	      100 print 1
	      200 goto 100
	    

A program is just a set of symbols

	      100 let n = 2
	      200 n = n + 2
	      300 print 1
	      400 if n /= sum of two primes goto 200
	      500 print "Goldbach conjecture is false"
	    

A program is just a set of symbols

Consider all the programs that can be written with N symbols. For each N, choose the program that writes out the largest number of ones and halts. This describes a function from N->N.
This is the Busy Beaver Function.
It grows faster than any function we've seen so far.