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

- N(<N>) accepts: <N> is in L
_{D}so by definition of L_{D}, N does not accept <N>, a contradiction. - N(<N>) does not accept: <N> is not in L
_{D}so by definition of L_{D}, N accepts <N>, a contradiction.

*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.

Already stuck on lesson 3... have not halted, accepted or rejected after 1 day. Continuing processing. Thanks for the lessons!

ReplyDeleteHi, I'm studying some topics of computational complexity now, and there is one thing that seems hard to understand regarding relativization. I know it is not the right place to post this, but I think it is somehow related to diagonalization. So, here is my question:

ReplyDeleteTake for instance the class C=P^NP, and a language B. How are the oracle machines from C^B working?

- are they deterministic polytime machines that ask queries from NP^B?

- are they deterministic polytime machines that ask queries to both B and NP?

Thanks!

The rule is all machines must have access to oracle B. So in (P^NP)^B both the P and NP machines have access to B, think ((P^B)^(NP^B)). Now the P machine can access B through the NP machine so this is the same as P^(NP^B).

ReplyDeleteThanks!

ReplyDelete