2 ms·
I'd say they're Turing complete (in common parlance) if they can reasonably viewed as a Turing-complete system that's been hobbled with an arbitrary memory limi
by foldr 4y ago
I'd say they're Turing complete (in common parlance) if they can reasonably viewed as a Turing-complete system that's been hobbled with an arbitrary memory limitation. FSAs generally can't be viewed this way as you can't just "add more memory" to an FSA. By way of contrast, consider a pushdown automaton with two stacks. While any physically real implementation of such a device will necessarily have some kind of limit on the size of the stacks, you can easily see how the device would behave if this limit were somehow removed.
It's definitely a bit fuzzy. I'm sure lots of philosophy papers have been written on when exactly it is or isn't appropriate to consider a finite computational system as a finite approximation to a Turing-complete system. In realistic everyday cases, however, it's usually clear enough what should and shouldn't count as such.
- charcircuit 4y ago>as you can't just "add more memory" to an FSA. Adding another state to a FSA adds more memory. There is no difference between a hobbled Turing machine and a FSA. Turing machines aren't a useful concept in the real world and that is okay.
- foldr 4y ago>Adding another state to a FSA adds more memory. Yes, but it also changes the state transition logic. You can't just 'add 100 more states' to an FSA in the same way that you can 'add 100 more stack slots' to a bounded pushdown automaton. As I said previously, these are somewhat fuzzy distinctions, and I'm not saying that they're easy to make mathematically precise. They do however seem clear enough in most cases of practical interest. There are many real-world computing systems that would be Turing-complete if they had unbounded memory. There are others that are not Turing-complete for more fundamental reasons than memory limitations. Again, I acknowledge that 'more fundamental' is not a mathematically precise concept.