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 1 Scribe Emilie Kim Administrivia When it is your turn to do scribe 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 nal grade depends on it After you submit your rough draft schedule a meeting with Yinmeng to discuss your notes 2 Review Turing Machines Turing machines 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 machine 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 in nity of real numbers versus the in nity of integers 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 rst electronic computers were used primarily for this purpose of cracking German codes which was extremely di cult because the Germans would change their codes every day The Germans never really suspected that the code had been 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 gure 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 box 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 access 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 M B solves A We write this as A T B 3 2 Example 1 Diophantine equations Given xn 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 x y z n 1 2 3 and try them all one by one in order and then pause when we nd 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 2 This 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 nite collection of tiles of all di erent shapes can we ll an entire plane just using these tiles For simplicity let us assume that all the tiles are 1x1 squares with di erent shaped notches in the sides Figure by MIT OpenCourseWare 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 more 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 nite region can be lled why does it follow that the whole in nite plane can be tiled In comes Ko nig 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 node has at most a nite number of children including 0 2 It is possible to nd a path in this tree going down in any nite length you want Claim The tree has to have a path of in nite length Why is this The tree has to be in nite because if it were nite then there would exist a longest path We don t know how many subtrees there are but there are a …