What is difference between following two problems, their decidability and recognizability status:
- Given Turing Machine TM “accepts” given string w.
- 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?