# Is the problem of Proper Subset of decidable languages decidable?

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?

• 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. Jun 4, 2023 at 20:32
• 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. Jun 4, 2023 at 20:32

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

• 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)|$ Jun 3, 2023 at 9:49
• @RookieCookie Thanks for pointing out my typo. I should have written "rejects" instead of "loops forever". Jun 3, 2023 at 10:00
• 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? Jun 3, 2023 at 10:26
• It looks you have understood my answer correctly. Jun 3, 2023 at 14:17
• 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$. Jun 3, 2023 at 14:22