3
$\begingroup$

In the case of LBAs (Linear Bounded Automaton), in writing a decider for the language

$\qquad A = \{ \langle M,w\rangle \mid M\ \mathrm{LBA}, w \in \mathcal{L}(M) \}$

we reject the input after a specific number (number of possible different configurations) of computation steps. We say that the machine must be looping after this many steps. Why don't we just check in every step to see if there is a loop (repetition of the same configuration) and if it is the case then just reject the input?

$\endgroup$

2 Answers 2

5
$\begingroup$

If I understand the question correctly, you are asking why are we bounding the number of configurations, rather than checking for a repeating configuration?

Well, clearly these are equivalent in the sense that in both ways you will detect a repeating configuration.

In the first method, we use the pigeonhole principle, and we say that if we passed a certain number of configurations, then there must be a repetition, since in an LBA the number of configurations is bounded (after fixing the input). In order to detect this, we must keep a counter of the number of configurations we passed. The advantage of this method is that keeping the counter is simple (it takes linear space). The disadvantage is that the loop may have occurred early in the run, and we will only detect it late (after an exponential number of steps).

In the second method, we need to track the configurations we have seen so far, and compare every new configuration to all the configurations we have already seen. The advantage is clear- we will detect the loop immediately when it is caused. But the disadvantage is huge - we need to track all the configurations - this may take exponential space, and in every step we need to compare all the configurations to the current one.

Essentially, the first method solves $A$ in PSPACE, whereas the second solves it in EXPSPACE, so we usually take the first.

$\endgroup$
3
$\begingroup$

Because the TM, as it has an infinite tape, can get into a loop that runs off into infinity and the configuration doesn't repeat. For a minimal example, just make it move right on blank, and rewrite with 0. Start it on a blank tape, and watch it ride into the sunset.

$\endgroup$
1
  • $\begingroup$ Since the OP accepted Shauli's answer, I assume this is not what they were asking and clarified the question accordingly. $\endgroup$
    – Raphael
    Commented Apr 2, 2013 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.