Comparison of
Turing Machines
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.


Only Turing machines that:

can be converted to Finite State Machines.


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.


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