Busy Beaver - The Busy Beaver Game

The Busy Beaver Game

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:

1. the current non-Halt state,
2. the symbol in the current tape cell,

and produces three outputs:

1. a symbol to write over the one in the current tape cell (it may be the same symbol as the one overwritten),
2. 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
3. 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.

Radó required that each machine entered in the contest be accompanied by a statement of the exact number of steps it takes to reach the Halt state, thus allowing the score of each entry to be verified (in principle) by running the machine for the stated number of steps. (If entries were to consist only of machine descriptions, then the problem of verifying every potential entry is undecidable, because it is equivalent to the well-known halting problem — there would be no effective way to decide whether an arbitrary machine eventually halts.)