# Busy beaver candidate elimination: Minimum space requirements

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
• 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? – mafu Oct 27 '14 at 23:19
• 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. – Marzio De Biasi Oct 28 '14 at 8:49
• @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. – mafu Oct 28 '14 at 10:12
• 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. – vzn Jan 17 '15 at 7:23

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.