patternModerate
Why must a Turing Machine that Repeats the Same Configuration Twice be in an Infinite Loop?
Viewed 0 times
whythesametwicemustinfinitelooprepeatsthatmachine
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#93690, answer score: 14
Revisions (0)
No revisions yet.