21
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Just a note: the tape can also be different: a sufficient (but not necessary) condition for an endless loop when the TM enters the same cell at step $t_1$ and at step $t_2 > t_1$ in the same state, is that at step $t_2$ the portion of the tape visited by the head between step $t_1$ and step $t_2$ is equal to the corresponding portion just before entering $t_1$. $\endgroup$ – Vor Jul 13 '12 at 15:51
  • 4
    $\begingroup$ If a TM had to loop in order to fail to halt, you'd be able to fairly easily solve the halting problem for TMs: remember all previous configurations, and at each step, see if you're in a configuration you've seen before, and if so, you know the thing doesn't halt (otherwise, since we assume that it must loop in order to run forever, it won't run forever, i.e., it will stop, in which case we'll eventually know about it). $\endgroup$ – Patrick87 Jul 13 '12 at 16:59
  • $\begingroup$ Inspired by @Niel de Beaudrap answer: a turing machine could compute the oeis.org/A014445 sequence and stop when it gets an odd number. It could compute oeis.org/A016742 as a running sum and halt when the number is odd. It could compute x^2 where x cycles between -100 and 100 and the cycling is done with a modulo and halt when the result is negative. It could compute x%2 where 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$ – Leonid Jul 16 '12 at 21:15
  • $\begingroup$ The question's assumption is only true for deterministic machines. $\endgroup$ – Raphael Jul 18 '12 at 10:04
15
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Hah, beat you to that edit. See my comment on the question. I like this way of explaining why not all non-halting TM's must loop... it builds intuition. $\endgroup$ – Patrick87 Jul 13 '12 at 17:33
  • $\begingroup$ @Patrick87- Sorry, I didn't notice the comment. I thought of the addendum on my commute and sat down to enter it as soon as I got back. $\endgroup$ – templatetypedef Jul 13 '12 at 19:30
  • $\begingroup$ No problem, man... I'm glad that you added it, since I think it's a good way of explaining it. I only added it as a comment, and not as an answer, since you beat me to that. :D $\endgroup$ – Patrick87 Jul 13 '12 at 20:53
  • $\begingroup$ Actually, in terms of the halting problem such that go back and change the tape ad infinitum seem to be the "real problem". Those void-walkers you can detect. $\endgroup$ – Raphael Jul 18 '12 at 10:06
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like playing with the digits of pi. A TM could halt whenever the square of any digit of pi equals exactly 7. $\endgroup$ – Leonid Jul 16 '12 at 21:18
  • $\begingroup$ @Leonid: You could certainly consider a Turing machine which accepts some input, and halts on a condition determined by that input. You could even make the specification of the conditions under which it halts part of the input. And you could provide an input, as you describe, setting a constraint which is never satisfied. $\endgroup$ – Niel de Beaudrap Jul 17 '12 at 17:15
10
$\begingroup$

Consider any non-halting Turing machine that never moves the read/write head to the left.

$\endgroup$
  • $\begingroup$ Some of them still loop. </nitpicking> $\endgroup$ – Raphael Jul 18 '12 at 10:08
5
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ What does this answer add to templatetypedef's answer? $\endgroup$ – Raphael Jul 18 '12 at 10:08
  • $\begingroup$ I guess it doesn't. Sorry, I somehow missed that answer when I wrote mine. $\endgroup$ – RecursivelyIronic Aug 13 '12 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.