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$

1 Answer 1

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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.