Finite State Machines - II
Question 2: Given a Turing Machine can we construct an equivalent Finite State Machine?
The above Turing Machine, as simple as it is, cannot be duplicated as a Finite State Machine simply because one instruction rewrites the tape character.
Response: Only in a limited number of cases.
- Essentially a Finite State Machine uses a tape that is only one directional - the Turing Machine can move in either direction.
- Once a FSM has "seen" a character it is lost; in the TM the character can still be retained on the tape. Thus the FSM has no "memory" except that which is implied in the choice of states; in the TM there is an unbounded memory on the tape.
Only Turing machines that:
can be converted to Finite State Machines.
- Do not rewrite characters on the tape; and
- Move in only one direction,
CS1104 Main Page
Last Updated 2000/11/12
© J.A.N. Lee, 2000