# What does it mean by "not recursively enumerable"?

I came across following therem:

There exists a recursively enumerable language whose complement is not recursively enumerable.

Now, I know following definitions:

• Recognizable language is one which have one-to-one correspondence with the natural number with the additional property that we could specify an algorithm to enumerate the language elements.
• Given the string not in the co-recognizable language, we can give Turing machine which can eventually confirm that the string indeed does not belong to the language.

Then what does the above theorem mean?:

1. $$L'$$ does not have one-to-one correspondence with the natural numbers?
2. We cannot give an algorithm to enumerate the $$L'$$s elements?
3. $$L'$$ is co-recognizable.
• It means not (recursively enumerable). Nov 10, 2019 at 15:36

I'm using r.e. to mean "recursively enumerable" and co-r.e. to mean "the complement is recursively enumerable". I'm assuming by $$L'$$, you mean the complement of $$L$$.

1. This is not correct. Every language over a finite alphabet $$\Sigma$$ has a one-to-one correspondence to the natural numbers. To show this, you would have to construct a one-to-one function that maps the words of your language to natural numbers. This isn't difficult at all, but a bit technical, so I'm only going to sketch the construction: Pick some well-founded total order $$\leq$$ on $$\Sigma^*$$, for example the lexicographic order. For $$w \in L$$, define $$predecessors(w) := \{ v \in L \mid v \lneq w\}$$ to be the set of words in $$L$$ preceding $$w$$ according to your order. Define a mapping $$f: L \to \mathbb N$$, by $$f(w) := |precedessors(w)|$$, assigning to each word the number of its predecessors. You could then show that $$f$$ is in fact a one-to-one mapping. This construction works for any language, though it is not necessarily computable for all languages.

2. Correct, when $$L$$ is not co-r.e., by definition $$L'$$ is not r.e., so there cannot be an algorithm that enumerates $$L'$$.

3. Correct, your theorem says $$L$$ is r.e., therefore $$L'$$ is co-r.e. Note this follows from the first premise of your theorem, not from the latter premise. In general, $$L'$$ being not r.e. on its own does not imply $$L'$$ being co-r.e. In other words, there are languages that are neither r.e. nor co-r.e., see here.

To elaborate a bit more on what the theorem means: It says there is a language $$L$$ that is r.e. but not co-r.e.

The important insight is that if a language $$L$$ is r.e. and co-r.e., then it is decidable. Assume you have a TM $$M$$ for enumerating $$L$$ and a TM $$M'$$ for enumerating its complement $$L'$$. Then you can build a new TM $$M^\star$$ for deciding $$L$$: For a given input $$w$$, $$M^\star$$ simulates $$M$$ and $$M'$$ in parallel. Since either $$w \in L$$ or $$w \notin L$$, one of $$M$$ or $$M'$$ has to enumerate $$w$$ eventually. At this point, $$M^\star$$ stops the simulation and accepts or rejects $$w$$ based on which of $$M$$ and $$M'$$ enumerated it. It follows that $$M^\star$$ halts on all inputs and accepts $$w$$ iff $$w \in L$$. Therefore, $$L$$ is decidable.

Based on this insight, if you can find a language $$L$$ that is r.e. and undecidable, you can then conclude that it cannot be co-r.e. Since if it would be co-r.e. it could not be undecidable.

The usual example would be some variant of the halting problem, e.g. $$H = \{ \langle M,w\rangle \mid M$$ is a Turing Machine that halts on input $$w\}$$. You should know that $$H$$ is undecidable. To show that $$H$$ is r.e., you would have to construct a TM that enumerates $$H$$. I'm only going to sketch the proof: Your TM $$M^*$$ would iterate over triples of the form $$\langle M, w, n \rangle$$ for a TM $$M$$, $$w \in \Sigma^*$$ and $$n \in \mathbb N$$ in some fixed order (e.g. lexicographic order). When looking at such a triple, $$M^*$$ would simulate $$M$$ on $$w$$ for at most $$n$$ steps. If $$M$$ halts on $$w$$ within these $$n$$ steps, $$M^*$$ prints $$\langle M, w \rangle$$. It's not difficult to see that $$M^*$$ will eventually print every pair $$\langle M,w \rangle$$ for which $$M$$ halts on $$w$$, as for every such pair, there is some $$n \in \mathbb N$$, such that $$M$$ halts on $$w$$ within $$n$$ steps. Therefore, $$M^*$$ enumerates $$H$$, thus $$H^\star$$ is r.e.

Based on knowing that $$H$$ is r.e. and undecidable, you can conclude that $$H$$ cannot be co-.r.e. which proofs your theorem.