1
$\begingroup$

Given 2 recursive - decidable languages $L_1$ and $L_2$ is the problem $L_1 \subset L_2$ solvable - decidable?

Since both $L_1$ and $L_2$ are recursive - decidable there exist Turing Machines say $M_1$ and $M_2$ that decide them.

Say that the problem stated is decidable then there exists a Turing Machine $M_3$ that given two deciders $M_i$ and $M_j$ responds with YES if $L(M_i) \subset L(M_j)$ otherwise it responds with NO.

If $M_3$ actually exists then there exists a Turing machine say $M_4$ that decides the Halting Problem and works in the following way:

  • Given $\langle M,w\rangle$ it constructs the description of a Turing Machine $M^*$ that given any input $x$ it erases $x$ from its tape, then writes $w$ on it and simulates $M$ on $w$. If $M$ halts on $w$ then $M^*$ responds with YES and $L(M^*) = Σ^*$ otherwise it loops infinitely as $M$ loops on $w$ and $L(M^*) = \emptyset$.

  • Then it constructs the description of a Turing Machine say $M^o$ such that $L(M^o) = Σ^*$

  • Next step is to feed $\langle M^*,M^o\rangle$ to $M_3$:

    • If $M_3$ responds with YES then $L(M^*) \subset L(M^o)$ so $M$ does not halt on $w$ and $M_4$ responds with NO.

    • If $M_3$ responds with NO then $L(M^*) \not\subset L(M^o)$ so $M$ halts on $w$ and $M_4$ responds with YES.

This is how I approached the problem but my concern is that the way $M^*$ works does not make it a decider as it may loop forever. Is there any way that I can modify my approach and make it work?

$\endgroup$
2
  • $\begingroup$ The exercise "given $2$ decidable languages $L_1$ and $L_2$ is the problem $L_1 \subset L_2$ decidable?" could be interpreted as "given $2$ decidable language $L_1$ and $L_2$, is there an algorithm which responds with YES if $L_1\subset L_2$ and which responds with NO if $L_1\not\subset L_2$?". The answer is true, since either the algorithm that says YES or the algorithm that says NO satisfies the requirement. Similarly, the answer to "given any number $n$, is there a number greater than $n$?" is YES, although the answer to "is there a number which is greater than any given number?" is NO. $\endgroup$
    – John L.
    Commented Jun 4, 2023 at 20:32
  • $\begingroup$ On the other hand, the exercise can be interpreted as "is the language $\{\langle M_1, M_2\rangle\mid M_1, M_2 \text{ are deciders}, L(M_1)\subset L(M_2)\}$ decidable?". This interpretation presents The problem this post and my answer try to solve. $\endgroup$
    – John L.
    Commented Jun 4, 2023 at 20:32

1 Answer 1

1
$\begingroup$

The following is a modification of your approach that works.

The idea is to construct language $L_1$ so that it is not empty if and only if the given $M$ halts on the given $w$. Then use $M_3$ to check whether $L_1$ is empty.

As in the question, a Turing machine responds with YES or NO means it accepts or rejects respectively. A language is decidable when a decider for it is given. "$\subset$" means "is a proper subset of".


Let $D$ be a Turing machine that decides given decidable language $L_1$ and $L_2$ whether $L_1\subset L_2$.

Given $\langle M,w\rangle$, Turing machine $M_6$ will do the following.

  1. It constructs Turing machine $H$ which on input $x$:

    1. Counts the number of symbols in $x$. Let it be $n$.
    2. Simulates $M$ on input $w$ up to $n$ steps. If the simulation halts within $n$ steps, accepts. Otherwise, rejects.

    Note that $H$ is a decider. $L(H)$ is empty iff $M$ does not halt on input $w$.

  2. It feeds $\langle L(H), \{\epsilon\}\rangle$ to $D$. Note that $\{\epsilon\}$ is a decidable language.

    • If $D$ responds with YES, then $L(H) \subset L(E)$, which means $L(H)$ is empty, which means $M$ does not halt on $w$. It responds with NO.
    • If $D$ responds with NO, then $L(H) \not\subset L(E)$, which means $L(H)$ is not empty, which means $M$ halts on $w$. It responds with YES.

$M_6$ is a decider for the halting problem.


The approach above uses $D$ only to decide whether a given decidable language is empty or not. Hence, we have proved, in fact, it is undecidable whether a given decidable language is empty or not.


Here is an exercise, which is another stronger form of the exercise in the question.

Is it decidable whether $\{a^n\mid n\in\Bbb N\}\subset L_2$ where $L_2$ is a decidable language $L_2$ over an alphabet that has $a$ and $b$?

$\endgroup$
7
  • $\begingroup$ What concerns me is the description of both $M^o$ and $M^h$ as they might loop forever. I am new to TM but as far as I know a decider must respond with YES or NO. An idea is to restate the hypothesis: Say that the problem is decidable then there exists a Turing Machine $M_3$ that given two Turing Machines $M_i$ and $M_j$ whose languages are decidable responds with YES if $L(M_i) \subset L(M_j)$ otherwise it responds with NO. Another idea is to try to prove that the $L(M_i) \subseteq L(M_j)$ is not provable since proper subset requires to prove that and the fact that $|L(M_i)| < |L(M_j)|$ $\endgroup$ Commented Jun 3, 2023 at 9:49
  • $\begingroup$ @RookieCookie Thanks for pointing out my typo. I should have written "rejects" instead of "loops forever". $\endgroup$
    – John L.
    Commented Jun 3, 2023 at 10:00
  • $\begingroup$ Would you mind providing some feedback on the other 2 approaches? Furthermore your solution is so elegant but I want to make sure I understand correctly. The language of $M^o$ is always $Σ^* \setminus \{ε\}$ and the language of $M^h$ is either the ${ε}$ or the strings whose length $|x| \geq 1 $ if $M$ does not halt on $w$, right? $\endgroup$ Commented Jun 3, 2023 at 10:26
  • $\begingroup$ It looks you have understood my answer correctly. $\endgroup$
    – John L.
    Commented Jun 3, 2023 at 14:17
  • 1
    $\begingroup$ One of the other 2 approaches of yours led me to a slightly-simpler solution. I will update answer to prove that it is undecidable whether a decidable language accepts at least one string, i.e., given a decider $M$, is $|L(M)|=0$. $\endgroup$
    – John L.
    Commented Jun 3, 2023 at 14:22

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.