1
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ It means not (recursively enumerable). $\endgroup$ Nov 10, 2019 at 15:36

1 Answer 1

4
$\begingroup$

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

To answer your questions directly:

  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.

$\endgroup$

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.