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 A DFA to store the machine state called the controller An array that is infinitely long in both directions called the tape 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 The state of the controller The symbol written on the cell which the head is at Using this the machine will Transition to some state in the DFA possibly the same state Write some symbol possibly the same symbol on the tape 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 1 0 2 1 3 4 5 Notation old symbol new symbol direction to move epsilon denotes empty cell H denotes halting state s Example Doubling a Number 0 1 1 0 2 1 3 4 5 Example Doubling a Number 0 1 1 0 2 1 3 4 5 Example Doubling a Number 0 1 1 0 2 1 3 4 5 Example Doubling a Number 0 1 1 0 2 1 3 4 5 Example Doubling a Number 0 1 1 0 2 1 3 4 5 Example Doubling a Number 0 1 1 0 2 1 3 4 5 Example Doubling a Number 0 1 1 0 2 3 4 5 Example Doubling a Number 0 1 1 0 2 3 1 4 5 Example Doubling a Number 0 1 1 0 2 3 1 4 5 Example Doubling a Number 0 1 1 2 0 3 1 4 5 Example Doubling a Number 0 1 1 2 0 3 1 4 5 Example Doubling a Number 0 1 1 2 0 3 1 4 5 Example Doubling a Number 0 1 2 0 3 1 4 5 Example Doubling a Number 0 1 1 2 0 3 1 4 5 Example Doubling a Number 0 1 1 2 0 3 1 4 5 Example Doubling a Number 0 1 1 2 0 3 1 4 5 Example Doubling a Number 0 0 1 1 2 0 3 1 4 5 TM vs DFA Is a decision machine more powerful than a DFA Yes Claim A decision machine can recognize n n the set a b n 0 n n Example a b n n Example a b 0 a 1 a 2 b 3 b 4 5 n n Example a b 0 a 1 a 2 b 3 b 4 5 n n Example a b 0 1 a 2 b 3 b 4 5 n n Example a b 0 1 a 2 b 3 b 4 5 n n Example a b 0 1 a 2 b 3 b 4 5 n n Example a b 0 1 a 2 b 3 b 4 5 n n Example a b 0 1 a 2 b 3 b 4 5 n n Example a b 0 1 a 2 b 3 4 5 n n Example a b 0 1 a 2 b 3 4 5 n n Example a b 0 1 a 2 b 3 4 5 n n Example a b 0 1 a 2 b 3 4 5 n n Example a b 0 1 2 b 3 4 5 n n Example a b 0 1 2 b 3 4 5 n n Example a b 0 1 2 b 3 4 5 n n Example a b 0 1 2 3 4 5 n n Example a b 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 a 2 3 4 5 No a 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 Correctness 0 1 2 b 3 4 5 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 b 1 b 2 b 3 4 5 No b 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 If no b s crashes after reading the a s Correctness 0 a 1 a 2 a 3 4 5 No epsilon transition 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 …
View Full Document
Unlocking...