# How to detect infinite loop exist in linear bounded automata (LBA)?

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?

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.
• 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? – Anonemous Aug 7 at 15:05
• "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. – dkaeae Aug 7 at 15:56
• If $M$ goes to an infinite loop on $w$, does it mean that : $w$ does not belong to the language which $M$ recognize? – Anonemous Aug 8 at 2:10
• 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. – dkaeae Aug 8 at 7:18
• So, if $M$ does not halt on $w$, then $w$ does not belong to the language of $M$, right? – Anonemous Aug 8 at 7:27