I am doing a presentation about Turing machines and I wanted to give some background on FSM’s before introducing Turing Machines. Problem is, I really don’t know what is VERY different from one another.

Here’s what I know it’s different:

FSM has sequential states depending on the corresponding condition met while Turing machines operate on infinite “Tape” with a head which

reads and writes.There’s more room for error in FSM’s since we can easily fall on a non-ending state, while it’s not so much for Turing machines since we

can go back and change things.But other than that, I don’t know a whole lot more differences which make Turing machines better than FSM’s.

Can you please help me?

**Answer**

The major distinction between how DFAs (Deterministic Finite Automaton) and TMs work is in terms of how they use memory.

Intuitively, DFAs have no “scratch” memory at all; the configuration of a DFA is entirely accounted for by the state in which it currently finds itself, and its current progress in reading the input.

Intuitively, TMs have a “scratch” memory in the form of tape; the configuration of a TM consists both of its current state and the current contents of the tape, which the TM may change as it executes.

A DFA may be thought of as a TM that neither changes any tape symbols nor moves the head to the left. These restrictions make it impossible to recognize certain languages which can be accepted by TMs.

Note that I use the term “DFA” rather than “FSM”, since, technically, I’d consider a TM to be a finite-state machine, since TMs by definition have a finite number of states. The difference between DFAs and TMs is in the number of configurations, which is the same as the number of states for a DFA, but is infinitely great for a TM.

**Attribution***Source : Link , Question Author : Julio Garcia , Answer Author : hengxin*