0
$\begingroup$

A Turing machine is given. The following problem is decidable :

Does the Turing-machine stay within given bounds of the tape (for example in the range $-100$ to $100$) AND halt ?

The problem is decidable because eventually the Turing machine must repeat an earlier configuration (and then never halts) or halt or leave the given range. My question :

Is there an efficient method to decide this variant of the halting problem ? Or do we have to let the machine run and note the configurations until we recognize a repetition or the machine halts ?

$\endgroup$
1
$\begingroup$

I would say that as with most of these kinds of halting/busy beaver problems, both approaches (pure analysis and simulation) will prove to be useful.

Yes, for some machines you can determine their behavior by pure analysis without actually simulating them, but most machines have such complex behavior that you have to run them. Then, after some time (hopefully not too long!), the machine will actually halt, leave the bounded range, or repeat some configuration. It is also possible that after a while you get some idea as to what the machine's macro-behavior is, so that you can go back and try to do some analysis again.

But from my experience there will still be many machines (at least if you have four or more states) whose behavior is so chaotic that you have to run them for a very, very long time, and probably still don't get any insight as to their behavior until they actually halt, leave the region, or actually end up in a repeating configuration.

The good news is that you can calculate how many possible configurations there are and at least get some upper bound as to how many steps you may have to run the machine so you don't go in blind ... though that upper bound will quickly become too large for practical purposes, e.g. with the tape going out 100 squares to the left and right and assuming a binary alphabet you already have $2^{201}$ possible tape-configurations and thus even more state-tape configurations .. not good!

$\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.