# FORMAL LANGUAGES, AUTOMATA AND COMPUTATION

0 0 11 views

**Unformatted text preview: **

F ORMAL L ANGUAGES AUTOMATA AND C OMPUTATION T URING M ACHINES Carnegie Mellon University in Qatar L ECTURE 12 S LIDES FOR 15 453 S PRING 2011 1 13 T URING M ACHINES S YNOPSIS We now turn to a much more powerful model of computation called Turing Machines TM TMs are similar to a finite automaton but a TM has an unlimited and unrestricted memory A TM is a much more accurate model of a general purpose computer Bad News Even a TM can not solve certain problems Such problems are beyond theoretical limits of computation L ECTURE 12 S LIDES FOR 15 453 S PRING 2011 2 13 T URING M ACHINES L ECTURE 12 S LIDES FOR 15 453 S PRING 2011 3 13 T URING M ACHINES VS F INITE AUTOMATA A TM can both read from the tape and write on the tape The read write head can move both to the left L and to the right R The tape is infinite to the right The states for rejecting and accepting take effect immediately not at the end of input L ECTURE 12 S LIDES FOR 15 453 S PRING 2011 4 13 H OW DOES A TM COMPUTE Consider B w w w 0 1 The TM starts with the input on the tape 0 1 1 0 0 0 0 1 1 0 0 0 t t tt X 1 1 0 0 0 0 1 1 0 0 0 t t tt X 1 1 0 0 0 X 1 1 0 0 0 t t tt X 1 1 0 0 0 X 1 1 0 0 0 t t tt X X 1 0 0 0 X 1 1 0 0 0 t t tt X X X X X X X X X X X X t t tt ACCEPT L ECTURE 12 S LIDES FOR 15 453 S PRING 2011 5 13 F ORMAL D EFINITION OF A T URING M ACHINE A TM is 7 tuple M Q q0 qaccept qreject where Q are all finite sets 1 Q is the set of states 2 is the input alphabet blank symbol t 6 3 is the tape alphabet t and 4 Q Q L R is the state transition function 5 q0 Q is the start state 6 qaccept Q is the accept state 7 qreject Q is the reject state and qreject 6 qaccept L ECTURE 12 S LIDES FOR 15 453 S PRING 2011 6 13 H OW DOES A TM C OMPUTE M receives its input w w1 w2 wn on the leftmost n squares on the tape The rest of the tape is blank The head starts on the leftmost square on the tape The first blank symbol on the tape marks the end of the input The computation proceeds according to The head of M never