Explain Turing Machine Model.
A Turing machine consists of a finite control which can be in any of finite set of states. There is a tape divided into squares or cells; each cell can hold any one of a finite number of symbols.
Initially, the input, which is a finite-length string of symbols chosen from the input alphabet, is placed on the tape. All other tape cells, extending infinitely to the left and right, initially hold a special symbol called the blank. The blank is a tap symbol, and there may be other tape symbols besides the input symbols and the blank, as well.
There is a tap head that is always positioned at one of the tape cells. The Turing machine is said to be scanning that cell. Initially, the tape head is at the leftmost cell that holds the input.
A move of the Turing machine is a function of the state of the finite control and the tape symbol scanned. In one move, the Turing machine will.
(i) Change state. The next state optionally may be the same as the current state.
(ii) Write a tape symbol in the cell scanned. This tape symbol replaces whatever symbol was in that cell.
(iii) Move the tape left or right.
Formally, a Turing matching (TM) can be described as follows –
M = (Q, Σ, Γ, δ, q0, B, F)
Where,
Q: The finite set of states of the finite control.
Σ: The finite set of input symbols.
Γ: The complete set of input symbols, Σ is always a subset of Γ.
δ: The next move function, a mapping from Q × Γ to Q × Γ × {L, R}.
q0: The start state, a member of Q, in which the finite control is found initially.
B: The blank symbol. This symbol is in Γ but not in Σ.
F: The set of final or accepting states, a subset of Q.
No comments
Dear Members, Thanks for Your Comments. We must be reply your comment answer as soon as possible. Please Stay with us.....