0
$\begingroup$

The language $L = \{ \text{M} \mid \text{M is a TM and the set of words w such that M halts on w is decidable} \}$ is given.

I need to prove that $L$ is NOT Turing recognizable. I've got a hint: it should be similar to prove to the Rice Theorem, using a reduction. However, this hint isn't very helpful to me.

$\endgroup$
2
  • 3
    $\begingroup$ Can you add a bit more details to the questions? Is there a specific issue that you're having in trying to complete a proof? Probably nobody will be very happy to solve your exercises... $\endgroup$ – Steven Nov 6 '19 at 16:02
  • $\begingroup$ currently, I am unable to find/think of any solution .... the only hint i've got is that the reduction should be something like rice proof. $\endgroup$ – Roy Padina Nov 7 '19 at 17:22
0
$\begingroup$

Given a machine $A$, construct a machine $M$ which on input $x$, acts as follows: run $A$ on the empty input, and if it ever halts, run the Turing machine encoded by $x$ on the empty input.

If $A$ halts on the empty input then the language $M$ recognizes is the halting language, while if $A$ doesn't halt on the empty input then the language $M$ recognizes is the empty language.

$\endgroup$
1
  • $\begingroup$ i don't see how this solves or proves the question ... $\endgroup$ – Roy Padina Nov 9 '19 at 14:06

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.