TransWikia.com

Proof: is the language $L_1={langle Mranglemidemptyset subseteq L(M)}$ (un)-decidable?

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

2 Answers

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP