CPS 140 - Mathematical Foundations of CSDr. S. RodgerSection: Turing Machines (handout)ReviewRegular Languages• FA, RG, RE• recognizeContext Free Languages• PDA, CFG• recognizeDFA:5432babba10current stateinput tapeheadtapehead moves Turing Machine:(read and write)5432babba10current stateinput tapeheadtapehead movesTuring Machine (TM)• invented by Alan M. Turing (1936)• computational model to study algorithms1Definition of TM• Storage– tape• actions– write symbol– read symbol– move left (L) or right (R)• computation– initial configuration∗ start state∗ tape head on leftmost tape square∗ input string followed by blanks– processing computation∗ move tape head left or right∗ read from and write to tape– computation halts∗ final stateFormal Definition of TMA TM M is defined by M=(Q,Σ,Γ,δ,q0,B,F) where• Q is finite set of states• Σ is input alphabet• Γ is tape alphabet• B∈ Γisblank• q0is start state• F is set of final states• δ is transition functionδ(q,a) = (p,b,R) means “if in state q with the tape head pointing to an ’a’, then move into state p,write a ’b’ on the tape and move to the right”.TM as Language recognizerDefinition: Configuration is denoted by `.if δ(q,a) = (p,b,R) then a move is denotedabaqabba ` ababpbba2Definition: Let M be a TM, M=(Q,Σ,Γ,δ,q0,B,F). L(M) = {w ∈ Σ∗|q0w∗` x1qfx2for some qf∈F,x1,x2∈Γ∗}TM as language acceptorMisaTM,wisinΣ∗,• if w∈ L(M) then M halts in final state• if w6∈ L(M) then either– M halts in non-final state– M doesn’t haltExampleΣ={a, b}Replace every second ’a’ by a ’b’ if string is even length.• Algorithm3Example:L={anbncn|n ≥ 1}Is the following TM correct?a;1,Ra;a,R2;2,Rb;2,Rb;b,R3;3,Rc;3,La;a,Lb;b,L2;2,L3;3,L2;2,R1;1,RTM as a transducerTM can implement a function: f(w)=w’start with: w↑end with: w’↑Definition: A function with domain D is Turing-computable or computable if there exists TMM=(Q,Σ, Γ,δ,q0,B,F) such thatq0w∗` qff(w)qf∈F, for all w ∈D.Example:f(x) = 2xx is a unary numberstart with: 111↑end with: 111111↑4Is the following TM correct?1;x,R1;1,R 1;1,LB;y,Lx;x,Ry;y,Ry;y,RB;B,Ly;1,Lx;1;LB;B,RExample:L={ww | w ∈ Σ+},Σ={a,