27
$\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?

$\endgroup$
  • 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 Oct 21 '13 at 21:07
  • $\begingroup$ Ok, I cheated a bit there >.>;; Gotcha! Thanks! $\endgroup$ – Julio Garcia Oct 21 '13 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 Oct 21 '13 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 Oct 22 '13 at 14:40
  • $\begingroup$ @Dai: It's more correct to say that a Turing Machine may use an arbitrarily large amount of memory. The amount used is never infinite. $\endgroup$ – reinierpost May 6 '14 at 10:53
24
$\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.

$\endgroup$
  • $\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 Oct 22 '13 at 14:47
  • $\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 Oct 22 '13 at 16:59
  • $\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 May 6 '14 at 13:48
16
$\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.

$\endgroup$
3
$\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

$\endgroup$
2
$\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
$\endgroup$
-3
$\begingroup$

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

$\endgroup$
  • 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 Feb 25 '16 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' Feb 25 '16 at 20:45
  • 1
    $\begingroup$ @Gilles Agreed but that's not what the answer says. $\endgroup$ – David Richerby Feb 26 '16 at 0:53

protected by Yuval Filmus Dec 11 '16 at 19:10

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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