Busy beaver candidate elimination: Minimum space requirements

Question

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

Answer 1

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.