Busy Beaver Problem

The Busy Beaver game was introduced in 1962 by Tibor Radó. This game involves the using of Turing Machines with a few conditions in order to play it:

  • The turing machine has n states plus the Halt state;
  • The machine uses a single two-way infinite or unbounded tape;
  • The tape alphabet is only {1} and also the tape can contain a blank symbol ( [] ) (2 symbols in total);
  • The machine transition function consider the non-Halt machine state and the current tape symbol, and  produce three outputs:
  1. a symbol to overwrite the current symbol in the tape;
  2. a direction to move left (L) or right (R);
  3. a state to transition into;

So, for this game, the starting state start’s with a blank cell on the tape as you can see in the following image:

tape_blank
Tape at the starting state

The machine score is the total of 1s number that is on the tape when the machine halts.

turing_tape1111
Machine score = 4

So explaining more the game, the n-state Busy Beaver (BB-n) game is a contest to find the largest possible score (the largest number of 1s in the tape) for a n-state Turing machine. The machine with the highest score possible is called the champion n-state machine.

Now i will explained you how to build Turing machines and how to code in Turing machine simulator for the current knowed busy Beaver states (from state 1 to state 6), but in this tutorial it will only be explained from state 1 from state 4 to give a general idea of the problem.

To code in Turing machine simulator i will use the following website:

http://morphett.info/turing/turing.html

Building Turing Machines and coding in Turing machine simulator

  • 1-state Busy Beaver (BB-1)

Building the Turing Machine

BB1

Code in Turing Machine Simulator

;State 0
0 _ 1 r !

Both, the building machine and the code are saying: in state 0 if you find blank symbol ( _ or []), then write 1 and move to the right (r) and halt (!). Note: Halt state doesn’t count as a state and Halt state is where the Turing Machine finish…

For BB-1 the total score is 1 – total steps = 1.

  • 2-state Busy Beaver (BB-2)

Building the Turing Machine

BB2

Code in Turing Machine Simulator

;State 0
0 _ 1 r 1
0 1 1 l 1

;State 1
1 _ 1 l 0
1 1 1 r !

In state 0 if you find a blank symbol then write 1, move to the right and go to state 1 or in state 0 if you find a 1 symbol, overwrite it with 1, move to the left and go to state;

In state 1 if you find a blank symbol write 1, move to the left and go to state 0 or in state 1 if you find a 1 symbol overwrite it with 1, move to the right and halt.

For BB-2 the total score is 4 – total steps = 6.

  • 3-state Busy Beaver

Building the Turing Machine

BB3

Code in Turing Machine Simulator

;State 0
0 _ 1 r 1
0 1 1 r !

;State 1
1 1 1 r 1
1 _ _ r 2

;State 2
2 _ 1 l 2
2 1 1 l 0

In state 0 if you find a blank symbol write 1, move to the right and go to the state 1 or if you find a 1 symbol, then overwrite it with 1 move to the right and halt;

In state 1 if you find a 1 symbol overwrite it with 1, move to the right and stay at the state 1 (loop) or if you find a blank space make it blank, move to the right and go to the state 2;

In state 2 if you find a blank symbol, then write 1, move to the left and stay at state 2 (loop) or if you find a 1 symbol, overwrite it with 1, move to the left and go to the state 0.

For BB-3 the total score is 6 – total steps = 14

  • 4-state Busy Beaver

Building the Turing Machine

BB4

Code in Turing Machine Simulator

;State 0
0 _ 1 r 1
0 1 1 l 1

;State 1
1 _ 1 l 0
1 1 _ l 2

;State 2
2 _ 1 r !
2 1 1 l 3

;State 3
3 _ 1 r 3
3 1 _ r 0

In state 0 if you find a blank symbol write 1, move to the right and go to the state 1 or if you find a 1 symbol, then overwrite it with 1 move to the left and go to the state 1;

In state 1 if you find a blank symbol write it with 1, move to the left and go to the state 0 or if you find a 1 symbol make it blank, move to the left and go to the state 2;

In state 2 if you find a blank symbol, then write 1 move to the right and go to the halt state or if you find a 1 symbol, overwrite it with 1, move to the left and go to the state 3.

In state 3 if you find a blank symbol, write 1, move to the right and stay at the state 3 (loop) or if you find a 1 symbol, make it a blank space, move to the right and go to the state 0.

For BB-4 the total score is 13 – total steps = 108

 

I hope you learned and enjoyed this lesson…

If you see that is something wrong please let us know…

If you have any questions about this topic please just send a message to us, we are glad to help you at all the times…