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.

  • $\begingroup$ Note that the language is the set of strings, not the description. There is only one empty language. $\endgroup$ – David Richerby Nov 17 '17 at 22:33

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

| cite | improve this answer | |
  • $\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 '17 at 19:42

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.