mathematician G. F. Cantor, who used it to demonstrate that the set of real
numbers is not countable. In the next few chapters, we will see a similar
argument in several contexts. Theorem 11.1 is diagonalization in its purest form.
Figure 11.2
As an immediate consequence of this result, we can show that, in some
sense, there are fewer Turing machines than there are languages, so that there
must be some languages that are not recursively enumerable.
Theorem 11.2
For any non empty Σ, there exist languages that are not recursively enumerable.
Proof: A language is a subset of , and every such subset is a language.
Therefore, the set of all languages is exactly 2 . Since is infinite, Theorem
11.1 tells us that the set of all languages on Σ is not countable. But the set of all
Turing machines can be enumerated, so the set of all recursively enumerable
languages is countable. By Exercise 16 at the end of this section, this implies
that there must be some languages on Σ that are not recursively enumerable.
This proof, although short and simple, is in many ways unsatisfying. It is
completely non constructive and, while it tells us of the existence of some
languages that are not recursively enumerable, it gives us no feeling at all for
what these languages might look like. In the next set of results, we investigate
the conclusion more explicitly.
numbers is not countable. In the next few chapters, we will see a similar
argument in several contexts. Theorem 11.1 is diagonalization in its purest form.
Figure 11.2
As an immediate consequence of this result, we can show that, in some
sense, there are fewer Turing machines than there are languages, so that there
must be some languages that are not recursively enumerable.
Theorem 11.2
For any non empty Σ, there exist languages that are not recursively enumerable.
Proof: A language is a subset of , and every such subset is a language.
Therefore, the set of all languages is exactly 2 . Since is infinite, Theorem
11.1 tells us that the set of all languages on Σ is not countable. But the set of all
Turing machines can be enumerated, so the set of all recursively enumerable
languages is countable. By Exercise 16 at the end of this section, this implies
that there must be some languages on Σ that are not recursively enumerable.
This proof, although short and simple, is in many ways unsatisfying. It is
completely non constructive and, while it tells us of the existence of some
languages that are not recursively enumerable, it gives us no feeling at all for
what these languages might look like. In the next set of results, we investigate
the conclusion more explicitly.