User:Sligocki/Green's numbers

This article is now available on my blog: https://www.sligocki.com/2009/10/08/green-numbers.html

Milton Green discovered a class of Turing machines which produce extremely large results in the busy beaver game.

The machines defined recursively and the number of 1s they leave on the tape is likewise defined recursively. We examine those numbers here:

Definition

Let us define the numbers $B_{n}$ for n odd.

• $B_{n}(0)=1$
• $B_{1}(m)=m+1$
• $B_{n}(m)=B_{n-2}[B_{n}(m-1)+1]+1$

Then, Green's numbers $BB_{n}$ are defined as:

• $BB_{n}=B_{n-2}[B_{n-2}(1)]$ for odd n
• $BB_{n}=B_{n-3}[B_{n-3}(3)+1]+1$ for even n

Examples

• $B_{1}(m)=m+1$
• $B_{3}(m)=3m+1$
• $B_{5}(m)={\frac {7}{2}}\cdot 3^{m}-{\frac {5}{2}}$
• $B_{7}(m)>3\uparrow \uparrow m$ and $B_{7}(1)=B_{5}(2)+1=29$
• $B_{9}(m)>3\uparrow \uparrow \uparrow m$ and $B_{9}(1)=B_{7}(2)+1=B_{5}(30)+2=720618962331271$

• $BB_{3}=3$
• $BB_{4}=7$
• $BB_{5}=13$
• $BB_{6}=35$
• $BB_{7}=B_{5}(8)=22961$
• $BB_{8}=B_{5}(93)+1=3(7\cdot 3^{92}-1)/2=824792557184288824246737061810550733633916929$
• $BB_{9}=B_{7}(B_{7}(1))=B_{7}(29)>3\uparrow \uparrow 29>10\uparrow \uparrow 28$ > a googolplex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex-plex (25 plexes).
• $BB_{10}=B_{7}(B_{7}(3)+1)+1>3\uparrow \uparrow 3\uparrow \uparrow 3=3\uparrow \uparrow \uparrow 3$ = the third Ackermann number
• $BB_{11}=B_{9}(B_{9}(1))=B_{9}(720618962331271)>3\uparrow \uparrow \uparrow 720618962331271$

Bounds

We will show that $B_{n}(m)$ grows like $3\uparrow ^{n/2}m$ and thus that $BB_{n}$ grows like $3\uparrow ^{n/2}3$ (See Knuth's up-arrow notation and User:sligocki/up-arrow properties).

Claim.

$B_{2k+3}(m)\geq 3\uparrow ^{k}m$ for any $k\geq -2$ and $m\geq 0$

Proof by induction.

Base Case

$B_{2k+3}(0)=1\geq 1=3\uparrow ^{k}0$

$B_{1}(m)=m+1\geq m+1=3\uparrow ^{-2}m$

Inductive Step

Assume that $B_{2k^{\prime }+3}(m^{\prime })\geq 3\uparrow ^{k^{\prime }}m^{\prime }$ (for all $k^{\prime }=k,m^{\prime }<m$ or $k^{\prime }<k,m^{\prime }<3\uparrow ^{k}(m-1)$)

$B_{2k+3}(m)=B_{2k+1}[B_{2k+3}(m-1)+1]+1>B_{2k+1}[3\uparrow ^{k}(m-1)]>3\uparrow ^{k-1}[3\uparrow ^{k}(m-1)]=3\uparrow ^{k}m\,$

QED

Claim.

$B_{2k+3}(m)<{\frac {1}{2}}(3\uparrow ^{k}(m+2))<(3\uparrow ^{k}(m+2))$ for any $k\geq 1$ and $m\geq 0$ (In fact the bound can be tightened to m+1 for k ≥ 2)

Proof by induction.

Base Case

$B_{2k+3}(0)=1<{\frac {1}{2}}(3\uparrow ^{k}2)$

$B_{5}(m)={\frac {9}{2}}3^{m}<{\frac {1}{2}}(3\uparrow (m+2))$

$B_{7}(m)<{\frac {1}{2}}(3\uparrow ^{2}(m+1))$ (left as an exercise to the reader)

Inductive Step

Assume that $B_{2k^{\prime }+3}(m^{\prime })<{\frac {1}{2}}(3\uparrow ^{k^{\prime }}(m^{\prime }+2))$ (for $k^{\prime }=k,m^{\prime }<m$ or $k^{\prime }<k,m^{\prime }<3\uparrow ^{k}m+1$)

${\begin{array}{rll}B_{2k+3}(m)=B_{2k+1}[B_{2k+3}(m-1)+1]+1&<&B_{2k+1}[{\frac {1}{2}}(3\uparrow ^{k}(m+1))+1]+1\\&<&{\frac {1}{2}}(3\uparrow ^{k-1}[{\frac {1}{2}}(3\uparrow ^{k}(m+1))+3])+1\\&\leq ?&{\frac {1}{2}}(3\uparrow ^{k-1}[{\frac {1}{2}}(3\uparrow ^{k}(m+1))+4])\\&\leq ?&{\frac {1}{2}}(3\uparrow ^{k-1}(3\uparrow ^{k}(m+1)))\\&=&{\frac {1}{2}}(3\uparrow ^{k}(m+2))\end{array}}$

≤? statements seem obvious, but grungy to prove (left as an exercise to the reader :)

Claim.

$3\uparrow ^{k}3<BB_{2k+4},BB_{2k+5}<3\uparrow ^{k+1}3$ for $k\geq 1$

Proof.

$BB_{2k+5}=B_{2k+3}(B_{2k+3}(1))>3\uparrow ^{k}(3\uparrow ^{k}1)=3\uparrow ^{k}3$

$BB_{2k+4}>B_{2k+1}(B_{2k+1}(3))>3\uparrow ^{k-1}(3\uparrow ^{k-1}3)=3\uparrow ^{k}3$

$BB_{2k+5}=B_{2k+3}(B_{2k+3}(1))<{\frac {1}{2}}(3\uparrow ^{k}({\frac {1}{2}}(3\uparrow ^{k}(1+2))+2))<3\uparrow ^{k}(3\uparrow ^{k}3)=3\uparrow ^{k+1}3$

$BB_{2k+4}=B_{2k+1}[B_{2k+1}(3)+1]+1<{\frac {1}{2}}(3\uparrow ^{k-1}({\frac {1}{2}}(3\uparrow ^{k-1}(3+2))+3))+1<3\uparrow ^{k-1}(3\uparrow ^{k-1}5)<3\uparrow ^{k}4<3\uparrow ^{k+1}3$

QED