From: Ryan Breedon
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