turing machine theory and making process.pptx

about turing machine

1. Turing Machine Theory Lecture 11

2. Related video links https://www.youtube.com/watch?v=qz_YJeOx4kA https://www.youtube.com/watch?v=sX5_9xjr-9Q https://www.youtube.com/watch?v=DlMtBUbbZng

3. What is Turing Machine A Turing machine consists of a finite-state control unit and a tape that is infinite in both directions and divided into cells, each of which can hold one symbol: At each step, the control unit performs two actions in a way dependent on: 1. either – move the read/write head one cell to the left or right; 2. put the control unit into a new state

4. What is Turing Machine Turing machine will be your ultimate model for computer. In Turing machine output is very important. We know that every program has an output but this is not exactly true.

5. Formal Definition A Turing machine is a 7-tuple (Q, ∑, Γ, ∂, q0 , qaccept , qreject ), where: Q is a set of states ∑ is a set of symbols (the alphabet) Γ is a set of symbols that can be written in tape, ∈ Γ and ∑ ⊆ Γ q0 ∈ Q is the initial state

6. Formal Definition q accept is the accepting state q reject is the rejecting state, q reject ≠ q accept ∂ is a collection of transitions defined by the function: ∂: (Q − { qaccept , qreject }) × Γ  Q × Γ × {  ,  }

7. Halt State in Turing Machine The machine halts in a state if there is no transition to follow.

8. Uses of Turing Machine