Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I want to show that $L_1 = \{\langle M\rangle \mid \emptyset \subseteq L(M)\}$ is decidable/undecidable - without rice theorem (just for the case that I can apply it).
Every language contain the $\emptyset$ as a subset. So my guess is that the language is decidable.
Therefore, let us assume that $L_1$ is decidable. Lets say that $N$ is the TM which decides $L_1$.
N = "with input $<M>$:"
How can I prove that $N$ is a decider for $L_1$?
Your language $L_1 = \{\langle M\rangle \mid \emptyset \subseteq L(M)\}$ is trivially decidable by a Turing machine $T$ that just checks whether $\langle M \rangle$ is a valid description of a Turing Machine. If it is, $T$ accepts. Otherwise $T$ rejects.
Notice that, for any Turing machine $M$, $L(M)$ is a set (by definition) and therefore $\emptyset \subseteq L(M)$ is always true.
∅ Is the empty set symbol, not a valid string. Only valid strings may be contained in a language.
If you meant that L(M) = ∅ - It is not decidable: ETM Undecidability
If you meant that L(M) contains the empty string - it is also not decidable. Suppose D is a TM that decides it. Let F be a function that, given (M,w), Creates a Turing machine M' that ignores its input and emulates w on M and accepts if M accepts w. Now if M accepts w then M' accepts anything, including the empty string, and accepts nothing (including the empty string) otherwise. You would then be able to run M' on D to decide if M accepts w, a contradiction.
If you did mean your question literally, see this - https://math.stackexchange.com/questions/1464707/is-the-empty-set-in-every-language
