HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

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

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#93690, answer score: 14

Revisions (0)

No revisions yet.