I am preparing for an exam and I came across this question in one of the tests.

Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)

The solution given says the statement its False.

But I think the statement is True. Halting problem in itself is undecidable. We can't determine whether the Turing Machine will halt or not.

The test series has a history of wrong answers that's why I am seeking an explanation even if I am wrong.

Edit: I was looking at the answers and I have trouble understanding the explanations. I know that 'By definition, recursive languages are decideable by Turing machines.' I will tell you how I breakdown the question. I am given a TM and told that this TM recognizes a recursive language. How do I know that the TM will halt?

  • $\begingroup$ Seems question is not well formulated by the exam. $\endgroup$ – Mr. Sigma. Dec 10 '18 at 15:39
  • $\begingroup$ I agree with you. $\endgroup$ – imagine5am Dec 10 '18 at 15:42
  • $\begingroup$ "I am given a TM and told that this TM recognizes a recursive language." This is redundant. TMs recognize recursive languages by definition. $\endgroup$ – ubadub Dec 10 '18 at 16:36
  • $\begingroup$ But the TM may fall in infinite loop. Can't it? $\endgroup$ – imagine5am Dec 10 '18 at 16:42
  • $\begingroup$ @imagine5am no, the whole point of a recursive language- it's very definition- is that the TM won't. Recursive languages are definitionally decidable. $\endgroup$ – ubadub Dec 10 '18 at 16:57

By definition, recursive languages are decideable by Turing machines. Thus for recursive languages the TM will always halt.

  • $\begingroup$ Please check out the edit. $\endgroup$ – imagine5am Dec 10 '18 at 15:21

If the task is to determine whether a given machine $M$ halts, when you already know that $M$s language is decidable then the answer is always "yes" because every TM that decides a language halts on every input (by definition of "to decide"). Hence, the halting problem on these kind of TMs is decidable.

However, if you want to determine whether the language $$A = \{\langle M \rangle \mid L(M) \text{ is decidable}\}$$ you can find an easy reduction that shows that $A$ is undecidable. I do not think this is the task but it was my first thought reading this question, so maybe it is still useful.

  • $\begingroup$ Please check out the edit in question. $\endgroup$ – imagine5am Dec 10 '18 at 15:20

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.