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
    May 31 '15 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$ May 31 '15 at 15:30
  • $\begingroup$ @Elimination does a TM that always returns TRUE decide the halting problem? $\endgroup$
    – Ran G.
    May 31 '15 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
    May 31 '15 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
    May 31 '15 at 20:04

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$ Jun 4 '15 at 1:40

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.