Foundations of Complexity Lesson 3: Universal Turing Machines and Diagonalization

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 L_U be the set of pairs (<M>,x) such that machine M accepts input x. L_U 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 L_D be the set of <M> such that machine M does not accept <M>. Suppose L_D is computably enumerable. There must be some machine N such that N(<M>) accepts if and only if <M> is in L_D. We have two cases

1. N(<N>) accepts: <N> is in L_D so by definition of L_D, N does not accept <N>, a contradiction.
2. N(<N>) does not accept: <N> is not in L_D so by definition of L_D, N accepts <N>, a contradiction.

This kind of argument is called diagonalization. It is the main technique to show that problems cannot be computed.

Step back for a second. We have shown that the language L_D cannot be computed by a computer. Any computer. Ever.