Jump to content

Busy beaver

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 195.186.152.254 (talk) at 07:44, 5 August 2002. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

A Busy Beaver is a Turing machine that, when given an empty string (a string with only 0's), does a lot of work, then halts. There are two main 'categories', namely the largest numbers of 1's printed when halted, and the largest number of steps taken. Note that machines that do not halt (when provided an empty string) are not counted.

Even with only a few states, a Busy Beaver can do very much. At the moment the records for 6-state Busy Beavers are over 10^865 (that is 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000) ones produced, using over 10^1730 steps.

External links:

  • The page of Heiner Marxen who with Jürgen Bontrock found the abovementioned record for a 6-state machine.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Busy_beaver&oldid=139406"