Unformatted text preview:

MIT OpenCourseWare http://ocw.mit.edu 6.080 / 6.089 Great Ideas in Theoretical Computer Science Spring 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.6.080/6.089 GITCS 21 February 2008 Lecture 5 Lecturer: Scott Aaronson Scribe: Emilie Kim 1 Administrivia When it is your turn to do scrib e notes, please have a rough draft prepared within one week. Then you have until the end of the course to get the notes in better shape, and you’ll want to do that because your final grade depends on it. After you submit your rough draft, schedule a meeting with Yinmeng to discuss your notes. 2 Review Turing Machines Turing m achines can go backwards and forwards on the tape, as well as write to the tape and decide when to halt. Based on this idea of Turing machines comes the “Existence of the Software Industry Lemma”, which states that there exist universal Turing machines that can simulate any other Turing machine by encoding a description of the machine on its tape. The Church-Turing thesis says that Turing machines capture what we mean by the right notion of computability. Anything reasonably called a computer can be simulated by a Turing m achine. However, there are limitations associated with Turing machines. For example, no Turing machine can solve the halting problem (Proof by poem). Also, the number of possible problems is far greater than the number of computer programs. Remember the infinity of real numbers versus the infinity of inte gers. But who cares? That’s why Turing brought up the halting problem; we actually care about that. 3 Oracles Oracles are a concept that Turing invented in his PhD thesis in 1939. Shortly afterwards, Turing went on to try his hand at breaking German naval codes during World War II. The first electronic computers were used primarily for this purpose of cracking German codes, which was extremely difficult because the Germans would change their codes every day. The Germans never really suspected that the code had be en broken, and instead thought that they had a spy among their ranks. At one point they did add settings to the code, which then set the code-breakers back about nine months trying to figure out how to break the new code. 3.1 Oracles An oracle is a hypothetical device that would solve a computational program, free of charge. For example, say you create a subroutine to multiply two matrices. After you create the subroutine, you don’t have to think about how to multiply two matrices again, you simply think about it as a 5-1“black b ox” that you give two matrices and out comes their product. However, we can also say that we have oracles for problems that are unsolvable or problems that we don’t know how to solve. Assuming that the oracle can solve such problems, we can then create hierarchies of unsolvability. If given many hard problems, we can use hierarchies of unsolvability to tell us which problems are hard relative to which other problems. It can tell us things like “this problem can’t be solvable, because if it were, it would allow us to solve this other unsolvable problem”. Given: A : {0, 1}∗ → {0, 1} where the input is any string of any length and the output is a 0 or 1 answering the problem, then we can write MA for a Turing machine M with acces s to oracle A. Assume that M is a multi-tape Turing machine and one of its tapes is a special “oracle tape ”. M can then ask a question, some string x, for the ora-cle on the oracle tape, and in the next step, the oracle will write its answer, A(x), on the oracle tape. From this, we can say that given two problems A and B, A is reducible to B if there exists a Turing machine M such that MB solves A. We w rite this as A ≤T B. 3.2 Example 1: Diophantine equations Given: x n + y n = z n n ≥ 3 xyz = 0 �is there a solution in just integers? In fact, there is no solution involving just integers, and this was an unsolved problem for 350 years. What if we had an oracle for the halting problem? Could we solve this problem? To try to solve this problem, we might try every possible solution in order, (x, y, z, n) of inte-gers: x + y + z + n = 1 x + y + z + n = 2 = 3 = ... and try them all, one by one in order, and then pause when we find the solution. However, if there is no solution, it would just go on forever. So our question to the oracle would be, “Does this program halt or not?”, and if so, the Diophantine equation would be solvable. If we solve the Diophantine problem, can we also then solve the halting problem? 5-2This was an unanswered question for 70 years until 1970, when it was shown that there was no algorithm to solve Diophantine equations because if there were, then there would also be an algorithm for solving the halting problem. Therefore, the halting problem is reducible to this problem. 3.3 Example 2: Tiling the plane Given some finite collection of tiles of all different shapes, can we fill an entire plane just using these tiles? For simplicity, let us assume that all the tiles are 1x1 squares with different-shaped notches in the sides. The halting problem is reducible to this problem, which means if you could solve this problem, you could then also solve the halting problem. Why is this? Assume you could create a set of tiles that would only link together in some way that encodes the possible actions of a Turing machine. If the Turing machine halts, then you wouldn’t be able to add any m ore tiles. Then the plane would only be tiled if the machine runs forever. Is this problem reducible to the halting problem? In other words, if you could solve the halting problem, then can you decide whether a set of tiles will tile the plane or not? Can you tile a 100x100 grid? Can you tile a 1000x1000 grid? These questions can be answered by a Turing machine. But suppose every finite region can be filled, why does it follow that the whole infinite plane can be tiled? In comes K¨onig’s Lemma. Let’s say that you have a tree (a computer science tree, with its root in the sky and grows towards the ground) with two assumptions: 1) Every no de has at most a finite number of children, including 0. 2) It is possible to find a path in this tree going down in any finite length you want. Claim: The tree has to have


View Full Document

MIT 6 080 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?