Let us say there is a Turing Machine $M$ and a string $x$. So now I want to know if $M$ accepts or rejects the string or loops on it. So, I feed the string to $M$. So, if $M$ is accept or reject the string it would halt after a finite time and I would get my answer. But how do I know if the machine loops on the string or not.

One possible way is to see if a configuration repeats itself. However, the machine has no way of knowing if the configuration has occurred before because it cannot store them . So, we would never get an answer. So, how will I be able to tell whether or not $x$ is accpted or rejected or looped upon by $M$.

  • 1
    $\begingroup$ This problem refers to the Halting problem . you can never make sure if the machine loops forever on a specific input String. You can only recognize this language , you cannot decide this language. $\endgroup$ – Shubham Singh rawat Nov 13 '16 at 15:25
  • $\begingroup$ Why do you think that your loop-testing TM couldn't store the configurations of the machine being tested? Conceptually, at least, you could store them on another tape. $\endgroup$ – Rick Decker Nov 13 '16 at 21:41

Halting problem is generally unsolvable. The states don't have to repeat. But if you know that they will, see cycle detection.


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.