4 ms·
> a computer is nothing but a finite state machine No. That is simply not true. See https://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarchy https://en.wi
by unhammer 6y ago
> a computer is nothing but a finite state machine
No. That is simply not true. See https://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarch...
As a simple example, try to make an FSM (which will have a fixed number n states) for matching parentheses – then I can always make a parenthesized expression of a certain size that your FSM cannot match. So you try to add some states to the FSM, now it can handle that expression. But then I wrap the expression in more parentheses and your FSM fails. However, a computer (or turing machine – or in this case even a pushdown automaton) can always match it.
(But the limitations of FSM's are also strengths – just like some people like to keep parts of their programs pure or free of I/O and feel safe when their compiler can check that, you know that the FSM itself won't eat your memory, and has a bunch of other provable characteristics.)
- kevmo314 6y agoNot if it's bounded on memory. A memory-bounded pushdown automaton will also fail but a general computer can match it. For the post I was referring to the physical computers we work with daily. I should clarify :)
- unhammer 6y agoEven a linear bounded automaton will accept context-sensitive languages, which an FSM cannot.
- kevmo314 6y agoThe point I'm trying to make is not that FSM actually can do these, but rather that this distinction is largely theoretical. In practice, even linearly bounded isn't practical because of course I can pick a sufficiently large input that will run out of tape: there's only so much information storage in the universe.