# Finding two languages satisfying conditions

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

• 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$. – John L. Mar 27 '19 at 20:04
• Thank you, I'll try again! – Alan Mar 28 '19 at 8:30
• If you has figured out this problem, please write an answer (yes, you can answer your own question). – xskxzr Mar 28 '19 at 8:53
• Certainly, I will – Alan Mar 28 '19 at 8:55
• 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. – chi Mar 28 '19 at 12:30

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.

• thank you for your answer! – Alan Apr 3 '19 at 18:32