7
$\begingroup$

I have seen the following statement, and I don't quite understand the reasoning behind it:

If a Turing machine repeats the same configuration twice, it must be in an infinite loop.

I thought that a $TM$ can be in a state $q_1$, with the tape on the left 000 and on the right 111. Let's say it moves right and then left, staying in the same state; aren't we in the same configuration?

$\endgroup$
  • 7
    $\begingroup$ Yes, we are in the same configuration, and we will loop forever moving right then left. $\endgroup$ – chi Jun 30 '18 at 15:44
13
$\begingroup$

This is because the transition function $\delta$ of a TM is deterministic. If the configuration is the same, then the arguments of $\delta$ are also the same, resulting in an infinite loop. Formally, this can be proved like @gnasher729 does.

Let's consider your example. If your $TM$ moves like the following,

$$ (q_1, \dots00[0]111\dots) \xrightarrow{q_1, \text{right}} (q_1, \dots000[1]11\dots) \xrightarrow{q_1, \text{left}} (q_1, \dots00[0]111\dots) $$

then the last step equals the first one, which means an infinite loop.

$\endgroup$
7
$\begingroup$

If your Turing Machine is in some state X after n steps, and again in the exact same state X after n+m steps, then it will repeat exactly the same actions from step n+m that it executed at step n, and after step n+2m it will be in state X again, same after step n+3m, n+4m and so on. So you are in an infinite loop.

Your example was a case where you reached the same state again after two steps, so m=2.

$\endgroup$
4
$\begingroup$

A version of @nekketsuu 's answer with no symbols, arrows or Greek:

A machine's configuration determines what it does next (and inductively, determines its entire future). Thus if what happens after a certain configuration is that you reach it again with some more steps, this will go on happening again and again to no end.

This is true for any deterministic machine: Turning machine, (Deterministic) Finite Automaton, (Deteriministic) Stack Automaton etc.

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