Let $$E_{TM} = \left \{ \langle M\rangle \mid L(M) = \emptyset \right\}$$

Prove that there are two languages $L_1, L_2$ such that

  1. $L_1, L_2 $ are infinite.
  2. $L_1 \cup L_2 = E_{TM}$
  3. $L_1 \cap L_2 = \emptyset$
  4. $L_1$ is decidable, $L_2$ is not recognizable.

I'm finding it really hard to find two languages that satisfy these conditions.

Especially the second condition, which two language unify to $E_{TM}$?

  • 4
    $\begingroup$ Hint 1, can you construct one $M$ such that $L(M)=\emptyset$? Hint 2, can you construct infinitely many such $M$? Hint 3, let $L_2=E_{TM}\setminus L_1$. $\endgroup$
    – John L.
    Mar 27, 2019 at 20:04
  • 3
    $\begingroup$ If you has figured out this problem, please write an answer (yes, you can answer your own question). $\endgroup$
    – xskxzr
    Mar 28, 2019 at 8:53
  • $\begingroup$ Certainly, I will $\endgroup$
    – Alan
    Mar 28, 2019 at 8:55
  • $\begingroup$ The padding lemma states that there is a total computable function that given any (encoding of) TM $M$, it returns a TM $N$ having a "longer" encoding than the one of $M$, where $L(M)=L(N)$. Essentially, the function adds a few redundant states to $M$ to make its encoding "longer". You could try to apply this function many times, iterating it. $\endgroup$
    – chi
    Mar 28, 2019 at 12:30
  • $\begingroup$ Hint: Another way to build $L_1$ without using the padding argument is using the set of accepting states $F$ ... what happens if $F = \emptyset$ ...? $\endgroup$
    – Vor
    Mar 29, 2019 at 14:18

1 Answer 1


A slight improvement:

$L_2 = E_{TM} \backslash L_1 $ (since we require that $L_1 \cap L_2 = \emptyset$).

$L_1$ must be a language of turing machines, i.e. $L_1 = \{\langle M\rangle \mid \dots\} $, so that $L_1 \cup L_2 = E_{TM}$.

So let's set $L_1 =$ $\{\langle M\rangle\mid C_0\text{ is a reject state}\}$.

The following holds:

  • $L_1 $ is infinite and decidable (easy to decide given $M$, what the configuration of the first state is).

  • $L_2 $ is infinite and unrecognizable.


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.