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
    $\begingroup$ Yes, we are in the same configuration, and we will loop forever moving right then left. $\endgroup$
    – chi
    Jun 30, 2018 at 15:44

3 Answers 3


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.

  • $\begingroup$ Is it both ways? If a TM doesn't repeat the same configuration twice, is it necessarily stops? $\endgroup$
    – Avishay28
    May 22, 2020 at 16:38
  • 1
    $\begingroup$ No. Counterexample: TM which only flips a current bit and always moves right and does not have a final state. If the initial tape is [0]000..., then it acts like 1[0]00..., 11[0]0..., 111[0]..., and so on. $\endgroup$
    – nekketsuuu
    May 23, 2020 at 1:19

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