[Overview] [Previous] [Next]

Non-Recursively Enumerable Languages

A language is a subset of sigma*. A language is any subset of sigma*.

We have shown that Turing machines are enumerable. Since recursively enumerable languages are those whose strings are accepted by a Turing machine, the set of recursively enumerable languages is also enumerable.

We have shown that the powerset of an infinite set is not enumerable -- that it has more than aleph0 subsets. Each of these subsets represents a language. Therefore, there must be languages that are not computable by a Turing machine.

According to Turing's thesis, a Turing machine can compute any effective procedure. Therefore, there are languages that cannot be defined by any effective procedure.

We can find a non-recursively enumerable language X by diagonalization. Using the enumerations described earlier, let string i belong to language X if and only if it does not belong to language i.

Problem. I've just defined a procedure for defining a non-recursively enumerable language. Isn't this a contradiction?


Copyright 1996 by David Matuszek
Last modified Apr 1, 1996