[Overview] [Previous] [Next]
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