Busy beaver

A player should conceive a transition table aiming for the longest output of 1s on the tape while making sure the machine will halt eventually.

The transition function may be seen as a finite table of 5-tuples, each of the form
(current state, current symbol, symbol to write, direction of shift, next state).

"Running" the machine consists of starting in the starting state, with the current tape cell being any cell of a blank (all-0) tape, and then iterating the transition function until the Halt state is entered (if ever). If, and only if, the machine eventually halts, then the number of 1s finally remaining on the tape is called the machine's score.

Radó required that each machine entered in the contest be accompanied by a statement of the exact number of steps it takes to reach the Halt state, thus allowing the score of each entry to be verified (in principle) by running the machine for the stated number of steps. (If entries were to consist only of machine descriptions, then the problem of verifying every potential entry is undecidable, because it is equivalent to the well-known halting problem — there would be no effective way to decide whether an arbitrary machine eventually halts.)

Because these Turing machines are required to have a shift in each and every transition or "step" (including any transition to a Halt state), the max-shifts function is at the same time a max-steps function.

Milton Green, in his 1964 paper "A Lower Bound on Rado's Sigma Function for Binary Turing Machines", constructed a set of Turing machines demonstrating that

Σ(7) is by the same way much, much greater than current common lower bound 331 (nearly 618 trillion), so the second lower bound is also very, very weak.

It is possible to further generalize the busy beaver function by extending to more than one dimension.

Likewise we could define an analog to the Σ function for register machines as the largest number which can be present in any register on halting, for a given number of instructions.

The Turing machines that achieve these values are available on webpage. Each of these websites also contains some analysis of the Turing machines and references to the proofs of the exact values.

Shows the first 100,000 timesteps of the current best 5-state busy beaver. Orange is "1", white is "0" (image compressed vertically).

Each machine begins in state A with an infinite tape that contains all 0s. Thus, the initial symbol read from the tape is a 0.

Note in the image to the right how this solution is similar qualitatively to the evolution of some cellular automata.

In the following table, the rules for each busy beaver (maximizing Σ) are represented visually, with orange squares corresponding to a "1" on the tape, and white corresponding to "0". The position of the head is indicated by the black ovoid, with the orientation of the head representing the state. Individual tapes are laid out horizontally, with time progressing vertically. The halt state is represented by a rule which maps one state to itself (head doesn't move).

Evolution of 1-state busy beaver until halt. The initial state triggers a halt, with a single "1" being written before termination.
Evolution of 4-state busy beaver until halt. Bottom line in left image wraps to top line of right image.