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 Feb 14 2008 Lecture 4 Lecturer Scott Aaronson 1 Scribe Aseem Kishore Previously in 6 089 Last lecture we talked about two di erent models of computation nite automata and circuits Finite automata allowed us to recognize many properties of an arbitrarily long input while circuits allowed us to represent any Boolean function However both models had signi cant limitations Circuits were limited in hardware we have to know how big an input is before we can make a circuit for it while nite automata were limited by their memory which also had to be known in advance of a problem 2 Turing Machines How can we generalize nite automata to overcome their limitations A rst idea is to let them move backwards on the tape as well as forwards This is a good start but by itself it actually provides no extra power To see why suppose a two way nite automaton is in some state a going forward at some point x on the tape At this point if it goes backwards on the tape and then returns to x that simply induces some function a f a where f depends on the earlier part of the tape But this means that we can simulate the two way machine by a one way machine which simply keeps track of the whole function f instead of just the state a 1 Thus being able to move in two directions provides no additional power on its own What we really need is a machine that can not only move backwards and forwards but also write to the tape and halt at any time of its choosing And that s what a Turing machine is The ability to write essentially gives Turing machines an unlimited memory since any information that can t t in the machine s internal state can always be written to the tape The ability to halt at discretion means that Turing machines aren t tied to the input the way nite automata are but can do as much auxiliary computation as they need So at any given point on the tape a Turing machine faces three questions 1 Change state 2 Write to the tape 3 Move left move right or halt The machine s answer to these questions is a function of its current state and the current input on the tape A clear example of these features overcoming the limitations of nite automata is a Turing machine s ability to solve the palindrome problem By using a simple back and forth process a 1 Note that the number of functions f a mapping states to states grows exponentially with the number of states in the original machine 4 1 Turing machine can repeatedly check that a letter at one end exists at the opposite end and by marking letters that it has seen the machine ensures it continuously narrows its scope Here we re assuming that additional symbols are available besides just 0 and 1 This algorithm takes O n2 time interestingly there is a proof that argues that this is the best a Turing machine can do Likewise addition of integers is also possible as are multiplying and some other mathematical operations We won t prove that Searching for non regular patterns also becomes possible But perhaps the most interesting thing a Turing machine can do is to emulate another Turing machine 3 Universal Turing Machines In his 1936 paper On Computable Numbers in some sense the founding document of computer science Turing proved that we can build a Turing machine U that acts as an interpreter for other Turing machines In other words U s input tape can contain a description of another Turing machine which is then simulated step by step Such a machine U is called a Universal Turing machine If a universal machine didn t exist then in general we would need to build new hardware every time we wanted to solve a new problem there wouldn t even be the concept of software This is why Professor Aaronson refers to Turing s universality result as the existence of the software industry lemma A question was brought up in class as to how this can be if the machine being interpreted may require more states than the interpreting Turing machine has It turns out that universal Turing machines aren t limited by their states because they can always keep extra state on blank sections of the tape They can thus emulate a machine with any number of states but themselves requiring only a few states In fact there is a popular parlor type competition to nd a universal Turing machine that uses as few states and symbols as possible Recently one student actually came up with such a machine that uses only two states and a three symbol alphabet To be fair however the machine required the inputs in a special format which required some pre computation so a question arises as to how much of the work is being done by the machine versus beforehand by the pre computation 4 The Church Turing Thesis Related to the idea of universal machines is the so called Church Turing thesis which claims that anything we would naturally regard as computable is actually computable by a Turing machine Intuitively given any reasonable model of computation you like RAM machines cellular au tomata etc you can write compilers and interpreters that translate programs back and forth between that model and the Turing machine model It s never been completely clear how to inter pret this thesis is it a claim about the laws of physics about human reasoning powers about the computers that we actually build about math or philosophy Regardless of its status the Church Turing Thesis was such a powerful idea that Go del declared one has for the rst time succeeded in giving an absolute de nition to an interesting epistemological notion But as we ll see even Turing machines have their limitations 4 2 5 Halting is a problem Suppose we have a Turing machine that never halts Can we make a Turing machine that can detect this In other words can we make an in nite loop detector This is called the Halting problem The bene ts of such a machine would be widespread For example we could then prove or disprove Goldbach s Conjecture which says that all even numbers 4 or greater are the sum of two primes We could do this by writing a machine that iterated over all even numbers to test this conjecture for i 2 to infinity if 2 i is not a sum of two primes then HALT We would then simply plug this program into our in nite loop detecting Turing machine If the machine detected a halt we d know the program must eventually encounter a number for