Turing machine

Theory Of Computation

1. Presentation on Turing Machine Presented By : Kanis Fatema 17102010 Monisha Dey 17102032 Rezuana Khatun 16102033

2. Objectives Definition Formal Definition Representation of Turing Machine Model of Turing Machine Transition Function Transition Diagram Instantaneous Description Multi-tape Turing Machine Example

3. INTRODUCING TURING MACHINES by Alan Turing in 1936 . mathematical model of a computer. computing capability of a computer.

4. DEFINITION a finite-state machine a tape head that can read or write one tape cell and move left or right. accepts the input string used for input and working storage .

5. Representation of Turing Machine Turing Machine is represented by M=(Q , ∑ , Γ,δ,q0,B,F) , Where Q is the finite state of states ∑ a set of Γ not including B, is the set of input symbols, Γ is the finite state of allowable tape symbols, δ is the next move function, a mapping from Q × Γ to Q × Γ ×{L,R} Q0 in q0 is the start state, B a symbol of Γ is the blank, F is the set of final states.

6. THE TURING MACHINE MODEL

7. TRANSITION FUNCTION One move (denoted by |---) in a TM does the following: δ(q , X) = (p ,Y ,R/L) q is the current state X is the current tape symbol pointed by tape head State changes from q to p

8. Transition Diagram

9. Instantaneous Description For Turing Machine ID of a Turing Machine is a snapshot of Turing Machine to describe the current situation of the Turing Machine. X1 X2…Xi-1 q Xi Xi+1 … Xn Means: q is the current state Tape head is pointing to Xi X1X2…Xi-1 Xi Xi+1… Xn are the current tape symbols δ ( q , Xi ) = (p ,Y , R ) is same as: X1 X2…Xi-1 q Xi Xi+1 … Xn |---- X1 X2…Xi-1 Y p Xi+1… Xn δ ( q ,Xi) = (p, Y ,L) same as: X1 X2…Xi-1 q Xi Xi+1 … Xn |---- X1 X2…pXi-1Y Xi+1 … Xn

10. MULTITAPE TURING MACHINES A Turing Machine with several tapes Every Tape have their Controlled own R/W Head For N- tape TM M=(Q, ∑ , Γ,δ, q0,B,F) we define δ : Q X Γ N Q X Γ N X { L , R} N

11. A Multi-tape Turing machine can be formally described as a 6-tuple ( Q, ∑, B, δ, q , F ) where − Q  is a finite set of states ∑ is the tape alphabet B  is the blank symbol δ  is a relation on states and symbols where δ: Q × X k  → Q × (X × { Left_shift , Right_shift , No_shift }) k where there is k number of tapes q  is the initial state F  is the set of final states

12. Uses Of Turing Machine language recognizer language generator language evaluator language decider

13. Transition Diagram of Turing Machine The formal specification of the Turing Machine M that accept the language {0 n 1 n | n ≥ 1}is, M = ({q , q 2 , q 3 , q 4 },{0,1},{0,1,X,Y,B}, δ , q , B, {q 4 }) where δ is given in the table below,

14. q q 1 q 3 q 2 q 4 0/0 1/Y X/X Y/Y Y/Y B/B Y/Y 0/0 Y/Y 0/X

15. Question?

16. Thank You