# Are empty-set languages recursively enumerable?

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.

• Note that the language is the set of strings, not the description. There is only one empty language. Commented Nov 17, 2017 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$.
• 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. Commented Dec 11, 2022 at 18:55
• 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. Commented Dec 11, 2022 at 20:55