1
$\begingroup$

Are languages whose sets are empty recursively enumerable or recursive? For example, consider the language $L$ $\subseteq$ {0,1}*:

$L$ = { $w$ | $w$ consists of only 0's} $\cap$ { $w$ | $w$ consists of only 1's }

I believe this language creates an empty set. There are many different ways to design a Turing Machine that decides that whether word $w$ is in $L$. In that sense, $L$ seems recursive. Further, there are many different machines that can return the empty set. Any of these them would effectively "enumerate" the members of L, even though there are none.

My gut tells me to reject these conclusions. Could anyone steer me in the right direction? Any guidance would be much appreciated.

$\endgroup$
1
  • 2
    $\begingroup$ Note that the language is the set of strings, not the description. There is only one empty language. $\endgroup$ Nov 17, 2017 at 22:33

2 Answers 2

2
$\begingroup$

The empty language is recursive. The TM accepting this language just returns $0$/REJECT on any input. Similarly, the language $\Sigma^*$ is also recursive. Just return $1$/ACCEPT on any input.

Basically, it does not matter how a language is defined. What makes them recursive/RE is the fact that we can effectively decide its membership. For a recursive language $L$ there is a TM that always accepts $x$ if $x \in L$ and rejects $x$ if $x \notin L$. For a recursively enumerable language $L$ there is a TM that always accepts $x$ if $x \in L$.

$\endgroup$
1
  • $\begingroup$ Ah, I see. I had a feeling that was it, but I just couldn't pull the trigger without a second opinion. Thank you! $\endgroup$
    – TWal
    Nov 17, 2017 at 19:42
-5
$\begingroup$

I strongly believe the answer from fade2black is wrong. The empty language is not recursive, in fact it is not even recursive enumerable. The question you have to ask yourself is given any encoding of a turing machine M, can we determine if its language is the empty language. The way you can formally prove this would be by showing that the complement of the empty language is recursive enumerable and then it follows directly, that the empty language is neither recursive (otherwise the complement must be recursive as well) nor recursive enumerable (if a Language L and its complement are both recursive enumerable you can proof by contradiction that L is recursive).

$\endgroup$
2
  • 2
    $\begingroup$ You are confusing things. The empty set is $\emptyset$. It is recursive: a corresponding Turing Machine would be a Turing Machine that immediately rejects. What you are talking about is $L =\{\langle M \rangle \mid L(M) = \emptyset\}$. Since there exist Turing Machine accepting no words, this language is not empty. $\endgroup$
    – Nathaniel
    Dec 11, 2022 at 18:55
  • $\begingroup$ FWIW, the index set of all TMs that accept the empty language -- $L$ in @Nathaniel's comment -- is indeed not recursive. You can show this by Rice's theorem; see our reference question. $\endgroup$
    – Raphael
    Dec 11, 2022 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.