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>$:"

  1. ...

How can I prove that $N$ is a decider for $L_1$?

  • 3
    $\begingroup$ 1. output "true". $\endgroup$ Jul 19 '20 at 0:22

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


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.