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
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.)
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
Back to the Busy Beaver page.