<p>Your proposed optimization is a special case of the "forward reasoning" nontermination detection that Marxen and Buntrock describe in part 5 of their paper:</p>

<blockquote>
  <p>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).</p>
</blockquote>

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

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

<pre><code>    0    1
A: 1LB, -?-
B: 1LC, 1LC
C: 1RB, 1RB
</code></pre>

CC BY-SA 3.0
2017-06-30T23:01:59.310Z
2017-06-30T23:01:59.310Z
Adam Dingle
<p>In <a href="http://www.drb.insel.de/~heiner/BB/mabu90.html#Enumeration" rel="nofollow">"Attacking the busy beaver 5" by Heiner Marxen and Jürgen Buntrock</a>, an algorithm to create tree normal candidates is explained (it also contains a concise introduction of the relevant terms).</p>

<p>If during simulation an undefined transition is found, the selection of the enumeration values is made as follows:</p>

<blockquote>
  <p>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.</p>
  
  <p>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:</p>
  
  <ol>
  <li>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).</li>
  <li>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.</li>
  <li>When defining the very last transition, consider only the halt state as target state.</li>
  <li>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.</li>
  <li>If there is a state that M has not yet taken, do not consider the halt state as target state.</li>
  </ol>
</blockquote>

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

<p>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$.</p>

<p>If we don't do this, it would be possible to create closed subsets, or equivalently, unreachable states (described e.g. by <a href="http://www.cogsci.rpi.edu/~heuveb/research/BB/downloads/OwenThesis.pdf" rel="nofollow">Kellett, MA thesis, 2005</a>, p.46), one of whom will be the halting state. Those machines cannot possibly halt obviously.</p>

<p>For instance, given the partially defined 3-state machine <code>1RB 0RB, 1LA -?-, -?- -?-</code>, the next transition (which in this example happens to be $\delta(B,1)$) must point exactly to state C.</p>

<ul>
<li>Pointing to H is not allowed because it would quit too early (unused state C).</li>
<li>Pointing to A or B is not allowed because it would lead to a closed state subset with no way to leave.</li>
</ul>

CC BY-SA 3.0
2015-01-17T07:20:17.250Z
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...
vzn
CC BY-SA 3.0
2015-01-17T18:25:59.080Z
Thanks for the feedback, I added links, also to an introduction.
mafu
CC BY-SA 3.0
2015-01-17T18:31:14.810Z
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.
mafu
CC BY-SA 3.0
2015-01-18T03:23:27.257Z
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.
vzn
CC BY-SA 3.0
2015-01-18T04:43:13.880Z
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$.
mafu
CC BY-SA 3.0
2015-01-18T04:53:52.417Z
I have edited the question to include this information, and added an example.
mafu
CC BY-SA 3.0
2015-01-18T18:15:16.780Z
see maybe some of the confusion. this is not so well explained in the brief M/B writeup but these enumerations are done not independently but _coupled_ with unique/ separate/ associated tape inputs/ outputs, which you dont mention at all. the tape starts out empty and the head traverses the tape and fills up with 0/1 assignments as the transition graph is built up. so theres a (separate/ associated) "partial tape" accompanying _each_ "partial transition graph". make sense?
vzn
<turing-machines>
Is there an easy way to improve this Tree Normal Form for Busy Beaver candidates?
mafu
# Is there an easy way to improve this Tree Normal Form for Busy Beaver candidates?

(Asked by: username_0 on 2015-01-13)

In ["Attacking the busy beaver 5" by Heiner Marxen and Jürgen Buntrock](http://www.drb.insel.de/~heiner/BB/mabu90.html#Enumeration), 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](http://www.cogsci.rpi.edu/~heuveb/research/BB/downloads/OwenThesis.pdf), 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.

**Tags:** turing-machines
> **Comments:**
> **username_1**: 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...  
> **username_0**: Thanks for the feedback, I added links, also to an introduction.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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$.  
> **username_0**: I have edited the question to include this information, and added an example.  
> **username_1**: see maybe some of the confusion. this is not so well explained in the brief M/B writeup but these enumerations are done not independently but _coupled_ with unique/ separate/ associated tape inputs/ outputs, which you dont mention at all. the tape starts out empty and the head traverses the tape and fills up with 0/1 assignments as the transition graph is built up. so theres a (separate/ associated) "partial tape" accompanying _each_ "partial transition graph". make sense?  

---

## 1 answers

### Answer by username_2 on 2017-06-30. Score: 4 | Accepted answer

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


---

