# Why must a Turing Machine that Repeats the Same Configuration Twice be in an Infinite Loop?

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?

• Yes, we are in the same configuration, and we will loop forever moving right then left.
– chi
Jun 30, 2018 at 15:44

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, \dots00111\dots) \xrightarrow{q_1, \text{right}} (q_1, \dots00011\dots) \xrightarrow{q_1, \text{left}} (q_1, \dots00111\dots)$$

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

• Is it both ways? If a TM doesn't repeat the same configuration twice, is it necessarily stops? May 22, 2020 at 16:38
• 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 000..., then it acts like 100..., 110..., 111..., and so on. 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.