THE BUSY BEAVER SURPRISE-IN-A-BOX

The following machine has been named the Busy Beaver Surprise-in-a-Box because (1) it has a perfectly square (3 symbols x 3 states) description table, and (2) it is confined to operate in a relatively short segment of tape, and (3) it is guaranteed to surprise you!

Start the machine in the center of a 60 square blank (all 0) tape. Operate the machine. Under the restrictions imposed, the machine is guaranteed either (1) to halt, or (2) get into a fixed repeating loop, or (3) go off the end of its restricted length tape. It is not guaranteed that either situation (1) or situation (2) will occur. However, since the tape is of length 60, it has 3^60 possible arrangements, and there are 60 possible squares for the machine to scan, and the machine can be in any one of three possible states. This gives you an upper bound of 3^60 (three to the sixtieth power) times the 60 possible scanning positions of the machine, times the three possible states. Now, 3^60=(3^10)^60, and since 3^10=59,049 is less than 60,000 we can neatly say the upper bound is less than


3x60x60000x60000x60000x60000x60000x60000 ,

which reduces to 30x6^7x10^24 or

8,398,080,000,000,000,000,000,000,000,000 .

Remember, this is an upper bound on all possible tape configurations with the state and scanning position of the machine included. If the machine has not already halted, and if the machine has not already gone off the end of the tape, and it finally reaches the number of steps above, then it is in a fixed loop and will repeat. Mathematically speaking then, the blank tape halting problem for the machine below can be decided straightforwardly. It just depends upon your practical definition for infinite.

Here is the description of the machine (following those on the main page with symbols 0, 1, 2 across the top above the columns and states 1, 2, 3 numbered down the rows, each triplet representing [q,m,s] or [next state, move, replacement symbol], and [0,0,0] representing halt.)


Busy Beaver Surprise-in-a-Box Description Table
2 1 1 , 2-1 2 , 3-1 1;
1-1 1 , 2 1 2 , 2 1 1;
0 0 0 , 1-1 2 , 3-1 0;
Rows down correspond to states q1, q2, q3.
Symbols {0,1,2} correspond to columns across.
Triplet entries are (q, m, s), i.e. (state,move,symbol),
where states q1, q2, q3 are represented by 1, 2, and 3,
with m=-1 for L or left, m= 1 for R or right.

Once started in the middle of a 60 square blank tape, will the machine ever halt, go off the end of the tape, or go into a fixed loop? Have fun!





Back to the Busy Beaver page.