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.

Conclusion:

Only Turing machines that:

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.

[Prev][TOC]

CS1104 Main Page
Last Updated 2000/11/12
© J.A.N. Lee, 2000