A Universal Turing Machine is a machine so powerful that it can simulate any other Turing machine. Initially it seems amazing that such a machine can exist. But think about the microprocessor that sits on the computer you are now using. Every program that you use, your word processor, the spreadsheet, the browser, the mp3 player all use code that runs on this processor. This processor acts like a universal Turing machine. Another example, is an interpreter for a language like Java. Suppose we had a program written in C++. The Java interpreter can run code that lets it interprets C++ and thus run any C++ program. This works for any other language and thus a Java interpreter is also a universal Turing machine.
What we have done is to consider programs as data themselves. Fix a programming language. For a machine M let <M> be the binary encoding of the program describing M. Let LU be the set of pairs (<M>,x) such that machine M accepts input x. LU is a computably enumerable set as we can create a machine U that simulates M on input x. The machine U is a universal Turing machine.
We now show that there is a language that is not computably enumerable. Let LD be the set of <M> such that machine M does not accept <M>. Suppose LD is computably enumerable. There must be some machine N such that N(<M>) accepts if and only if <M> is in LD. We have two cases
- N(<N>) accepts: <N> is in LD so by definition of LD, N does not accept <N>, a contradiction.
- N(<N>) does not accept: <N> is not in LD so by definition of LD, N accepts <N>, a contradiction.
Step back for a second. We have shown that the language LD cannot be computed by a computer. Any computer. Ever.