On Tue, Jul 23, 2013 at 2:19 PM, Daniel C. <[email protected]> wrote:
> 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
The problem with enumerating Turing Machines is the tape. You can't,
in general, enumerate all Turing machines of n states because they
include a finite tape that can hold an arbitrarily large finite number
of non-blank cells. Of course, the BB problem specifically states an
all-blank tape; I think this makes potential-BB Turing machines
enumerable. Just enumerate all the possible 5-tuples with the {0, 1}
alphabet and n states, and there you go.
--Levi
/*
PLUG: http://plug.org, #utah on irc.freenode.net
Unsubscribe: http://plug.org/mailman/options/plug
Don't fear the penguin.
*/
