5 ms·
It sounds a bit like you are talking about a Turing machine rather than a finite automaton (the latter is much weaker than the former in computational power).
by dbaupp 14y ago
It sounds a bit like you are talking about a Turing machine rather than a finite automaton (the latter is much weaker than the former in computational power).
(Not that it matters much, your point still stands.)
- marcosdumay 14y agoThey are equivalent. None of them is weaker. And, by the way, your PC (Von Neuman architecture) is an example of finite automatum. I've seen the FA formalism used in computing theory a few times. Yet, I'm also missing whatever enlightment the author is looking for. But, if for no other reason, it's worth learning just because it's a very nice tool.
- robrenaud 14y agoRead the theory again. Finite automata are quite weak.
- aaronblohowiak 14y agoWhere 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 agorobrenaud 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 agoTuring 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 agoIndeed, 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.
- upquark 14y agoThis is factually incorrect.