3
$\begingroup$

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:

  1. 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).
  2. 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.
  3. When defining the very last transition, consider only the halt state as target state.
  4. 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.
  5. 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.
Improve this question
$\endgroup$
7
  • $\begingroup$ it would be helpful to cite the online versions of these papers as urls. also more bkg/ intro on the algorithm would be helpful & defn of basic terms eg "undefined transition", "tree normal" etc (brief ok)... probably these are all concepts that mostly originate/ exist only in a single paper. all such algorithms are somewhat ad hoc and there are various simple improvements... $\endgroup$
    – vzn
    Jan 17 '15 at 7:20
  • $\begingroup$ Thanks for the feedback, I added links, also to an introduction. $\endgroup$
    – mafu
    Jan 17 '15 at 18:25
  • $\begingroup$ TNF has been used by virtually all authors (e.g. Brady, Marxen/Buntrock, Machlin/Stout, Ross, Kellett) quickly after the invention of the Busy Beaver concept. Even though they all describe this technique, none of them seems to apply the proposed technique, not even the quite recent Kellet 2005. Maybe I missed it, or my idea is misled to begin with for some reason. $\endgroup$
    – mafu
    Jan 17 '15 at 18:31
  • $\begingroup$ ok thx reviewed it. the idea is that 2N transitions of the TM (N states, 0/1 input) are "open" at the beginning. the algorithm is enumerating different transition graphs. for step (3) if all the transitions other than the last one (of the "partial (defined) graph") point to nonhalting states, then the last one must point to a halting state for the TM to be eventually halting. otherwise all transitions of the fully defined graph point to nonhalting states only and the TM cannot halt. the rules are basically designed to enumerate all transition graphs that are not isomorphic. $\endgroup$
    – vzn
    Jan 18 '15 at 3:23
  • $\begingroup$ Yes, exactly. What I'm proposing is to extend rule 3: 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$. $\endgroup$
    – mafu
    Jan 18 '15 at 4:43
3
$\begingroup$

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
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.