Jump to content

User:Sligocki/Green's numbers

From Wikipedia, the free encyclopedia
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

[edit]

Let us define the numbers for n odd.

Then, Green's numbers are defined as:

  • for odd n
  • for even n

Examples

[edit]
  • and
  • and


  • > 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

Bounds

[edit]

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
Proof by induction.
Base Case
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
(left as an exercise to the reader)
Inductive Step

Assume that (for or )

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

Claim.
for
Proof.


QED

References

[edit]
  1. ^ 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.