FORMAL LANGUAGES, AUTOMATA ANDCOMPUTATIONTURING MACHINESCarnegie Mellon University in Qatar( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 1 / 13TURING MACHINES-SYNOPSISWe now turn to a much more powerful model ofcomputation called Turing Machines (TM).TMs are similar to a finite automaton, but a TM has anunlimited and unrestricted memory.A TM is a much more accurate model of a general purposecomputer.Bad News: Even a TM can not solve certain problems.Such problems are beyond theoretical limits of computation.( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 2 / 13TURING MACHINES( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 3 / 13TURING MACHINES VS FINITE AUTOMATAA 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 theright (R).The tape is infinite (to the right).The states for rejecting and accepting take effectimmediately (not at the end of input.)( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 4 / 13HOW 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 ttX 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 ttX 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( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 5 / 13FORMAL DEFINITION OF A TURING MACHINEA TM is 7-tuple M = (Q, Σ, Γ, δ, q0, qaccept, qreject) where Q, Σ, Γare all finite sets.1Q 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,5q0∈ Q is the start state,6qaccept∈ Q is the accept state,7qreject∈ Q is the reject state and qreject6= qaccept( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 6 / 13HOW DOES A TM COMPUTE?M receives its input w = w1w2· · · wnon the leftmost n squares onthe 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 moves left of the beginning of the tape(stays there!)The computation proceeds until M enters either qacceptor qreject,when it halts.M may go on forever, never halting!( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 7 / 13CONFIGURATION OF A TMAs a TM proceeds with its computation, the state changes, thetape changes, the head moves.We capture each step of a TM computation, by the notion of aconfiguration.101 101 1 1 1t· · ·101 101 1 1 1t· · ·101 101 1 1 1t· · ·101 101 1 1 1t· · ·101 101 1 1 1t· · ·101 101 1 1 1t· · ·101 101 1 1 1t· · ·101 101 1 1 1t· · ·101 101 1 1 1t· · ·101 101 1 1 1t· · ·101 101 1 1 1t· · ·q7The machine is in state q7, u = 1011 is to the left of the head,v = 01111 is under and to the right of the head. Tape hasuv = 101101111 on it.We represent the configuration by 1011q701111.( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 8 / 13CONFIGURATIONSConfiguration C1yields (⇒)configuration C2if TM canlegally go from C1to C2.ua qibv ⇒ u qjacv if δ(qi, b) = (qj, c, L)ua qibv ⇒ uac qjv if δ(qi, b) = (qj, c, R)If the head is at the left end, qibv ⇒ qjcv if the transition isleft-moving.If the head is at the left end, qibv ⇒ cqjv if the transition isright-moving.Think of a configuration as the contents of memory and atransition as an instruction.( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 9 / 13CONFIGURATIONSThe start configuration is q0w.uqacceptv is an accepting configuration,uqrejectv is a rejecting configuration.Accepting and rejecting configurations are haltingconfigurations.( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 10 / 13ACCEPTING COMPUTATIONA TM M accepts input w if a sequence of configurationsC1, C2, · · · , Ckexists, where1C1is the start configuration of M in input w,2Ci⇒ Ci+1, and3Ckis an accepting configuration.L(M) is the set of strings w recognized by M.A language L is Turing-recognizable if some TM recognizesit (also called Recursively enumerable)A TM is called a decider if it halts on all inputs.A language is Turing-decidable if some TM decides it (alsocalled Recursive)Every decidable language is Turing recognizable!( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 11 / 13EXAMPLE TM-1q1startq2q8q3q4qaq5q6q70, 1 → R 0, 1 → RX → R X → R0, 1, X → L0, 1 → LX → R0 → X , R 1 → X , R# → R # → R# → Rt → R0 → X , L 1 → X , L# → LX → R( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 12 / 13EXAMPLE TM-1Let us see how this TM operates on input 001101#001101( LECTURE 12) SLIDES FOR 15-453 SPRING 2011 13 /