Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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:
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!
A Turing machine which computes all of the decimal places of π (or any other non-terminating fraction, in any base) never halts, and can be made to write on each cell only a finite number of times. Of course, the fact that there is no transition to a halting state would be a dead giveaway, but it is at least a natural example.
A more interesting (but also ambiguous) case would be a Turing machine which iteratively computes the Collatz function on its input, $$ f(n) = \begin{cases} 3n+1 , & \text{if $n$ is odd}; \\ n/2, & \text{if $n$ is even}, \end{cases} $$ terminating if and only if it obtains the integer 1. The famous Collatz conjecture is that for any input, this procedure eventually halts. But it is not known whether this is the case. It can fail in two different ways, in principle: either it can find a sequence of integers which loops around (corresponding to the existence of an integer n such that $f \circ f \circ \cdots f(n) = n$ for some number of compositions, where n ≠ 1); or it could be that there are chains of integers n, f(n), f(f(n)), ... which asymptotically diverge to infinity. If any sequences of the latter sort exist, this would imply that the Turing machine I've described above would be non-repeating, as the tape would be continually changed to larger and larger numbers.
pi. A TM could halt whenever the square of any digit of pi equals exactly 7.
$\endgroup$
Consider any non-halting Turing machine that never moves the read/write head to the left.
If this were true, then the halting problem would be decidable. You would just record each (tape, state) pair seen when executing the Turing machine, and the machine would either halt (in which case it obviously halts), or you see a pair that you've seen before, in which case the machine does not halt.
Since the halting problem is undecidable, this cannot be true. (See other examples for counter examples.)
x^2wherexcycles between-100and100and the cycling is done with a modulo and halt when the result is negative. It could computex%2where x ranges from zero to positive infinity and stop when the result equals 2. In assembly language do/while/for loops all come down do having a conditional jump, but cond jump alone means little. $\endgroup$