The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
Tree Normalization
In order to accomplish our goal of categorizing every machine in the search space, an effective enumeration strategy must be put in place in order to minimize the computation required while maintaining the completeness of the search. The solution that we have implemented is a generative method known as tree normalization. With this approach, we can completely avoid generating certain types of redundant machines. Consider the machines represented below:
Redundancy: Isomorphic Machines
The Turing machines illustrated below are identical to one another except that states 2 and 3 have been interchanged. Clearly, the machines are functionally equivalent. For any n-state Turing machine there are n! isomorphic machines (since there are n! permutations of the n state-numbers), but we need to consider only one of these since their behavior will be identical.
Isomorph1
Isomorph2
Redundancy: Unused-State Machines
This Turing machine is a 6-state machine but only four of the states are reachable (i.e. because there are no transitions terminating in either state 4 or 5). For every n-state machine that has 1 unreachable state, there is an equivalent machine with n - 1 states, so no such machines need to be considered for our search to be exhaustive.
Unused state machine
Solution: Tree Normalization Schema
In order to eliminate the above redundancies in our enumeration strategy, we have chosen to employ a tree normalization solution. The general idea is as follows: The root node of the tree contains a single-state machine with no transitions defined. This machine is consequently run on an infinite, blank tape. Clearly, it will do nothing, as no transitions are defined. However, we consider this a "partial machine" as the machine halted, but not in the halting state. The conditions under which it halted therefore, are not halting conditions, but rather oppurtunities to create additional transitions. In the case of the root node, it halts in state 0, reading a 0 on the tape. Therefore, we create child machines, each of which contains a transition for the case in state 0, reading a 0. We enumerate all possible transitions for this case to all possible existing states, as well as to one of the remaining unused states (if the number of currently used transitions is less than n for which we are calculating BB(n)). The child machines are then pushed onto a stack, and successfully popped off, with the above general procedure applied to each until all possible machines have been defined.
Expanded root of normalized tree
It is easy to see that no machine which qualifies as an unused-state machine specified above will be generated with such a schema. This is because a particular transition is only defined if a machine is guaranteed to reach the particular state and read symbol for this particular transition. Therefore, no transition can ever be defined from a state which has no transitions terminating in it. In addition, it can be proven that this technique never generates a pair of isomorph machines as specified above. A complete discussion of this tree normalization strategy in more detail can be found in section 7 of the superpaper.
Additional Filters
In addition to the specifics of the machine enumeration strategy, there are also additional filters which can be implemented in the procedure to weed out even more redunancies in the search space. These are as follows:

Nonproductive Transitions
Empty tape machines
Mirror machines
Optimization Filters
Project Components
Current Champions
n B(n) b(n) O(n) o(n)
1 1T 1T 1T 1T
2 2T 3T 2T 3T
3 3? 13R 3O 13R
4 5? 31R 8O 37R
5 11? 57R 15O 111O
6 25M 255M 239R 41606R
7 196M 13682M

8 672M 198339M


n P(n) p(n) R(n) r(n)
1 1T 2T 1T 2T
2 2T 4T 2T 4T
3 4R 14R 4R 14R
4 7R 32R 8R 38R
5 16R 112R 16R 112R
6 163R 27174R 240R 41607R

RSet by present RPI effort
MSet by Machado and Pereira
OSet by Oberschelp, et al.
TTrivial records
?Unknown origin

Also note: A solid yellow background indicates records have been explicitly confirmed by the present effort. A faded yellow indicates relative confidence but not yet an explicit proof.
Busy Beaver Research Team
Bram van Heuveln
Selmer Bringsjord
Boleslaw Szymanski
Carlos Varela
Kyle Ross
Owen Kellett
Shailesh Kelkar