Turing Machine A Turing machine (TM) is the most powerful kind of automaton. TM consist of states and transitions, and use an infinite tape for storage. The tape is divided into square, each square holds a single symbol. The head is capable of performing 3 operations: Reading a symbol being scanned. Modifying a symbol being scanned. Shifting either to previous square or next square. Advantages Of Turning Machine Over Finite State Machine (FSM) A finite state machine is just a set of states and transitions. The only memory it has is what state it is in. Thus, the number of memory states is... finite. A Turing machine is a finite state machine plus a tape memory. Each transition may be accompanied by an operation on the tape (move, read, write). Its total possible configurations is arbitrarily large, regardless of the size of the program; it expands towards infinity. In between the two is a stack machine, which is like a Turing machine except that the operations are limited to pushing and popping onto the stack. A FSM can recognize only regular expressions. A stack machine can recognize context-free languages. A Turing machine can recongize all recursively enumerable languages.
