Hacker News new | past | comments | ask | show | jobs | submit login
On the Unreasonable Effectiveness of Finite State Machines (kevmo314.com)
11 points by kevmo314 on Sept 23, 2020 | hide | past | favorite | 6 comments

> a computer is nothing but a finite state machine

No. That is simply not true. See 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.)

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 :)

Even a linear bounded automaton will accept context-sensitive languages, which an FSM cannot.

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.

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?

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.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact