Computer Science Asked by Schleudergang on October 21, 2021
I want to show that $L_1 = {langle Mrangle 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 Mrangle 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.
Answered by Steven on October 21, 2021
∅ 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
Answered by Guy on October 21, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP