The Busy Beaver Turing Machine

The Busy Beaver is a game invented by Tibor Radó that he used to teach his students about the Turing Machine.

The object of the game is to design a Turing Machine that, starting with a completely blank tape, will have the most 1's printed on the tape when it halts. Before the game begins, a decision is made as to how many states are allowed for the Turing Machine. Any Turing Machine that never stops and just runs forever, or that stops because it crashes because of an illegal instruction, is disqualified.

As an alternative, the object of the game can be to design a Turing Machine that will have taken the most steps before it stops. The rest of the rules are the same.

---

For example, suppose we decide to play this game using Turing Machines with only 3 states. Then, each contestant must come up with 6 instructions for the Turing Machine; 2 instructions for each state--one for when the Turing Machine reads 0, and another for when the Turing Machine reads 1. Each instruction consists of three consecutive commands: write either 0 or 1 on the tape; move the tape 1 square to the right, or 1 square to the left, or stop; and the state to which the Turing Machine should go next. (Of course, at least one of these instructions must have a stop, or else it'll run forever and be disqualified.)

Then, all contestants run their Turing Machines. When all the Turing Machines stop running, the one whose Turing Machine has the most 1's on the tape is declared the winner. Also, the one whose Turing Machine took the most steps before it stopped is also declared another winner.

---

Since Tibor Radó invented this game, people have been publishing winning strategies that gave the most 1's on the tape, or ran the longest. Believe it or not, lots of people are still working on these problems!!!! If you allow too many states for the Turing Machines, then the game can run for years!!!

---

Of course, the Busy Beaver Turing Machines are not just all fun and games. They have also been used to give further insight into Turing Machines and mathematics.

In 1962, Tibor Radó published the paper "On non-computable functions" in the Bell System Technical Journal, where he first defined the Busy Beaver problem and proved that it was uncomputable and grew faster than any computable function.