Does a never-halting machine always loop?

Problem Detail: 

A Turing machine that returns to a previously encountered state with its read/write head on the same cell of the exact same tape will be caught in a loop. Such a machine doesn't halt.

Can someone give an example of a never-halting machine that doesn't loop?

Asked By : hollow7

Answered By : templatetypedef

Consider the TM that always moves the tape head to the right and prints a special non-blank tape symbol at each step. This means that the TM never halts, since it always moves to the right, and never repeats a state, since after k steps the tape head is over the kth cell of the machine. Consequently, each configuration of the machine is different from all others, and the machine always loops.

We could also nonconstructively show the existence of such machines. Assume for contradiction that every TM that never halts eventually loops. This means that if you start a TM $M$ on a string $w$, one of the following will eventually happen:

1. $M$ halts, or
2. $M$ repeats a configuration.

In this case, the halting problem would be decidable as follows. Given a TM $M$ and string $w$, simulate $M$ on $w$, at each point writing out the contents of the tape, current state, and current tape position. If this configuration is a duplicate, output "does not halt." Otherwise, if $M$ halts on $w$, output "halts." Since one of these is guaranteed to happen eventually, this process always terminates, so we would have an algorithm for the halting problem, which we know does not exist.

Hope this helps!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2728