4
$\begingroup$

I'm currently enrolled in a course that introduces Turing machines. As I wanted to play around a bit, I wrote a little TM engine and had it search for busy beavers (it successfully found the 4-state 2-symbol BB listed in Wikipedia).

To more quickly eliminate bad candidates, I'm searching for conditions that imply indefinite runtime. I found a couple of filters already, but the number of indefinite runs is still rather high (indefinite, as in, either seemingly running forever or sometimes checked manually).

In this questions in particular I would like to inquire what space requirements a BB must have after a certain number of shifts. If it accessed less of the tape than this number, it can be dismissed directly. For this purpose, consider the tape length to extend exactly as far as the head went at most in either direction.

As simple upper bound I guess something like $N_{shifts} \leq {N_{TapeLength}}^{|Q|}$ could work, though I am not sure this is even correct. Also, it should certainly be possible to improve this boundary considerably.

Edit: I currently employ the following eliminations:

Static

  • Fixed first/last transition (A0-B1R,xx-H1R)
  • State enumeration ordering
  • All states in transitive closure of A
  • H in transitive closure of all states
  • Trap states
  • Equivalent states
  • Inability to change the tape

Dynamic

  • At either end of the tape, current state's transitive closure (using only 0-transitions) always directs further away
$\endgroup$
  • $\begingroup$ I just noticed this site is for research-level questions. I'm only in 3rd semester so I cannot judge if this applies to my question (probably not). Should I ask elsewhere? $\endgroup$ – mafu Oct 27 '14 at 23:19
  • 1
    $\begingroup$ Do you know the techniques used to find the current record holders? You can find a comprehensive list of papers/links on Heiner Marxen's BB page BTW many loop detecting techniques are based on running two simulations (usually not of the small TM itself, but of an extended "macro" machine that embeds many steps of the simpler TM) in parallel: one slower (x1 speed) and one faster (x2 speed), and comparing the two configurations. $\endgroup$ – Marzio De Biasi Oct 28 '14 at 8:49
  • $\begingroup$ @MarzioDeBiasi I have only yet seen the Marxen/Buntrock paper. I'll read the resources on the site, it looks very interesting. The idea of running two TM in parallel is a very good hint, too. $\endgroup$ – mafu Oct 28 '14 at 10:12
  • $\begingroup$ undecidability analysis is definitely research level and arguably will always be so! but in some ways (eg empirical studies such as those above) a very narrow field or research program at the moment. $\endgroup$ – vzn Jan 17 '15 at 7:23
4
$\begingroup$

There are many methods for detecting that specific TMs will run infinitely. As Marzio mentioned, Heiner Marzen's page and papers provide almost all of the currently used methods.

The method you describe is a great simple requirement. Specifically, if we know that the TM has only moved around on a small tape of size $N_{tape}$, then the exact configuration at every step so far can be described by (1) the symbols at each of these $N_{tape}$ cells, (2) the position of the reading head and (3) the TM state. Thus there are $|Q| \cdot N_{tape} \cdot |S|^{N_{tape}}$ possible configurations (Where $|Q|$ is the number of states and $|S|$ is the number of symbols). So, if the TM has taken more than that many steps of computation, you know that it must have been in one configuration at least twice and thus that it will infinitely repeat.

However, I don't think this method works very often in practice because it is more common for TMs to run off infinitely in one direction than to stay on a small section of tape.

$\endgroup$
  • $\begingroup$ Thank you for this good explanation. I'm already able to catch trivial infinite side runners, so the currently dominant problem in my enumeration space is local infinity, which your answer helps to solve. The next steps after that will certainly require more advanced methods, as you pointed out. $\endgroup$ – mafu Oct 28 '14 at 18:42

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.