Is $T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$ recognizable?

Question

$$T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$$

I started with Rice's theorem (come up with an example where $|L(M)| = 2$) to see that $T$ was undecidable. Then I figured out $\bar{T}$ was unrecognizable, because $H =\{\langle M \rangle \mid M\text{ halts on the empty string} \}$ has a mapping-reduction to $T$, and $H$ is not co-recognizable, so $T$ is not co-recognizable.

Now I'm stuck. I tried mapping-reductions from $H$, $E = \{\langle M \rangle \mid M \text{ doesn't accept anything} \}$ and $F = \{ \langle M \rangle \mid L(M) \text{ is finite} \}$.

What's a good set to try and reduce from (or reduce to)? Am I right that $T$ is unrecognizable?

Answer 1

You can establish a reduction $\overline{H}\le_M T$ by mapping $\langle M\rangle\rightarrow \langle N\rangle$ where

N(x) =
   if x = 0, accept
   if M halts on the empty string
      if x = 1, accept

Now

• If $\langle M \rangle\in H$ then $L(N) = \{0, 1\}$ which implies $\langle N\rangle\notin T$
• If $\langle M \rangle\notin H$ then $L(N) = \{0\}$ which implies $\langle N\rangle\in T$

and since you already know $\overline{H}$ is not recognizable, $T$ must not be recognizable.