Turing Machine
Turing Machine was developed by Alan Turing in 1936. It is more than just recognizing languages. This is the foundation of modern theory of computation.
“What could naturally be called an effective procedure can be realized by a Turing Machine.”
This is known as Church-Turing hypothesis. Turing Machine is still a valid computational model for most modern computers. This machine consists of a state machine, an input tape and a movable r/w tape head. A move of a Turning Machine
– Read the character on the tape at the current position of the tape head
– Change the character on the tape at the current position of the tape head
– Move the tape head
– Change the state of the machine based on current state and character read
Turing Machine consists of infinite tape divided into sets. Except for the finite portion, other will be blank. It is i/o device or accepting device. It accepts as type 0 language.
At current state q, a will be read. Then when the state changes from q ->p , reads another symbol.
δ(q,a) = (p,A,R)
q = current state
a,A = symbols
p = next state
R = move right
i.e read ‘A’ instead of ‘a’ at state p and move right.
When the machine halts, non blank portion is the output and when the machine starts, non blank portion is the input. Therefore it can be said as i/o device. Effective procedures can be realized by TM. This machine can be viewed as a tape player with an arbitrarily extendable tape. The section may contain either 0 or 1 or blank. There is a tape head that looks at one section at a time. This tape head is capable of only three actions
- write on the tape (or erase from tape), only on the section being viewed.
- change the internal state
- move the tape 0 or 1 space to the left or right.
Formally,
A Turing Machine M is a 5-tuple:
– M = (Q, ∑, Γ, q0, δ) where
• Q = a finite set of states (assumed not to contain the
halting state h)
• ∑ = input alphabet (strings to be used as input)
• G = tape alphabet (chars that can be written onto the
tape. Includes symbols from ∑)
• Both ∑ and Γ are assumed not to contain the “blank”
symbol
• δ = transition function