0
$\begingroup$

First of all, obviously there is a flaw in my logic and I just want to know what it is. So here is my idea: Given a TM M and an input string ω, simulate M on ω on another TM S. For every change of state on M record the TM's configuration. On all iterations compare the new configuration to every other recorded configuration. If there was a match, then the TM is surely not going to halt, at which point we stop the computation and accept or reject accordingly.

$\endgroup$
3
  • $\begingroup$ What happens if I give it a machine with one state that always writes $1$ to the current cell, moves the head right, and stays in the single state? $\endgroup$
    – Dan Doel
    Aug 8, 2023 at 16:44
  • 2
    $\begingroup$ Your question is not explicit, so I assume it is "why doesn't this an algorithm solve the halting problem" (or something similar), to which the answer would be: your algorithm might never end. $\endgroup$
    – jthulhu
    Aug 8, 2023 at 16:45
  • 4
    $\begingroup$ A machine may run forever without looping. $\endgroup$ Aug 9, 2023 at 18:32

3 Answers 3

6
$\begingroup$

Detecting whether a machine $M$ is looping (meaning that it has reached the same configuration (not only of its internal state but also of the tape) twice), is indeed as "easy" as recording the configurations as we simulate $M$ and checking whether the current one was already seen.

This method is of course incapable of deciding whether a machine will eventually loop, but rather it detects looping only once it happens, which means that such procedure never tells you the machine won't ever loop; only that it hasn't looped yet. Note that this is same thing that occurs with the halting problem; it's easy to tell that a machine has halted; the hard part is deciding whether a machine will eventually halt or not.

It is worth noting as well that even though looping $\implies$ not halting, it's not true that not halting $\implies$ looping; for instance a Turing Machine listing all prime numbers on its tape will never halt and yet also never loop...

$\endgroup$
4
$\begingroup$

This method will not detect

n:= 0;
while true do
  n:= n+1

so it is not universal.

$\endgroup$
0
$\begingroup$

There are two problems: One, a Turing machine doesn't necessarily halt. That's because it has unlimited amounts of state. Your PC with 128 GB of RAM = 1 Terabit only has $2^{1024 \cdot 1024 \cdot 1024 \cdot 1024}$ different states, so it has to reach the same state again.

Two, if you simulate the Turing machine and you havent detected the same state after a year or after a trillion years then you don't know if you will eventually find a repeating state or not.

$\endgroup$
1
  • $\begingroup$ I guess that the OP's argument is "the machine will return to the same state sooner or later". There lies the flaw. $\endgroup$
    – user16034
    Aug 17, 2023 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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