0
$\begingroup$

The following theorem from Michael Sipser's book "Introduction to the Theory of Computation" states:

$A_{\textrm{LBA}}= \{ \langle M, w \rangle \mid \text{$M$ is an LBA that accepts string $w$} \}$.

THEOREM: $A_{\mathrm{LBA}}$ is decidable.

On the proof part, it states:

The idea for detecting when $M$ is looping is that as $M$ computes on $w$, it goes from configuration to configuration. If $M$ ever repeats a configuration, it would go on to repeat this configuration over and over again and thus be in a loop.

I do not understand this: "If $M$ ever repeats a configuration, it would go on to repeat this configuration over and over again". What if $M$ only repeat one configuration, then halts?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The machine $M$ is deterministic. This means that, if $M$ is in a certain configuration $c$, then there is a single fixed configuration $c'$ (determined by the rules of $M$) which the execution of one step will lead it to. If $M$ ever reaches the configuration $c$ again, then the configuration $c'$ will follow no matter what. Hence, if the computation of $M$ causes it to be assume configurations $c_1, \dots, c_n$ and $c_n = c_1$, then $M$ will repeat the loop $c_1, \ldots, c_n$ indefinitely.

Improve this answer
$\endgroup$
9
  • $\begingroup$ What if we change the $M$ to a normal deterministic turing machine, which is allowed to move off the input portion. if $C_{1}$ = $C_{n}$, does $M$ will repeat the loop too? $\endgroup$
    – Anonemous
    Commented Aug 7, 2019 at 15:05
  • $\begingroup$ "Configuration" comprises the contents of all tapes of $M$ as well as the positions of every head and $M$'s internal state. Hence, it does not matter. $\endgroup$
    – dkaeae
    Commented Aug 7, 2019 at 15:56
  • $\begingroup$ If $M$ goes to an infinite loop on $w$, does it mean that : $w$ does not belong to the language which $M$ recognize? $\endgroup$
    – Anonemous
    Commented Aug 8, 2019 at 2:10
  • $\begingroup$ You should review the definition of Turing-recognizable in Sipser's book. (In the 3rd edition I have here at hand it's Definition 3.5, p.170; see also the discussion in p. 169.). If $M$ accepts $w$, then it must halt in the accept state; if it loops, then it doesn't even halt. $\endgroup$
    – dkaeae
    Commented Aug 8, 2019 at 7:18
  • $\begingroup$ So, if $M$ does not halt on $w$, then $w$ does not belong to the language of $M$, right? $\endgroup$
    – Anonemous
    Commented Aug 8, 2019 at 7:27

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.