5 ms·

On the Unreasonable Effectiveness of Finite State Machines

11 points by kevmo314 6y ago

chmaynard 6y ago
An off-topic question: In the declaration let door = "open"; the intended type of door is DoorState, but it could also be a string type. How does the compiler decide which is the best choice? By looking ahead?
- kevmo314 6y ago
  Ah good catch, the TS compiler can't as it types it as string that fails. let door: DoorState = "open"; works though. :) I've updated the post and a link to the TS playground.
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 ago
  Not 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 ago
    Even a linear bounded automaton will accept context-sensitive languages, which an FSM cannot.
    - kevmo314 6y ago
      The 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.

11 points by kevmo314 6y ago

An off-topic question: In the declaration let door = "open"; the intended type of door is DoorState, but it could also be a string type. How does the compiler decide which is the best choice? By looking ahead?

kevmo314 6y ago
Ah good catch, the TS compiler can't as it types it as string that fails. let door: DoorState = "open"; works though. :) I've updated the post and a link to the TS playground.

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 ago
Not 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 ago
  Even a linear bounded automaton will accept context-sensitive languages, which an FSM cannot.
  - kevmo314 6y ago
    The 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.