Let $L = \{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\}$. I'm trying to determine whether $L$ is decidable.

I don't think it's even recognizable, but I'm not sure. Regardless, I think I can show it's undecidable. Suppose $L$ is decidable by machine $D$. Then we can construct machine $S$ that decides the accepting problem, i.e. $\mathrm{ACC} = \{(M,w): M\text{ accepts }w\}$, which is undecidable.

For $S$ on input $(M,w)$, construct machine $M'$ with input $x$ such that if $x \neq 1100$, then loop, and if $x = 1100$, run $M$ on $w$. If $M$ accepts, then $M'$ halts. Next, run machine $D$ on $M'$. If $M'$ halts, then $D$ accepts. Otherwise, $D$ rejects.

So, if $M$ accepts $w$, then $x=1100$ and $M'$ halts, so $D$ accepts. On the other hand, if $M$ does not accept $w$, then $M'$ loops (and does not accept anything), and $D$ rejects. But then $D$ decides $\mathrm{ACC}$, which is undecidable. Hence, $L$ is undecidable.

Am I on the right track?

  • 1
    $\begingroup$ Your proof looks fine. We don't normally do "check my answer" type questions here because they're usually only useful to the person who asked them. In this case, though, it's useful context for your secondary question about unrecognizability, since it shows that you're pretty close to the answer for that, too. $\endgroup$ – David Richerby Dec 9 '18 at 17:43

To show that $L$ is not recognizable, you can reduce the complement of the halting problem to it. $\overline{\mathrm{HALT}}$ is not recognizable because, if a language and its complement are both recognizable, then they're both decidable, and we know that $\mathrm{HALT}$ isn't recursive.

Given a Turing machine $M$ and input $w$, you want to accept iff $M(w)$ loops. So construct the machine $M'$ which halts if its input is $1100$ and simulates $M(w)$, otherwise. If $M'\in L$, then $M'$ cannot halt on $0011$ or $1000$,* which means that $M(w)$ doesn't halt.

* It seems there's a typo in the question, which mentions $0011$ twice. Obviously, this doesn't make any real difference.

| cite | improve this answer | |

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.