Is there an easy way to improve this Tree Normal Form for Busy Beaver candidates? 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.
Your proposed optimization is a special case of the "forward reasoning" nontermination detection that Marxen and Buntrock describe in part 5 of their paper:


  If there is a set S of states such that all transitions from elements of S are defined and their target state is also in S, (and the machine is in one of those states) it will never again leave S and thus not halt (closed state/transition cluster).


If you've implemented this nontermination detection then your optimization is redundant.  You could include it for a possible slight efficiency win.  Your optimization applies whenever we are defining the 2k-th transition and there are currently only k states.  That will not be the case as often as you might think, since Marxen and Buntrock's enumeration algorithm does not assign transitions in order by state index.  Instead, it simulates each Turing machine during enumeration and assigns each transition only as it is reached.

The "forward reasoning" nontermination detection will catch cases that your optimization would not, e.g. in this partially defined 3-state machine:

    0    1
A: 1LB, -?-
B: 1LC, 1LC
C: 1RB, 1RB