**Comparison of
Turing Machines
and
Finite State Machines - II**

**Question 2:** Given a Turing Machine can we construct an equivalent Finite State Machine?

**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.

**Conclusion:**

Only Turing machines that:

- Do not rewrite characters on the tape; and
- Move in only one direction,

**EXAMPLE:**

CS1104 Main Page

Last Updated 2000/11/12

© J.A.N. Lee, 2000