Turing machine automata ppt

turing machine ppt slides and turing machine ppt with example
Dr.SamuelHunt Profile Pic
Dr.SamuelHunt,United Arab Emirates,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
Turing Machines (TM)Outlines • Structure of Turing machines • Deterministic Turing machines (DTM) – Accepting a language – Computing a function • Composite Turing machines • Multitape Turing machines • Nondeterministic Turing machines (NTM) • Universal Turing machines (UTM) www.ThesisScientist.comStructure of TM Finite set of states CONTROL Start state UNIT A single halt state TAPE Move left or right one HEAD cell at a time TAPE Store input for the TM Can be of any length Can read from and write on tape www.ThesisScientist.comWhat does a TM do? • Determine if an input x is in a language. – That is, answer if the answer of a problem P for the instance x is “yes”. • Compute a function – Given an input x, what is f(x)? www.ThesisScientist.comHow does a TM work? • At the beginning, –A TM is in the start state (initial state) –its tape head points at the first cell –The tape contains , following by input string, and the rest of the tape contains . www.ThesisScientist.comHow does a TM work? • For each move, a TM – reads the symbol under its tape head – According to the transition function on the symbol read from the tape and its current state, the TM: • write a symbol on the tape • move its tape head to the left or right one cell or not • changes its state to the next state www.ThesisScientist.comWhen does a TM stop working? • A TM stops working, – when it gets into the special state called halt state. (halts) • The output of the TM is on the tape. – when the tape head is on the leftmost cell and is moved to the left. (hangs) – when there is no next state. (hangs) www.ThesisScientist.comHow to define deterministic TM (DTM) • a quintuple (Q, , , , s), where – the set of states Q is finite, not containing halt state h, – the input alphabet  is a finite set of symbols not including the blank symbol , – the tape alphabet  is a finite set of symbols containing , but not including the blank symbol , – the start state s is in Q, and – the transition function  is a partial function from Q ()  Qh  () L, R, S. www.ThesisScientist.comExample of a DTM • M= s /,L (s,p1,p2,p3,p4,q1,q2, /,R 1/,R 0,1,0,1,, , s p1 q1 /,R 0/,R 0/0,L /,R 1/1,L 0/0,R p2 1/1,R p4 q2 /1,L /,L 0/,L h p3 www.ThesisScientist.comHow a DTM works s /,L /,R 1/,R p1 q1  1 0 0 0 1 0 0 0  /,R 0/,R 0/0,L /,R 1/1,L 0/0,R p2 1/1,R p4 q2 /1,L /,L 0/,L On the input 0001000, h p3 the TM halts. www.ThesisScientist.comHow a DTM works s /,L /,R 1/,R p1 q1  0 0 0 0 0 0 0  /,R 0/,R 0/0,L /,R 1/1,L 0/0,R p2 1/1,R p4 q2 /1,L On the input 0000000, /,L 0/,L the TM hangs. h p3 www.ThesisScientist.comConfiguration Definition • Let T = (Q, , , , s) be a DTM. A configuration of T is an element of  Q  h () ()() • Can be written as – (q,l,a,r) or string to the right of tape head Current state – (q,lar) symbol under tape head string to the left of tape head www.ThesisScientist.comYield the next configuration Definition • Let T = (Q, , , , s) be a DTM, and (q ,  a ) 1 1 1 1 and (q ,  a ) be two configurations of T. 2 2 2 2 We say (q ,  a ) yields (q ,  a ) in one step, 1 1 1 1 2 2 2 2 T denoted by (q ,  a )  (q ,  a ), if 1 1 1 1 2 2 2 2 –(q , a ) = (q ,a ,s),  = and = , 1 1 2 2 1 2 1 2 –(q , a ) = (q ,b,R),  = b and =a , 1 1 2 2 1 1 2 2 –(q , a ) = (q ,b,L),  = a and =b . 1 1 2 1 2 2 2 1 www.ThesisScientist.comYield in zero step or more Definition • Let T=(Q, ,, , s) be a DTM, and (q ,  a ) and 1 1 1 1 (q ,  a ) be two configurations of T. 2 2 2 2 We say (q ,  a ) yields (q ,  a ) in zero step or 1 1 1 1 2 1 2 2 more, denoted by (q ,  a ) - (q ,  a ), if 1 1 1 1 T 2 1 2 2 – q =q ,  = , a = a , and  =  , or 1 2 1 2 1 2 1 2 – (q , a )- (q, a) and (q, a)- (q , a ) 1 1 1 1 T T 2 1 2 2 for some q in Q, and  in  , and a in . www.ThesisScientist.comYield in zero step or more: Example (p4,010) (s,0001000) s (p4,010) (p1,0001000) /,L (p1,010) (p2,001000) /,R (p2,10) (p2,001000) 1/,R (p2,10) p1 q1 (p3,001000) (p2,10) /,R (p4,00100) 0/,R (p3,10) (p4,00100) 0/0,L /,R 1/1,L (p4,1) (p1,00100) (p4,1) (p2,0100) 0/0,R p2 1/1,R p4 q2 (p1,1) (p2,0100) (q1,) (p3,0100) /1,L (q1,) /,L (q2,) 0/,L (h ,1) h p3 www.ThesisScientist.comTM accepting a language • Definition Let T=(Q, , , , s) be a TM, and w. T accepts w if (s, , , w) - (h, , , 1). T The language accepted by a TM T, denoted by L(T), is the set of strings accepted by T. www.ThesisScientist.comExample of language accepted by a TM n n L(T)=0 10 n0 s n n • T halts on 0 10 /,L /,R n+1 n • T hangs on 0 10 at p3 1/,R p1 q1 n n+1 • T hangs on 0 10 at q1 /,R n 2 n 0/,R • T hangs on 0 1 0 at q1 0/0,L /,R 1/1,L 0/0,R p2 1/1,R p4 q2 /1,L /,L 0/,L h p3 www.ThesisScientist.comTM computing a function • Definition Let T=(Q, , , , s) be a TM, and f be a function from  to  . T computes f if, for any string w in  , (s, , , w) - (h, , , f(w)). T www.ThesisScientist.comExample of TM Computing Function 1/1,L 1/1,R 1/1,R /,R 1/,L /1,R/,L p1 p2 p3 p4 s /,R h www.ThesisScientist.comExample of TM Computing Function 0/0,L 0/0,R /0’,L 1/1,R 1/1,L q2 q1 h 0’/0’,L 1’/1’,L 0’/0,R/,S /0,R 0/,R 1’/1,R /,R 0’/0,R/,L p1 p2 p3 s 1’/1,R /1,R 1/,R 1/1,L 0/0,L r2 r1 0/0,R 0/0,L /1’,L 1/1,R 1/1,L 0’/0’,L 1’/1’,L www.ThesisScientist.com

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.