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?

  • 7
    Yes, we are in the same configuration, and we will loop forever moving right then left. – chi Jun 30 at 15:44
up vote 13 down vote accepted

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.

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.

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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