In "Attacking the busy beaver 5" by Heiner Marxen and Jürgen Buntrock, an algorithm to create tree normal candidates is explained (it also contains a concise introduction of the relevant terms).
If during simulation an undefined transition is found, the selection of the enumeration values is made as follows:
Enumerate all meaningful values (see below) for this transition, and recursively do step 2 with M set to each of these more completely defined machines.
The set of legal transition values is formed by an arbitrary combination of (n+1) target states, 2 symbols to write, and 2 directions to move. The set of meaningful transitions enumerated in step 6 is a subset of all legal ones by the following reduction rules:
- From the set of states M has not yet taken, only the smallest one (according to some arbitrary but fixed order on the states) is used as target state (isomorphism).
- When defining the very first transition force a state change (else M never halts), write a one (isomorphism), and move left (symmetry). This completely fixes the very first transition.
- When defining the very last transition, consider only the halt state as target state.
- If the target state is the halt state, go left (makes no difference) and write a one (never worse). This completely fixes the last transition.
- If there is a state that M has not yet taken, do not consider the halt state as target state.
I'm not sure if I'm missing something, but should there not be a rule that enforces using a new state if we're determining the last open slot of all currently used states? This new rule would replace/extend rule 3 above.
In other words: With $2k-1, k \leq N$ transitions defined, and the maximum index of states used being $\leq k$, the $2k$-th transition must point to a state with index > $k$.
If we don't do this, it would be possible to create closed subsets, or equivalently, unreachable states (described e.g. by Kellett, MA thesis, 2005, p.46), one of whom will be the halting state. Those machines cannot possibly halt obviously.
For instance, given the partially defined 3-state machine 1RB 0RB, 1LA -?-, -?- -?-
, the next transition (which in this example happens to be $\delta(B,1)$) must point exactly to state C.
- Pointing to H is not allowed because it would quit too early (unused state C).
- Pointing to A or B is not allowed because it would lead to a closed state subset with no way to leave.