Theory Of Computation (2160704)

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:
  1. Reading a symbol being scanned.
  2. Modifying a symbol being scanned.
  3. 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.