Comprehension of the Busy Beaver problem requires a conceptual understanding of what a turing machine is and does. In short, a turing machine is an abstract model of computation that encapsulates the definition of computability. More formally, a turing machine is structured with the following components:

1. A finite set of states - the machine can only be in one state at a time during execution
2. A finite alphabet which the machine operates on
3. A finite set of instructions
4. An infinitely long tape of characters from the finite alphabet which maintains a current read-position that moves back and forth along the tape according to the instructions

Each instruction takes the following format: (current state, current symbol, new state, new symbol, move) where the current state is the state that the machine is currently in and current symbol is the symbol corresponding to the position of the read head on the tape. Execution of the instruction moves the machine to the new state, replaces the current symbol on the tape with the new symbol, and then moves the read head position left or right according to the value of move. A Turing Machine, therefore, takes a set of characters and current position on the tape as input and transforms the tape according to its instruction set. The machine halts when it reaches either a state, symbol pair for which there is no corresponding instruction, or it transitions into a explicitly defined halt state.

Turing Machines can be easily conceptualized when depicted in a graphical diagram as shown below. Each node in the diagram represents a state and each directed arrow represents an instruction. Each instruction contains a label of the following format: (Read Symbol:Write Symbol,Move Direction). When a machine is in a particular state, the action that it performs corresponds to the "Write Symbol" and "Move Direction" of the instruction in which the "Read Symbol" matches the symbol at the current read head on the tape. The machine then transitions to the state in which the instruction's arrow terminates and repeats the process. The machine halts when it enters an explicitly defined halt state or no instruction can be found given the current state and read head symbol. The execution of the very simple Turing Machine below is shown. The machine operates on an initially infinite tape of all 0's with an alphabet of {0,1}:

0   State 0  10  State 1  11  State 0 011  State 0 111  State 1 101  State 2

^*Note: infinite sequences of 0's are truncated from the left and right sides of each tape sequence

Considering the definition of a Turing Machine above, we can now define the Busy Beaver function, invented by Tibor Rado around 1960. As you may have noticed, it is quite easy to construct a turing machine that never halts given a particular piece of input. In fact, it is provably impossible to define an algorithm which, given a turing machine and an input tape, can definitively return whether or not that machine halts on that particular input. This is classicly known as the halting problem and is what the Busy Beaver is centered around. The Busy Beaver function is defined as follows:

Consider a binary alphabet Turing Machine which is given an infinite, blank tape as input. If this machine halts, we define its productivity as the number of 1's left on the tape after the machine is run to completion. If it does not halt, the machine is given a productivity value of zero. Now consider all of the binary alphabet Turing Machines that have n states. The machine in this set which has the highest productivity is called a Busy Beaver, and its productivity is the result of the Busy Beaver function BB(n). Alternatively, the productivity score can be defined as the number of transitions made before halting.

Clearly, if we had an algorithm that could solve the halting problem than we could very easily devise an algorithm to solve the Busy Beaver problem. This is not the case, however, and the proof of the uncomputability of the Busy Beaver problem can be found here.

Quadruple vs. Quintuple Formulation
The Turing machine described above is classified as a quintuple formulation Turing machine. This is so because each instruction contains five pieces of information (current state, current symbol, new state, new symbol, move). During every transition, a write action and a move action is performed before proceeding to the next state. Consider, now, a Turing machine whose instructions are only allowed to perform one action for every transition. An instruction can specify either a new write symbol or a move direction but not both. Such a machine is of the quadruple variety of Turing machines. Quadruple machines and quintuple machines are provably equivalent in expressive power.

Halting Type
There are two methods of specifying how a Turing machine halts. One is by simply not creating an instruction for a particular state, symbol pair. When the machine encounters these conditions, it has no action to take and will therefore halt. We describe these machines as implicit halt machines. The second method is to create an additional halting state. If the machine makes a transition to this new halt state, it immediately halts. These machines are thus explicit halt machines. It is important to note, for the purposes of studying the Busy Beaver problem, that an n-state Turing machine has n states plus exactly one halt state. The Turing machines considered in our research have the restriction that there can be no outgoing transitions from the halt state---when the machine is in the halt state, it cannot be run any further.

Standard Position
The definition of the Busy Beaver problem defined above makes no reference to the nature of the tape after the machine has halted beyond strictly the number of 1's that are present. A variant of the problem enforces the additional restriction that a machine can not be considered a Busy Beaver candidate unless the resulting pattern of 1's on the tape is in a contiguous sequence with the read head located at the left-most 1. We call this configuration "standard position"

Our Attack focuses on the variants of the quadruple formulation of the problem as defined above. Most previous work on the Busy Beaver problem has dealt with some variant of the binary alphabet quintuple formulation. There has, however, been some previous study of several of the quadruple variants:

• Boolos and Jeffrey have studied the quadruple, implicit halt, standard position formulation. It was in part this work that inspired the present research. Busy Beaver maximal productivity numbers for this formulation will be denoted B(n) and maximal shift numbers will be denoted b(n).
• A Portuguese group used a combination of genetic algorithms and hill-climbing techniques to study the quadruple, explicit halt, standard position variant of the problem. We call this function P(n) and the associated shift function p(n).
• A German group (Oberschelp, et al.) used probabilistic reasoning to research the quadruple, implicit halt, non-standard formulation. We define O(n) and o(n) to represent the productivity and shift champions, respectively, for this variant.
• The quadruple analogue to Rado's original problem (quadruple, explicit halt, non-standard) has not, to our knowledge, been studied previously, but we use R(n) (for Rado) to denote the productivity champions for this version and r(n) for the shift champions.