Turing machine in automata

Limitation of finite automata and pushdown automata 

Finite Automata is an abstract model of general purpose computer that is only capable of doing recognizing of regular language.

To remove the limitation of finite automata and add one additional memory(stack) and this model is known as Pushdown automaton.Pushdown automaton does the same job as finite automaton that is recognization not computation.

In real  machine  that can perform recognization as well as computation . Computer system which are capable of doing recognization as well as computation.

Turing machine 

which are capable of doing

Recognization 

computation.

Turing machine which uses a read-write tape instead of read only tape.Tape is divided into cell.Each cell hold one input symbol.The head of turing machine is capable of reading as well as writing on the tape and can move left to right and right to left.Turing machine is abstract version of computer system this has been used to define what is computable.

Turing machine is suggested by Alan Turing an English mathematician in 1936.Alan turing formulated an abstract machine and based on his name this machine is known as Turing machine.

Turing machines recognize the languages definable by these grammars and these languages are called Type 0 language or recursively enumerable languages.

Turing machine stop eventually in a halting state for each word in the language. Halting state is a special state in turing machine similar to the final state.

Basic Model of Turing Machine

Turing machine consists of  

• A  tape which is finite at left end and infinite at right end.
• Finite control to control the operations and a read and write head.

Turing machine reading and writing capability make it different and powerful from other class of machine.There is left end marker $ on the tape that indicate the left end of the tape .

Mathematical Description of Turing Machine

Turing Machine consist of 4 Tuples (Q,∑,δ,s)

• Q is the finite set of states not including the halt state.
• ∑ is the alphabet containing the blank symbol #.
• δ is the transition function which maps from Q*∑ to (Q∪ {h})*{L,R}).
• s∈Q is the initial state or starting state.

Turing machine processes some input then it may fall into one of these states:

• Halting state.
• Non Halting state.
• Loop.
• Crash.
• Hang state.

when Turing Machine read input on the tape then it keeps write on the tape and when it halts or stops the processing then whatever written on the tape in the output of produce by it.

Example:

Design a turing machine which increments the input decimal integer number by one.

Solution:

Turing Machine M=(Q,{0,#},δ,s) increments the input integer number by one.It means if m is the decimal number then output is m+1.

f(m)=m+1.

δ(s,0)=(s,0,R)

δ(s,#)=(h,0,S)

let consider decimal number m=2

δ(s,00##)

δ(s,00##)

δ(s,00##)

δ(h,000#)

Decimal number 2 is increment by 1 . Now m is 3.

M read input from left and reaches the end of input without right and add one zero at the end to increment the input number by one.

Transition diagram

So that proved Turing machine can perform computation Increment,decrement,addition,subtraction . Because turing machine have read and write capability and left to right movement capability.