From: Ryan Breedon <eco@sympatico.ca>
Subject: Re: Largest number??????
Date: Thu, 08 Apr 1999 17:18:00 GMT
Newsgroups: sci.math,sci.logic
Keywords: Busy Beaver references

David Bernier wrote:

> I suspect a Turing machine with at most a few thousand states
> could produce a tape with J 1's on it after it has halted (starting
> with a blank tape).  The busy beaver function ( capital Sigma ) is
> a non-computable function studied by logicians.  I know there are
> busy beaver contests, and I'm curious to know what the latest
> record holders are.  Anyone have any recent references on the
> Busy Beaver function?

The information is available online. Have a look at the following sites:

http://www.drb.insel.de/~heiner/BB/  (Heiner Marxen's site)
http://www.dei.uc.pt/~machado/BB.html (Genetic Beaver Project site)

Note that there is a difference between "4-tuple" and "5-tuple" machines which
significantly affects the sigma value for any given state--a 5-tuple machine,
similar to the original presented in Turing's "On Computable Numbers..." can both
write and move at any given time, whereas a 4-tuple machine, like the ones
discussed in Boolos & Jeffrey's _Computability and Logic_, can either move or
write.  As far as I know, these are the only two sorts of machines being tested
presently (although I would be interested to learn if I am incorrect on this
point), and the URLs above cover both types.

Ryan Breedon