Theorem 11.4
If a language L and its complement are both recursively enumerable, then
both languages are recursive. If L is recursive, then is also recursive, and
consequently both are recursively enumerable.
Proof: If L and are both recursively enumerable, then there exist Turing
machines M and that serve as enumeration procedures for L and ,
respectively. The first will produce w 1 , w 2 ,…in L, the second
in .
Suppose now we are given any w ∈ Σ + . We first let M generate w 1 and compare
it with w. If they are not the same, we let generate and compare again. If
we need to continue, we next let M generate w 2 , then generate , and so on.
Any w ∈ Σ + will be generated by either M or , so eventually we will get a
match. If the matching string is produced by M, w belongs to L, otherwise it is in
. The process is a membership algorithm for both L and , so they are both
recursive.
For the converse, assume that L is recursive. Then there exists a membership
algorithm for it. But this becomes a membership algorithm for by simply
complementing its conclusion. Therefore, is recursive. Since any recursive
language is recursively enumerable, the proof is completed.
From this, we conclude directly that the family of recursively enumerable
languages and the family of recursive languages are not identical. The language
L in Theorem 11.3 is in the first but not in the second family.
Theorem 11.5
There exists a recursively enumerable language that is not recursive; that is, the
family of recursive languages is a proper subset of the family of recursively
enumerable languages.
Proof: Consider the language L of Theorem 11.3. This language is recursively
If a language L and its complement are both recursively enumerable, then
both languages are recursive. If L is recursive, then is also recursive, and
consequently both are recursively enumerable.
Proof: If L and are both recursively enumerable, then there exist Turing
machines M and that serve as enumeration procedures for L and ,
respectively. The first will produce w 1 , w 2 ,…in L, the second
in .
Suppose now we are given any w ∈ Σ + . We first let M generate w 1 and compare
it with w. If they are not the same, we let generate and compare again. If
we need to continue, we next let M generate w 2 , then generate , and so on.
Any w ∈ Σ + will be generated by either M or , so eventually we will get a
match. If the matching string is produced by M, w belongs to L, otherwise it is in
. The process is a membership algorithm for both L and , so they are both
recursive.
For the converse, assume that L is recursive. Then there exists a membership
algorithm for it. But this becomes a membership algorithm for by simply
complementing its conclusion. Therefore, is recursive. Since any recursive
language is recursively enumerable, the proof is completed.
From this, we conclude directly that the family of recursively enumerable
languages and the family of recursive languages are not identical. The language
L in Theorem 11.3 is in the first but not in the second family.
Theorem 11.5
There exists a recursively enumerable language that is not recursive; that is, the
family of recursive languages is a proper subset of the family of recursively
enumerable languages.
Proof: Consider the language L of Theorem 11.3. This language is recursively