Busy Beaver function realised using Turing MAchine

Consider a Turing machine with the binary alphabet {0, 1} and n operational states (often labelled 1, 2, ... n or A, B, C, ...) and an additional Halt state.

His definition of a Turing machine was as follows:

* The machine runs on a 2-way infinite (or unbounded) tape.
* At each step, two conditions --

1. the machine's current "state" (instruction); and
2. the tape symbol the machine's head is scanning

-- define each of the following:

1. a unique symbol to write (the machine can overwrite a 1 on a 0, a 0 on a 1, a 1 on a 1, and a 0 on a 0);
2. a direction to move (Left or Right but "none" is not allowed in this model); and
3. a state to transition into (may be the same as the one it was in).

* The machine halts if and when it reaches the special Halt state.

Now start with a blank tape (i.e. every cell has a 0 in it) and a TABLE of n instructions. Run the machine; if it halts, note the number of 1s it leaves on the tape.

The n-state busy beaver (BB-n) game is a competition to find an n-state Turing machine which leaves the largest number of 1s on its tape before halting.

In order to take part in this competition you must submit the description of an n-state Turing machine that halts along with the number of steps it takes to halt to a qualified umpire who must test its validity. It is important that you provide the number of steps taken to halt, because if you do not and your Turing machine does not halt, there is no general algorithm that the umpire can use to prove that it will not halt. Whereas if you do provide a finite number of steps along with a candidate machine, the umpire can (given enough time) decide whether or not the machine will halt in so many steps.

The busy beaver function Σ(n)

The busy beaver function Σ(n) is defined as the number of 1s that the champion Turing machine prints given the number n of "states" (Turing-instructions) and a blank tape at the outset.

Radó went on to demonstrate that there is a well-defined champion to the n-state busy beaver Game:

There are a finite number of Turing machines with n states and 2 symbols, specifically there are [4n+2]2n of them. In addition it is trivial that some of these are halting machines; i.e., there exists at least one n-state, 2-symbol TM that will halt, for every n.

Now define:

* En to be the finite, non-empty set of halting n-state, 2-symbol Turing machines.
* σ(M) = the number of 1s left on the tape after the Turing machine M is run on a blank tape for any M in En.
* Σ(n) = max { σ(M) | M in En} (The largest number of 1s written by any n-state 2-symbol Turing machine)

Since σ(M) is a non-negative finite number for any M halting (in En), and since En is a non-empty finite set, Σ(n) is a well-defined non-negative finite number for any n.

This Σ is the busy beaver function and any n-state, 2-symbol machine M for which σ(M) = Σ(n) (i.e. which attains the maximum) is called a busy beaver.