4 ms·

Read the theory again. Finite automata are quite weak.

• aaronblohowiak 14y ago
  Where is the infinite tape? Finite automata are as capable, in the real world, as Turing-like machines, because it is impossible to fabricate a machine with infinite storage.
  • ncallaway 14y ago
    robrenaud did not respond to the argument that the PC is a Finite Automata. His only comment was that "Finite Automata are quite weak" (in the context of the _theoretical difference_ between Turing machines and FA). He's absolutely correct. FA can compute a strict subset of what Turing machines can compute.
  • jacquesm 14y ago
    Turing machines have infinite storage by definition, no such machine has ever been built (we're using approximations), real world restrictions do not apply to imaginary constructs. If a Turing machine were not defined that way then you'd have to set some upper limit to the size of the tape and that in turn would have odd implications for what would be considered 'computable'. By making the tape infinite by definition you get much more meaningful answers about what is in principle computable and what is not.
    • mturmon 14y ago
      Indeed, we have done everything we can to provide ways to keep the illusion of running on a Turing machine going -- I'm thinking about mmap(), swapping to disk, tape robots, and databases, among others. Yes, Virginia, you can always obtain more memory.