What is difference between following two problems, their decidability and recognizability status:

  1. Given Turing Machine TM "accepts" given string w.
  2. Given Turing Machine TM "halts on" given string w.

I feel first problem means,

whether given TM "halts by accepting" given string

and second problem means,

whether given TM "halts by accepting or rejecting" given string

If I am correct, then is their any difference between their decidability and recognizability status?

For 2nd language, if TM accepts w, then it will eventually halt, but if it does not accept w, then it may keep looping infinitely. Hence its undecidable but recognizable.

I believe 1st problem is subset of 2nd problem and hence it is definitely recognizable. But I am confused about decidability of 1st problem, since it eliminates "halt by rejecting" criteria from 2nd problem. Does that make it decidable?


Your intuition is correct in defining the two problems. In fact accepting also means halting but halting does not necessarily mean accepting (it could also reject). Remember that when a Turing Machine is run on an input it can do three things: Accept, Reject, Loop Forever. In the first two cases the machine stops, in the third obviously not.

As for decidability, note that both problems are the Halting Problem because the first case implies a halting, even if it excludes the fact that the arrest is due to reject, therefore they are both undecidable.

| cite | improve this answer | |

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.