Comparison of Machines

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,

can be converted to Finite State Machines.

EXAMPLE:

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.