- 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.[1]
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
for n odd.
![{\displaystyle B_{n}(0)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ebacc7824a62d8076291f15e0b71f0d3aa633e5c)
![{\displaystyle B_{1}(m)=m+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa68670e4f766345065258ebe066ec248aea19ac)
![{\displaystyle B_{n}(m)=B_{n-2}[B_{n}(m-1)+1]+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff1acf2d3af558008d8ba06b96344689ce9c7d2e)
Then, Green's numbers
are defined as:
for odd n
for even n
Examples
![{\displaystyle B_{1}(m)=m+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa68670e4f766345065258ebe066ec248aea19ac)
![{\displaystyle B_{3}(m)=3m+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a36780c94393f789a2e1665eb01150a05db1894)
![{\displaystyle B_{5}(m)={\frac {7}{2}}\cdot 3^{m}-{\frac {5}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8aa6e87a91564643170749222706aa7be8dcc15a)
and ![{\displaystyle B_{7}(1)=B_{5}(2)+1=29}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4e10c25acc54aaea280d0f9a5c1f0302ba139c3)
and ![{\displaystyle B_{9}(1)=B_{7}(2)+1=B_{5}(30)+2=720618962331271}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a80287bf89857edd980bd0edffb510262bb45fd)
![{\displaystyle BB_{3}=3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f66bcc1bc1dcbdb638fa1479ae55730fbb193263)
![{\displaystyle BB_{4}=7}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad82caa71da7c647b9a8777a0fb36bdd05bc80a9)
![{\displaystyle BB_{5}=13}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6376443888c813bbb0d82a63ea2dfe1cb950767)
![{\displaystyle BB_{6}=35}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d9f4255893998131e4bfd36f8f5c9ed1ac2ebc8)
![{\displaystyle BB_{7}=B_{5}(8)=22961}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41ec28968827db70759fe7902afc8bd4af7605c1)
![{\displaystyle BB_{8}=B_{5}(93)+1=3(7\cdot 3^{92}-1)/2=824792557184288824246737061810550733633916929}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b06db17f25896165fb8a0651e3195b97726cba2)
> 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).
= the third Ackermann number
![{\displaystyle BB_{11}=B_{9}(B_{9}(1))=B_{9}(720618962331271)>3\uparrow \uparrow \uparrow 720618962331271}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb8ecb91915be2e2c2b7673215beae2888b7660b)
Bounds
We will show that
grows like
and thus that
grows like
(See Knuth's up-arrow notation and User:sligocki/up-arrow properties).
- Claim.
for any
and ![{\displaystyle m\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0d2d765e4cfd7adfbca9ae0e37e75a2811c0333)
- Proof by induction.
- Base Case
![{\displaystyle B_{2k+3}(0)=1\geq 1=3\uparrow ^{k}0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3eeb6f9e404d0b9901ff9a80065d45e9d6144960)
![{\displaystyle B_{1}(m)=m+1\geq m+1=3\uparrow ^{-2}m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a0c8421d2b1397be0e38312213877d00fa6438b)
- Inductive Step
Assume that
(for all
or
)
- QED
- Claim.
for any
and
(In fact the bound can be tightened to m+1 for k ≥ 2)
- Proof by induction.
- Base Case
![{\displaystyle B_{2k+3}(0)=1<{\frac {1}{2}}(3\uparrow ^{k}2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9edbf9e4a325de8946004cb820b99e4cda3517a2)
![{\displaystyle B_{5}(m)={\frac {9}{2}}3^{m}<{\frac {1}{2}}(3\uparrow (m+2))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63821bf5bcf44efcb9132f93bf961d03e40f09f8)
(left as an exercise to the reader)
- Inductive Step
Assume that
(for
or
)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28f8ac74e12fda64188f0537c6c0f2ab448b4a49)
≤? statements seem obvious, but grungy to prove (left as an exercise to the reader :)
- Claim.
for ![{\displaystyle k\geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d30d7dcf305b7bce39d36df72fe3985b47aa9961)
- Proof.
-
![{\displaystyle BB_{2k+5}=B_{2k+3}(B_{2k+3}(1))>3\uparrow ^{k}(3\uparrow ^{k}1)=3\uparrow ^{k}3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae3e87a73278dcaee26c669eafcf19f0c5c8ad1f)
![{\displaystyle BB_{2k+4}>B_{2k+1}(B_{2k+1}(3))>3\uparrow ^{k-1}(3\uparrow ^{k-1}3)=3\uparrow ^{k}3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ee33ea71c04d55a7d7916f81247473f215e7ffe)
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed5ef8bd2156e270101757aa23adda87c65d6112)
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7dcc1f25057f8f52fa3a55b4c16acdf3b56b254)
- QED
References
- ^ Milton W. Green. A Lower Bound on Rado's Sigma Function for Binary Turing Machines. In Preceedings of the IEEE Fifth Annual Symposium on Switching Circuits Theory and Logical Design, pages 91–94, 1964.