1
$\begingroup$

I need to show that the following language, L = {$\langle M \rangle$ | The set of words which M halts on is decidable}, is not recursively enumerable. In the instructions they advise thinking of a reduction that is similar to the one used in the proof for Rice's Theorem in Sipser's 3rd edition (page 243). I couldn't think of a proper proof by myself. I assume L $\notin RE\cup CO-RE$ so there's no point in trying to prove $\bar{L}$ is in RE to show L is not in RE. Can anyone help?

$\endgroup$
1
$\begingroup$

Here is a reduction from coHALT (given a Turing machine, determine whether it doesn't halt on the empty input) to $L$. Given a Turing machine $M$, construct a new Turing machine $M'$ which acts as follows:

  • Run $M$ on the empty input.
  • If $M$ halts, interpret the input as a Turing machine and run in on the empty input.

If $M$ doesn't halt on the empty input, then the set of words on which $M'$ halts is the empty set, which is decidable, and so $M' \in L$. If $M$ does halt on the empty input, then the set of inputs on which $M'$ halts is HALT, which is not decidable, and so $M' \notin L$.

| cite | improve this answer | |
$\endgroup$

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.