15 251 Great Theoretical Ideas in Computer Science Lecture 21 Dan Kilgallin Turing Machines Goals Describe the nature of computation Mathematically formalize the behavior of a program running on a computer system Compare the capabilities of different programming languages Turing Machines What can we do to make a DFA better Idea Give it some memory How much memory Infinite What kind of memory Sequential access e g CD hard drive or RAM An infinite amount of RAM requires remembering really big numbers and needlessly complicates proofs Turing Machines Definition A Turing Machine consists of o A DFA to store the machine state called the controller o An array that is infinitely long in both directions called the tape o A pointer to some particular cell in the array called the head Operation The head begins at cell 0 on the tape The DFA begins in some initial state Symbols from some alphabet are written on a finite portion of the tape beginning at cell 1 Operation At each step the machine uses as input o The state of the controller o The symbol written on the cell which the head is at Using this the machine will o Transition to some state in the DFA possibly the same state o Write some symbol possibly the same symbol on the tape o Move the head left or right one cell Two Flavors The machine will stop computation if the DFA enters one of a pre defined set of halting states A decision machine will if it reaches a halting state output either Yes or No i e there are accepting and rejecting halt states A function machine will if it reaches a halting state have some string of symbols written on the tape This string of symbols is the output of the function Example Doubling a Number 0 1 2 3 1 0 1 Notation old symbol new symbol direction to move epsilon denotes empty cell H denotes halting state s 4 5 Example Doubling a Number 0 1 2 3 1 0 1 4 5 Example Doubling a Number 0 1 2 3 1 0 1 4 5 Example Doubling a Number 0 1 2 3 1 0 1 4 5 Example Doubling a Number 0 1 2 3 1 0 1 4 5 Example Doubling a Number 0 1 2 3 1 0 1 4 5 Example Doubling a Number 0 1 2 3 1 0 1 4 5 Example Doubling a Number 0 1 2 3 1 0 4 5 Example Doubling a Number 0 1 2 3 1 0 1 4 5 Example Doubling a Number 0 1 2 3 1 0 1 4 5 Example Doubling a Number 0 1 2 3 1 4 5 0 1 Example Doubling a Number 0 1 2 3 1 4 5 0 1 Example Doubling a Number 0 1 2 3 1 4 5 0 1 Example Doubling a Number 0 1 2 3 4 5 0 1 Example Doubling a Number 0 1 2 3 4 1 0 1 5 Example Doubling a Number 0 1 2 3 4 1 0 1 5 Example Doubling a Number 0 1 2 3 4 1 0 1 5 Example Doubling a Number 0 1 2 3 0 1 0 1 4 5 TM vs DFA Is a decision machine more powerful than a DFA Yes Claim A decision machine can recognize the set anbn n 0 Example anbn Example anbn 0 1 2 3 a a b b 4 5 Example anbn 0 1 2 3 a a b b 4 5 Example anbn 0 1 2 3 4 a b b 5 Example anbn 0 1 2 3 4 a b b 5 Example anbn 0 1 2 3 4 a b b 5 Example anbn 0 1 2 3 4 a b b 5 Example anbn 0 1 2 3 4 a b b 5 Example anbn 0 1 2 3 4 a b 5 Example anbn 0 1 2 3 4 a b 5 Example anbn 0 1 2 3 4 a b 5 Example anbn 0 1 2 3 4 a b 5 Example anbn 0 1 2 3 4 5 b Example anbn 0 1 2 3 4 5 b Example anbn 0 1 2 3 4 5 b Example anbn 0 1 2 3 4 5 Example anbn 0 1 2 3 4 5 Correctness Every time we reach the bottom right state the number of b s deleted equals the number of a s Correctness 0 1 2 3 4 5 Correctness Every time we reach the bottom right state the number of b s deleted equals the number of a s If there are more a s it crashes right after deleting the last b Correctness 0 1 2 3 4 a No a transition 5 Correctness Every time we reach the bottom right state the number of b s deleted equals the number of a s If there are more a s it crashes right after deleting the last b If there are more b s it crashes in the bottom right state after scanning to the left of the b s Correctness 0 1 2 3 4 5 b No epsilon transition Correctness Every time we reach the bottom right state the number of b s deleted equals the number of a s If there are more a s it crashes right after deleting the last b If there are more b s it crashes in the bottom right state after scanning to the left of the b s If NO a s crashes immediately Correctness 0 1 2 3 b b b No b transition 4 5 Correctness Every time we reach the bottom right state the number of b s deleted equals the number of a s If there are more a s it crashes right after deleting the last b If there are more b s it crashes in the bottom right state after scanning to the left of the b s If NO a s crashes immediately If no b s crashes after reading the a s Correctness 0 1 2 3 a a a No epsilon transition 4 5 Definitions A set is recursively enumerable if there is a decision machine which answers yes if and only if the input belongs to the set A function f is computable or recursive if there is a function machine that when given input x produces output f x Interlude What is an algorithm A precise step by step plan for a computational procedure that begins with an input value and yields an output value in a finite number of steps Corbin Leiserson Rivest Introduction to Algorithms Turing machines can capture this notion precisely Algorithms on a TM Given a human comprehensible goal encode the input into some alphabet Define the steps of the algorithm as a DFA Put the input on a tape Let the Turing Machine run Translate the output Objection Why not just use a programming language such as C As it turns out writing a C program is just using a computer to build …
View Full Document
Unlocking...