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

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 _{0}
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