Languages That Are Not Recursively Enumerable
We can establish the existence of languages that are not recursively enumerable
in a variety of ways. One is very short and uses a very fundamental and elegant
result of mathematics.
Theorem 11.1
Let S be an infinite countable set. Then its power set 2 s is not countable.
Proof: Let S = {s 1 , s 2 , s 3 ,…}. Then any element t of 2 s can be represented by a
sequence of 0’s and 1’s, with a 1 in position i if and only if s i is in t. For
example, the set {s 2 , s 3 , s 6 } is represented by 01100100…, while {s 1 , s 3 , s 5 ,…}
is represented by 10101…. Clearly, any element of 2 s can be represented by such
a sequence, and any such sequence represents a unique element of 2 s . Suppose
that 2 s were countable; then its elements could be written in some order, say t 1 ,
t 2 ,…, and we could enter these into a table, as shown in Figure 11.2. In this table,
take the elements in the main diagonal, and complement each entry, that is,
replace 0 with 1, and vice versa. In the example in Figure 11.2, the elements are
1100…, so we get 0011…as the result. The new sequence along the diagonal
represents some element of 2 s , say t i or some i. But it cannot be t 1 because it
differs from t 1 through s 1 . For the same reason it cannot be t 2 , t 3 , or any other
entry in the enumeration. This contradiction creates a logical impasse that can be
removed only by throwing out the assumption that 2 s is countable.
This kind of argument, because it involves a manipulation of the diagonal
elements of a table, is called diagonalization. The technique is attributed to the
We can establish the existence of languages that are not recursively enumerable
in a variety of ways. One is very short and uses a very fundamental and elegant
result of mathematics.
Theorem 11.1
Let S be an infinite countable set. Then its power set 2 s is not countable.
Proof: Let S = {s 1 , s 2 , s 3 ,…}. Then any element t of 2 s can be represented by a
sequence of 0’s and 1’s, with a 1 in position i if and only if s i is in t. For
example, the set {s 2 , s 3 , s 6 } is represented by 01100100…, while {s 1 , s 3 , s 5 ,…}
is represented by 10101…. Clearly, any element of 2 s can be represented by such
a sequence, and any such sequence represents a unique element of 2 s . Suppose
that 2 s were countable; then its elements could be written in some order, say t 1 ,
t 2 ,…, and we could enter these into a table, as shown in Figure 11.2. In this table,
take the elements in the main diagonal, and complement each entry, that is,
replace 0 with 1, and vice versa. In the example in Figure 11.2, the elements are
1100…, so we get 0011…as the result. The new sequence along the diagonal
represents some element of 2 s , say t i or some i. But it cannot be t 1 because it
differs from t 1 through s 1 . For the same reason it cannot be t 2 , t 3 , or any other
entry in the enumeration. This contradiction creates a logical impasse that can be
removed only by throwing out the assumption that 2 s is countable.
This kind of argument, because it involves a manipulation of the diagonal
elements of a table, is called diagonalization. The technique is attributed to the