Question

I came across following problem to finding whether the following language is decidable or semi-decidable or not even a semi-decidable.

$L: \{\langle M\rangle: M\space is\space a\space TM\space and\space |L(M)| \ge3\}$

Now thinking intuitively I conjectured that this language is semi-decidable. We can say yes when the input does belong to $L$. But, we can not say no when the input does not belong to $L$.

Now, I formulated following reduction from complement of halting problem $\overline{HP}$ which is not semi-decidable (non $RE$).

$\overline{HP}: \{\langle M, w\rangle : M\space is\space TM\space and\space it\space does\space not\space halt\space on\space string\space w.\}$

$\tau(\langle M,x\rangle) = \langle M'\rangle$.

$M'$ on input $w$ works as follows. It erases w, puts $M$ and $x$ on its tape, and runs $M$ on $x$ and accepts if $M$ doesn't halt on x. Otherwise it rejects.


Proof of validity of reduction:

$\langle M,x\rangle \in \overline{HP} \implies M\space does\space not\space halt\space on\space x \implies M'\space accepts\space all\space inputs\space \implies|L(M')| \ge 3\implies M' \in L$

$\langle M,x\rangle \notin \overline{HP} \implies M\space does\space halt\space on\space x \implies M'\space rejects\space all\space inputs\space \implies|L(M')| < 3\implies M' \notin L$


According to above reduction $\overline{HP}$ should be recursively enumerable$(RE)$ which it is not. So, $L$ should not be $RE$ but it indeed is $RE$. So, my reduction must be flawed.

Please point out where I messed up.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top