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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Dec 1, 2018 at 2:53
-
$\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$ Dec 2, 2018 at 14:27
-