16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] to Computers & ProgrammingTheory of computation 5: Reducibility, Turing machinesProf. Kristina LundqvistDept. of Aero/Astro, MIT16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] b b aA finite automataStatecontrola b b ajklA pushdown automataStates and transition functionTape with input stringNext input symbol to be readCan recognize a language {0n1n| n ≥ 0}16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] 0 1 100Read symbols from the input. As each 0 is read, push it onto the stack. As soon as 1s are read, pop a 0 from stack. If reading the input finishes at the sametime as the stack becomes empty of 0s, the input is accepted. If the stack becomesempty while still reading 1s, or if the 1s are finished while there still are 0s on thestack, reject the input.{0n1n| n ≥ 0}{anbncn| n ≥ 0} is not context free16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] 1 0 1 • •…A Turing machineDifferences between finite automata and Turing machines:1. A TM can both write on the tape and read from it2. The read-write head can move both to the left and to the right3. The tape is infinite4. The special states for rejecting and accepting take immediate effectsCan a TM recognize: {anbncn| n ≥ 0} ?16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] c c • • • …{anbncn| n ≥ 0} ?a a bXb c c • • • …x a bXb c c • • • …x a xXb x c • • • …x a xX{anbncn| n ≥ 0} !!16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected]§ We use the Turing machine as our model of a general purpose computer.§ The primary method for proving that problems are computationally unsolvable is called: Reducibility§ A reduction is a way of converting one problem into another problem in such a way that a solution to the second problem can be used to solve the first problem.§ Example: § Problem of finding your way around in a new city, can bereduced to the problem of obtaining a map of the city§ Problem of measuring the area of a rectangle reduces to theproblem of measuring its height and width16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] Reducibility§ Once we have a single problem known to beundecidable we can determine that other problems are also undecidable by reducing a knownundecidable problem to the new problem. § To use this idea: take a problem known to beundecidable. Call this problem U. Given a new problem, P, if U can be reduced to P so that P can be used to solve U, then P must also beundecidable.16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] Reducibility§ Important – we must show that U reduces to P, not vice versa§ If we show that our P reduces to U then we have only shown that a new problem can be solved by theundecidable problem§ It might still be possible to solve problem P by other means; e.g. we might be taking the tough path to solve P§ But if we can show the other direction, that P can solve U, then P must be at least as hard as U, which we already know to be undecidable.16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] Example§ Does program Q ever call function foo? § This problem is also undecidable§ Just as we saw with the ‘hello world’ problem, it is easy to write a program that can determine if some programs call function foo. § But we could have a program that contains lots of control logic to determine whether or not function foo is invoked. This general case is much harder, and in fact undecidable16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] Example§ Use the reduction technique for the Hello-World problem§ Rename the function “foo” in program Q and all calls to that function.§ Add a function “foo” that does nothing and is not called.§ Modify the program to remember the first 12 characters that it prints, storing them in array A§ Modify the program so that whenever it executes any output statement, it checks the array A to see if the 12 characters written are “hello, world” and if so, invokes function foo.§ If the final program prints “hello, world” then it must also invoke function foo. Similarly, if the program does not print “hello, world” then it does not invoke foo.16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] Caller§ Say that we have a program F-Test that can determine if a program calls foo. § If we run F-Test on the modified program above, not only can it determine if a program calls foo, it can also determine if the program prints “hello, world”. § But we would then be solving the “hello-world-tester” problem which we already know isundecidable, therefore our F-Test problem must beundecidable as well16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] Machines§ TM’s described in 1936§ Turing machines were first proposed by Alan Turing, in an attempt to give a mathematically precise definition of "algorithm" or "mechanical procedure". § Well before the days of modern computers but remains a popular model for what is possible to compute on today’s systems§ Advances in computing still fall under the TM model, so even if they may run faster, they are still subject to the same limitations§ A TM consists of a finite control (i.e. a finite state automaton) that is connected to an infinite tape.16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] Machine§ The tape consists of cells where each cell holds a symbolfrom the tape alphabet. Initially the input consists of a finite-length string of symbols and is placed on the tape. To the left of the input and to the right of the input, extending to infinity, are placed blanks. The tape head is initially positioned at the leftmost cell holding the input.Finite control… B B X1X2… XiXnB B …16.070 — April 25/2003 — Prof. I. K. Lundqvist — [email protected] Machine Details§ In one move the TM will:§ Change state, which may be the same as the current state§ Write a tape symbol in the current cell, which may be the same as the current symbol§ Move the tape head left or right one cell§ Formally, the Turing Machine is denoted by the 7-tuple: § M =
View Full Document
Unlocking...