1
$\begingroup$

I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, which consists of exactly five strings. Because $S$ is a property of the accepted language (there exists a TM that recognizes $L$), hypothesis of Rice Theorem applies, and because the set is not empty nor it is the set of all computable functions (equally, $S$ is non-trivial), it is undecidable. Yet, is it semidecidable? I was kinda attempting to prove that the complement of $S$ is semidecidable (thus guessing that $S$ is not semidecidable), but couldn't come up with anything useful.

$\endgroup$
1
$\begingroup$

We know that the halting problem is semidecidable, but the non-halting problem is not semidecidable (since otherwise the halting problem would be decidable). Hence one way to show that a language is not semidecidable is by reduction from the non-halting problem.

Let $\langle M,x \rangle$ be an input the the non-halting problem. We construct a new Turing machine $M'$ which on inputs $1,2,3,4,5$ halts, on input $6$ simulates $M$ on $x$, and on all other inputs never halts. Then $M' \in S$ iff $M$ doesn't halt on $x$.

We can also construct another Turing machine $M''$ which on inputs $1,2,3,4$ halts, on input $5$ simulates $M$ on $x$, and on all other inputs never halts. Then $M'' \notin S$ iff $M$ doesn't halt on $x$.

These reductions show that neither $S$ nor its complement are semidecidable.

$\endgroup$
  • $\begingroup$ Thanks, and, just out of curiosity, how would the reasoning change if the set were $S = \{ M \mid |L(M)| \geq 5 \}$ ? If there are more than 5 strings sooner or later I'll find them, otherwise it just doesn't halt, so it should be semidecidable, correct? $\endgroup$ – Antonio Frighetto Dec 2 '18 at 14:27
  • $\begingroup$ Right, this one is semidecidable. $\endgroup$ – Yuval Filmus Dec 2 '18 at 17:16

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.