Turing Machines and Alan Turing's Contributions

Turing Machines Turing Machines Part One Part One - -Intro Intro CSCI 432 Computer Science Theory

Alan Turing Alan Turing 1912 - 1954 English mathematician, computer scientist, logician, cryptanalyst "father of computer science theory" code breaker for British in WW2

Human Computer Human Computer If a human were to use pencil and paper to solve problems, what fundamental steps would he use? erasing a symbol on paper and replacing it with another symbol the symbol to write would depend on the symbol observed by the pencil the state of mind of the computer Theory of Computing by Kinber & Smith, page 121

Turing Machine Turing Machine Finite Automata a) current state b) next symbol on the tape c) next state based on current state and next symbol Turing Machine additions d) move the tape backwards e) rewrite the current symbol

Sequence, Selection, Iteration Sequence, Selection, Iteration Sequence o the read head can be moved forward Selection o the states can transition based on the state and the symbol Iteration o the read head can move backward Thus, a Turing Machine has all the elements of an imperative programming language. Theory of Computing by Kinber & Smith, page 122

Church Church- -Turing thesis Turing thesis Every computer algorithm can be implemented as a Turing Machine.

Tape Tape Just like a FA or PDA, the tape is loaded with input symbols before the program is run. The tape has a left border, marked with > if it sees >, it automatically moves right one space The tape has no right border (infinite memory). At the end of the input symbols is a blank space.

States States Just like a FA, the current symbol and the current state determine the next state. o the next state might be the current state A TM has additional actions: o rewrite the current symbol o move forward o move backwards Unlike a FA, a TM does not terminate at the end of input. o Special states terminate the program

Formal Definition Formal Definition S s S H S set of States alphabet, contains > and blank initial state set of Halting States transition function (deterministic)

Formal Notation o This formal definition of the delta function is similar to the notation we used for PDA transitions. o We need to know current state current symbol next state new symbol o Examples o ( (q,a), (p,b) ) When in state q reading symbol 'a', write a 'b' and change state to p. o ( (s,>), (s,R) ) When in state s and reading left end of tape, keep state s and go right

Formal Notation example 1 TM to erase a tape full of the symbol 'a'. 1. ( (s,-), (h,-) ) "-" is my way to indicate a blank 2. ( (s,a), (q,-) ) 3. ( (q,-), (s, R) ) Computations: s q s q s q s h > a a a - > - a a - > - a a - > - - a - > - - a - > - - - - > - - - - > - - - - start state s and initial tape after applying rule 2 after applying rule 3 after applying rule 2 after applying rule 3 after applying rule 1 Theory of Computing by Kinber & Smith, page 124

Common Notation Instead of this form ( (s,-), (h,-) ) ( (s,a), (q,-) ) ( (q,-), (s, R) ) The graphs we used for FAs are easier to draw and use. a/-,- on symbol a / write a blank, don't move -/-,R s q -/-,- on symbol blank / write a blank, move Right h

Example 2 Example 2 Hello World of TMs Turing Machine to determine if the tape is the pattern 01*0 Algorithm: eat first 0 (write over it with a x) eat 1's until we see a 0 (write over them with y) eat second 0 if only blanks remain, then accept 0/x,R 0/x,R A 1/y, R B C 1/1,R -/-,R 1/1,R -/-,R -/-,R reject accept

Example 3 Example 3 L = 0N1N Algorithm repeat: > 0 0 0 1 1 1 - remove that 0 (mark with x) find leftmost 1 remove that 1 (mark with y) move back to leftmost 0 accept if no more 1s A 0/0,R 0/0,L y/y,R y/y,L 0/x,R 1/y,L B C y/y,R x/x,R -/-,L y/y,R -/-,L D for simplicity, transitions to reject state are not shown accept

Next Classes Next Classes more basic Turing Machines creating Turing Machines subroutines varieties of Turing Machines