41
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ It's not hard to google for "FSM vs. Turing Machine"! That's the fun part of doing your own research. The main difference is that a Turing machine has infinite "memory", but a FSM doesn't. $\endgroup$
    – Dai
    Commented Oct 21, 2013 at 21:07
  • $\begingroup$ Ok, I cheated a bit there >.>;; Gotcha! Thanks! $\endgroup$
    – Julio Garcia
    Commented Oct 21, 2013 at 21:12
  • 3
    $\begingroup$ the argument about "error" is not correct. Try wikipedia and course books. See what are their basic differences, the purpose of using each one (e.g when we cannot choose a FSM over TM?) and their relation. $\endgroup$
    – Parham
    Commented Oct 21, 2013 at 21:17
  • $\begingroup$ @MahmoudAlimohamadi what I mean is there is a bigger chance for a fsm to land on a non-ending state. $\endgroup$
    – Julio Garcia
    Commented Oct 22, 2013 at 14:40
  • 1
    $\begingroup$ @Dai those comments are silly - at some point (read: now) the first FEW links using google report to this very topic! $\endgroup$
    – paul23
    Commented Oct 6, 2014 at 21:03

5 Answers 5

Reset to default
37
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Ah, got it. One question regarding the "no memory" part: I saw a vending machine example which added up the coins dispensed. How do they know how much money there is if it has no memory? $\endgroup$
    – Julio Garcia
    Commented Oct 22, 2013 at 14:47
  • 1
    $\begingroup$ @JulioGarcia It's hard to say without knowing exactly what you saw. There are Moore and Mealy machines which can output symbols on transitions. The activity of a vending machine might be better modeled by one of those mechanisms. A vanilla DFA only accepts and rejects strings... a vending machine should "accept" any "string" of coinage. Depending on how you model the extra side effects of giving change, the kind of scratch memory needed may be none or infinite random access. $\endgroup$
    – Patrick87
    Commented Oct 22, 2013 at 16:59
  • 1
    $\begingroup$ Without seeing your example, I can't be completely certain, but I have two guesses. One is that it doesn't know how much money there is: it just assumes there's enough. You wouldn't want to build a real vending machine that way, but it's still a useful example of the concept. The other possibility is that it's not really a "pure" FSA: it's hooked up to a sensor that can get this data from "outside" the machine somehow. The machine doesn't know or care where the data comes from, and it can't store anything in the sensor (so it's not really "memory"), but it can still act on what it sees there. $\endgroup$
    – The Spooniest
    Commented May 6, 2014 at 13:48
  • $\begingroup$ The third, perhaps, is that there is a well-defined and finite amount of coins required to get the candy, (say 3) so that the machine may have states "user has input 1 token", "user has input 2 tokens" etc. $\endgroup$
    – cody
    Commented Dec 20, 2022 at 20:52
25
$\begingroup$

Turing Machines describe a much larger class of languages, the class of recursively enumerable languages. Finite state machines describe the class of regular languages.

Finite state machines have no "memory", it is limited by its states.

A finite-state machine is a restricted Turing machine where the head can only perform "read" operations, and always moves from left to right.

Take this language as an example:

$$ L = \{ a^ib^i | \ i>= 0 \} $$

Because finite states machines are limited in the sense that they have no memory, a FSM that accepts L can't be constructed.

To summarize:

Finite state machines describe a small class of languages where no memory is needed.

Turing Machines are the mathematical description of a computer and accept a much larger class of languages than FSMs do.

Turing Machines have has more computational power than FSM. There are tasks which no FSM can do, but which Turing Machines can do.

Improve this answer
$\endgroup$
4
$\begingroup$

I had the same doubt and I saw two very enlightning videos and one explanation on Quora as follows:

A finite state machine is just a set of states and transitions. The only memory it has is what state it is in. Thus, the number of memory states is... finite.

A Turing machine is a finite state machine plus a tape memory. Each transition may be accompanied by an operation on the tape (move, read, write).

I have understood from it that a turing machine uses/has a a finite state machine as part of its operating procedure, plus adding some editable memory to it.

Please watch also those two videos, they are enlightning!

https://youtu.be/gJQTFhkhwPA

https://youtu.be/E3keLeMwfHY

Improve this answer
$\endgroup$
3
$\begingroup$

As far as I understand the differences between (standard model) Turing and (standard model) Mealy Machines:

  • Turing Machines read and write on the same tape vs. Mealy Machines read on one input tape and write on another output tape
  • Turing Machines can change the "tape direction" (proceed leftwards or rightwards [or halt]) vs. Mealy Machines can only proceed rightwards (thats why there is no direction set {L,R,H} in the transition function of the Mealy Machine [it is implicitly {R}, which means no choice at all])
  • Turing Machines can halt on any tape cell vs. Mealy Machines read the complete input and then halt accepting or rejecting it
Improve this answer
$\endgroup$
-3
$\begingroup$

A Turing machine can store, as part of the tape, things it want to remember.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ It's not clear what you mean by "it" but both Turing machines and FSMs can do this so it isn't a difference. $\endgroup$
    – David Richerby
    Commented Feb 25, 2016 at 5:15
  • $\begingroup$ @DavidRicherby But an FSM can only store a predetermined amount, whereas Turing machines can store as much as they want. That is the fundamental difference. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Feb 25, 2016 at 20:45
  • 1
    $\begingroup$ @Gilles Agreed but that's not what the answer says. $\endgroup$
    – David Richerby
    Commented Feb 26, 2016 at 0:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.