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:

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.

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.

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.
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.

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