效绵鼎 Instantaneous Descriptions of a Turinga Machine ■ Initially,a TM has a tape consisting of a string of input symbols surrounded by an infinity of blanks in both directions. ■ The TM is in the start state,and the head is at the leftmost input symbol. .16
Instantaneous Descriptions of a Turing Machine ◼ Initially, a TM has a tape consisting of a string of input symbols surrounded by an infinity of blanks in both directions. ◼ The TM is in the start state, and the head is at the leftmost input symbol. 16
效绵鼎 TMID's-(2) ■ An ID is a string aqβ，where aβincludes the tape between the leftmost and rightmost nonblanks. The state q is immediately to the left of the tape symbol scanned If q is at the right end,it is scanning B. 0 Ifq is scanning a B at the left end,then consecutive B's at and to the right of q are part of a .17
TM ID’s – (2) ◼ An ID is a string q, where includes the tape between the leftmost and rightmost nonblanks. ◼ The state q is immediately to the left of the tape symbol scanned. ◼ If q is at the right end, it is scanning B. If q is scanning a B at the left end, then consecutive B’s at and to the right of q are part of . 17
效绵鼎 TMID's-(3) ■As for PDA’s we may use symbols andH*to represent“becomes in one move”& and "becomes in zero or more moves,respectively, on ID's. Example:The moves of the previous TM are q00r0q0r00q0q01r00q1000f .18
TM ID’s – (3) ◼ As for PDA’s we may use symbols ⊦ and ⊦* to represent “becomes in one move” and “becomes in zero or more moves,” respectively, on ID’s. ◼ Example: The moves of the previous TM are q00⊦0q0⊦00q⊦0q01⊦00q1⊦000f 18
效绵鼎 月 Formal Definition of Moves 1. If 5(q,Z)=(p,Y,R),then oqZβFaYpB IfZ is the blank B,then also aqhaYp 2. If (q,Z)=(p,Y,L),then u For any X,oXqZβFapXYβ u In addition,qZβrpBYβ .19
Formal Definition of Moves 1. If δ(q, Z) = (p, Y, R), then u qZ⊦Yp u If Z is the blank B, then also q⊦Yp 2. If δ(q, Z) = (p, Y, L), then u For any X, XqZ⊦pXY u In addition, qZ⊦pBY 19
效绵鼎 Languages of a TM A TM defines a language by final state,as usual. L(M)={w qow*I,where I is an ID with a final state}. Or,a TM can accept a language by halting H(M)={w qow*I,and there is no move possible from ID I. .20
Languages of a TM ◼ A TM defines a language by final state, as usual. ◼ L(M) = {w | q0w⊦*I, where I is an ID with a final state}. ◼ Or, a TM can accept a language by halting. ◼ H(M) = {w | q0w⊦*I, and there is no move possible from ID I}. 20