Consider the following language:

$$L = \{ \langle M \rangle \ |\ M \text { is a TM that decides the halting problem} \}$$

determine whether or not the language is in $R$.

Now, from my understanding an $\langle M \rangle \in L$ doesn't necessarily returns the right answer but rather halts for every $\langle P, x \rangle$ where $p$ is a program (=TM) and $x$ is an input for the program.

I am guessing the language isn't decidable and can be showed as such by some reduction, but couldn't think of something useful.

I'll be glad for help.

  • $\begingroup$ Hint: what do you know of the halting problem? $\endgroup$
    – Shaull
    Commented May 31, 2015 at 15:26
  • $\begingroup$ There's is no a TM that halts for every $\langle p,x\rangle$. At first I thought that $L = \emptyset$ but, consider a TM that always returns TRUE. Isn't this TM in $L$? $\endgroup$ Commented May 31, 2015 at 15:30
  • $\begingroup$ @Elimination does a TM that always returns TRUE decide the halting problem? $\endgroup$
    – Ran G.
    Commented May 31, 2015 at 15:33
  • $\begingroup$ A TM in L needs to decide the halting problem, not just decide something. Thus, a TM that always returns TRUE is not in L, and you're right - $L=\emptyset$. $\endgroup$
    – Shaull
    Commented May 31, 2015 at 15:36
  • 1
    $\begingroup$ Semantic Capulets against computability Montague. An old story. Everything you want to know about Computer Science is in Romeo and Juliet. :) - - - We just get what the students get, for a good part. And students do get a lot of unpalatable stuff. $\endgroup$
    – babou
    Commented May 31, 2015 at 20:04

1 Answer 1


comments summary:

The language $L$ is decidable.


$L$ is in fact empty! It contains all the machines that decide the halting problem. But, the halting problem is undecidable => there are no machines that decide it.

  • $\begingroup$ Which responds to @Andrej's comment to the OP. Nice. $\endgroup$ Commented Jun 4, 2015 at 1:40

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.