0
$\begingroup$

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

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

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ thank you for your answer! $\endgroup$ – Alan Apr 3 '19 at 18:32

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.