Introduction to the Busy Beaver Function

The following is an informal explanation of what the Busy Beaver function means and how it is determined.

The values of the Busy Beaver function are a result of playing the Busy Beaver game.

Premise of the game:

Imagine you have a robot on an infinite 1-dimensional tape full of zeros. Your friend challenges you to create a program that will allow the robot to turn those zeros into as many ones as possible.

You think about it for a moment, and you have a genius idea. This is your program:

• [State A]
  • If I see 0: Turn it into a 1, Move to the Right, Stay on State A
  • If I see 1: N/A

Your robot turns a zero into a one, and then moves to the right. Your robot will then see another zero. This will occur infinitely often, creating an infinite number of ones! You win, right?

Well, not quite. The busy beaver game forbids a program to have an infinite runtime (what use is a computer program that never ends?). In the busy beaver game, the robot must eventually halt.

Ok, you think. Here is a program that can create arbitrarily many ones and then halt:

• [State A]
  • If I see 0: Turn it into a 1, Move to the Right, Go to State B
  • If I see 1: N/A
• [State B]
  • If I see 0: Turn it into a 1, Move to the Right, Go to State C
  • If I see 1: N/A
• [State C]
  • If I see 0: Turn it into a 1, Move to the Right, Go to State D
  • If I see 1: N/A
• [State D]
  • If I see 0: Turn it into a 1, Move to the Right, Go to State E
  • If I see 1: N/A
• [State E]
  • If I see 0: Turn it into a 1, Move to the Right, Go to State F
  • If I see 1: N/A
• [State F]
  • If I see 0: Turn it into a 1, Move to the Right, Go to State HALT
  • If I see 1: N/A

A robot running this program will create 6 ones before halting. But you can add as many states as you like, and the program will create that many ones. So you've beaten the busy beaver game—you just need an extremely large number of states.

For this reason, the busy beaver game sets a limit on the number of states your program can use. If we set the limit to 2 states, you can make the following program. I strongly suggest you get a paper and pencil and run this program manually. This will allow you to get a feel for how busy beaver programs work. (Note: the robot will always start on a tape full of zeros and on state A)

• [State A]
  • If I see 0: Turn it into a 1, Move to the Right, Go to State B
  • If I see 1: Keep it a 1, Move to the Left, Go to State B
• [State B]
  • If I see 0: Turn it into a 1, Move to the Left, Go to State A
  • If I see 1: Keep it a 1, Move to the Right, Go to State HALT

If you ran this program, you will see that the robot reaches the halt state on step 6, and it creates 4 ones in the process. And it turns out that this program is the best you can do with 2 states. Therefore, the busy beaver value for 2 states is 4 ones and 6 steps. In other words:

• BB_Σ(2) = 4
• BB_S(2) = 6