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 Feb 14, 2008 Lecture 4 Lecturer: Scott Aaronson Scribe: Aseem Kishore 1 Previously in 6.089... Last lecture, we talked about two different models of computation, finite 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 significant limitations. Circuits were limited in hardware–we have to know how big an input is before we can make a circuit for it–while finite automata were limited by their memory–which also had to be known in advance of a problem. 2 Turing Machines How can we generalize finite automata to overcome their limitations? A first 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 finite 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 th en returns to x, that simply induces some function a ⇒ f (a), w here 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, w hich 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 m achine 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 fit in the machine’s intern al 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 finite automata are, but can do as much auxiliary computation as they n eed. So at any given point on th e 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 cu rrent state and the current input on the tape. A clear example of these features overcoming the limitations of finite automata is a Turing machin e’s ability to solve the palindrome problem. By using a simple back-and-forth process, a 1Note that the number of functions f (a) mapping states to states grows exponentially with the number of states in the original machine. 4-1Turing 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 continuous ly 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 d o). 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 C omputable Numbers” (in some sense, the found ing d ocument 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 machin e, which is then simulated step by step. Such a machin e U is called a Universal Turing machine. If a un iversal 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 h ow this can be, if th e machine being interpreted may require more states than the interpreting Turing machine has. It turns out that univers al Turing machin es 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 find a universal Turing machin e that uses as few states and s ymbols as possible. Recently, one student actually came up with such a machine th at uses only two states and a three-symbol alphabet. To be fair, however, the machine required the inputs in a special format, which required s ome 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 anyth ing 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 w rite compilers and interpreters that translate programs back and forth between that model and the Turing m achine 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,


View Full Document

MIT 6 080 - Turing Machines

Download Turing Machines
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 Turing Machines 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 Turing Machines 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?