1
$\begingroup$

$$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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.