Difference between a turing machine and a finite state machine?

Question

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 1

The short answer to 'the difference between finite automata and Turing machines' is that finite automata are like tiny circuits (with no memory) and Turing machines are like computers that we use everyday, so Turing machines (TMs) are a lot more powerful than finite automata (FA, also called finite state machines).

The power of FA and TMs can be measured by the languages (i.e., a set of strings) they can accept. Accept a language means you can tell it is part of the language or not.

You can design FA to accept the following language:

L1 = {0*1*2*} <- some number of 0s followed by some number of 1s, and followed by some number of 2s.

But FA are not powerful enough to accept the following language:

L2 = {0^k1^k^2k | for some k} <- some number of 0s followed by the same number of 1s, and followed by the same number of 2s.

However, a Turing machine can easily accept L2, as TMs can count and compare.

You may refer to textbooks on how FA can accept L1 but not L2, and How TMs can accept both.