Busy Beaver Numbers

Daniel C. dcrookston at gmail.com
Tue Jul 23 14:19:52 MDT 2013


I may be getting my terms confused.  Here are the rules for the BB
game, according to Wikipedia
(http://en.wikipedia.org/wiki/Busy_beaver)

The n-state busy beaver game (or BB-n game), introduced in Tibor
Radó's 1962 paper, involves a class of Turing machines, each member of
which is required to meet the following design specifications:

* The machine has n "operational" states plus a Halt state, where n is
a positive integer, and one of the n states is distinguished as the
starting state. (Typically, the states are labelled by 1, 2, ..., n,
with state 1 as the starting state, or by A, B, C, ..., with state A
as the starting state.)
* The machine uses a single two-way infinite (or unbounded) tape.
* The tape alphabet is {0, 1}, with 0 serving as the blank symbol.
* The machine's transition function takes two inputs:
    - the current non-Halt state,
    - the symbol in the current tape cell,
and produces three outputs:
    - a symbol to write over the one in the current tape cell (it may
be the same symbol as the one overwritten),
    - a direction to move (left or right; that is, shift to the tape
cell one place to the left or right of the current cell), and
    - a state to transition into (which may be the Halt state).

The transition function may be seen as a finite table of 5-tuples,
each of the form (current state, current symbol, symbol to write,
direction of shift, next state).

"Running" the machine consists of starting in the starting state, with
the current tape cell being any cell of a blank (all-0) tape, and then
iterating the transition function until the Halt state is entered (if
ever). If, and only if, the machine eventually halts, then the number
of 1s finally remaining on the tape is called the machine's score.

The n-state busy beaver (BB-n) game is a contest to find such an
n-state Turing machine having the largest possible score — the largest
number of 1s on its tape after halting. A machine that attains the
largest possible score among all n-state Turing machines is called an
n-state busy beaver, and a machine whose score is merely the highest
so far attained (perhaps not the largest possible) is called a
champion n-state machine.

-------

So what I'm asking is whether it is possible to procedurally generate
all possible n-state Turing machines that have an alphabet of {0, 1}.
Obviously you would have to examine them each individually to see
whether they halt, but at least you'd have a list of all of them,
which is a finite (if large) set.

-Dan

On Tue, Jul 23, 2013 at 3:53 PM, Levi Pearson <levipearson at gmail.com> wrote:
> It's well known that BB(n) is not a computable function.  Your
> question is not the typical phrasing of the Busy Beaver problem, so
> I'm not sure how it relates to it.  I don't think they're equivalent,
> as BB is about a certain kind of Turing machine, and you're asking
> about finite automata.
>
> The enumeration of all finite state automata of n states (for some
> finite alphabet) should be computable, but I don't think it's a
> tractable problem.  Also, all finite automata will halt on a finite
> input string, as they consume one input token per state transition.
>
> Now, if you actually meant automata in general rather than finite
> automata, that's another story, and I haven't put any thought into
> that one yet.
>
>      --Levi
>
> /*
> PLUG: http://plug.org, #utah on irc.freenode.net
> Unsubscribe: http://plug.org/mailman/options/plug
> Don't fear the penguin.
> */


More information about the PLUG mailing list