0
$\begingroup$

I'm trying to understand what's the difference between $S=\emptyset$ and $S=\{\emptyset\}$
The diffenition that I found for $L_S=\{\langle M\rangle\ | L(M)\in S \}$
I understood that $S=\emptyset$ and $S=RE$ are trivial and
$S=\emptyset \Rightarrow L_\emptyset=\emptyset\in R$
$S=RE \Rightarrow L_{RE}=\Sigma^*\in R$

But can't understand what's going with $S=\emptyset$ and $S=\{\emptyset\}$

Improve this question
$\endgroup$
1
$\begingroup$

Assume that all languages are over the alphabet $\Sigma$. What you have here is a bit of ambiguity in the meaning of $\emptyset$ (recall that the emptyset is defined w.r.t a universal set, and here $\emptyset$ is used w.r.t different universal sets). Indeed, $S = \{ \emptyset\}$ refers the set of languages containing only the empty language, that is, in this case, $\emptyset\subseteq \Sigma^*$. Also, $S = \emptyset$ refers to the empty set of languages, that is, in this case $\emptyset\subseteq 2^{\Sigma^*}$.

As you noted, if $S = \emptyset$, then $L_S = \{ \langle M\rangle: L(M)\in \emptyset\} = \emptyset \in \text{R}$. Now if $S = \{ \emptyset\}$, then $L_S = \{ \langle M\rangle: L(M)\in \{\emptyset\}\} = \{ \langle M\rangle: L(M) = \emptyset\} = E_{TM}$ which is known to be in $\text{coRE}\setminus \text{R}$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you, I need to think a bit about it, just what do you mean by $E_{TM}$? $\endgroup$ – ChaosPredictor Jan 21 at 19:27
  • 1
    $\begingroup$ The language of all TMs with empty language ($\{ \langle M\rangle: L(M)=\emptyset\}$) is know by the name $E_{TM}$ ($E$ stands form empty, and $TM$ stands for turing machine) $\endgroup$ – Bader Abu Radi Jan 21 at 19:33
  • $\begingroup$ Sometimes they call it $EMPTY_{TM}$. I wrote it in case you want read about it. $\endgroup$ – Bader Abu Radi Jan 21 at 19:36
  • $\begingroup$ I want to check that I understood it on the right way. $\{ \langle M\rangle: L(M)\in \emptyset\}$ stands for none of the languages of any TM will be accepted and because of it $M$ even don't need to be run on any input $x$, we can say straight away $L=\emptyset$. On the other hand $\{ \langle M\rangle: L(M) = \emptyset\}$ means that TM should be run on all the inputs and if it accept even one $x$, $M$ will be rejected $\endgroup$ – ChaosPredictor Jan 21 at 22:06
  • 1
    $\begingroup$ You got it right. To be more precise: the language $\{ \langle M\rangle: L(M) \in \emptyset \}$ is the emptyset because for every TM $M$ the condition $L(M)\in \emptyset$ is not satisfied (the condition always evaluates to false). So a TM that decides the language immediately rejects all inputs (without even reading them). The language $\{ \langle M\rangle: L(M) = \emptyset \}$ is the language of all machines that do not accept any input ( they either reject or do no halt, on every input) - so you're right, a machine that accepts at least one input is not in the language. $\endgroup$ – Bader Abu Radi Jan 21 at 22:28

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.