4 ms·

This is a strange take. Every last program ever written is a state machine. The number of possible states a program represents is normally very, very large, an

This is a strange take. Every last program ever written is a state machine. The number of possible states a program represents is normally very, very large, and the transition rules are very complicated and often mixed up with, e.g., multiplier circuits. So we use familiar programming languages instead, which help to organize it all. A program emulating another state machine tends to raise the question why the (or anyway some) programming language is not being used to manage its complexity. So in practice we emulate only the simplest of state machines explicitly. A programmer writing such a program is sometimes said to be in a state of sin.

taeric 4y ago
Amusingly, I will push back that your take is equally strange. The point is clearly on a pattern of programming. Yes, programming is often creating tools that will have states. That is somewhat banal and doesn't help. Now, I fully grant that there can easily be an explosion of states. I still find it odd to see so much pushback to trying to force a limit on the number of states that we want to support on a UI. We seem to want to allow any number of inner states to transition on a page at any time, and then we wonder at the complexity of the interfaces that we have built up.
rhelz 4y ago
Here is a kind of bridge from the articles POV to yours: As the OP points out, state machines are very hard to develop by stepwise refinement. A "general solution" to that problem is...the universal Turing machine--a state machine which can emulate any other state machine. However, its really hard to program a Turing machine, so we invented assembly language, which is really hard to program, so we invented higher-level programming languages.... Basically, the programming languages we have are the best way we've figured out how to make state machines...
- BlueTemplar 4y ago
  I was also confused then realized that Turing machines that are allowed to write on their tape are not (always equivalent to ?) state machines. So I guess that making a state machine involves clearly separating the write-protected parts that make it from the rest of the program, and forbidding tampering ? Also, all computing is not (directly) state machines or even Turing machines : quantum computing and generally analogic computing come to mind. P.S.: Also, seems like (because of that restriction ?) you cannot have multithreading inside a state machine ?
  - jholman 4y ago
    Here are some comments from the perspective of computing science (i.e. not from the perspective of software development). There is a conceptual thing called a "finite state machine", which has no memory except a set of finite states. It can, of course, "recognize" the elements of any finite set, but the question is, what infinite sets can it recognize? There is another conceptual thing called a "Turing machine". It has all the same capabilities that an FSM has, plus the ability to read from, and write to, an infinite long tape with a finite set of symbols writable to that tape. Again, the question, what infinite sets can this conceptual machine recognize? Another machine, a push down automaton, has memory capability greater than the FSM, but lesser than the TM. Again the same question. So, yes, in this context, a TM can do anything an FSM can do, but the converse is very much not true. That said, real life computers do not have infinite tape; they are actually very very powerful FSMs. So when we talk about the applicability of these ideas to the practical day-to-day writing of software, there are several layers of metaphor involved in why we care at all.
    - BlueTemplar 4y ago
      Yeah, as I understand it, this is actually more about emulating a (much more simple) FSM on a (finite, therefore pseudo-)TM ? And so another thing that I thought would matter for software development is that you should be able to actually make the FSM write "outside of itself" without losing its FSM-ness, in the sense of not being able to later read it - which makes no sense talking generally, but does make sense in this context of emulation ?
    - KMag 4y ago
      > Another machine, a push down automaton, has memory capability greater than the FSM, but lesser than the TM. What you've written is correct, but someone who's not reading carefully might mistake "capability" for "capacity". Both pushdown automatons and Turing machines have infinite storage capacity, but the Turing machine can seek to any position in its infinite tape while the pushdown atomaton can only access the top of its infinite stack.

taeric 4y ago

Amusingly, I will push back that your take is equally strange. The point is clearly on a pattern of programming. Yes, programming is often creating tools that will have states. That is somewhat banal and doesn't help. Now, I fully grant that there can easily be an explosion of states. I still find it odd to see so much pushback to trying to force a limit on the number of states that we want to support on a UI. We seem to want to allow any number of inner states to transition on a page at any time, and then we wonder at the complexity of the interfaces that we have built up.

rhelz 4y ago

Here is a kind of bridge from the articles POV to yours: As the OP points out, state machines are very hard to develop by stepwise refinement. A "general solution" to that problem is...the universal Turing machine--a state machine which can emulate any other state machine. However, its really hard to program a Turing machine, so we invented assembly language, which is really hard to program, so we invented higher-level programming languages.... Basically, the programming languages we have are the best way we've figured out how to make state machines...

BlueTemplar 4y ago
I was also confused then realized that Turing machines that are allowed to write on their tape are not (always equivalent to ?) state machines. So I guess that making a state machine involves clearly separating the write-protected parts that make it from the rest of the program, and forbidding tampering ? Also, all computing is not (directly) state machines or even Turing machines : quantum computing and generally analogic computing come to mind. P.S.: Also, seems like (because of that restriction ?) you cannot have multithreading inside a state machine ?
- jholman 4y ago
  Here are some comments from the perspective of computing science (i.e. not from the perspective of software development). There is a conceptual thing called a "finite state machine", which has no memory except a set of finite states. It can, of course, "recognize" the elements of any finite set, but the question is, what infinite sets can it recognize? There is another conceptual thing called a "Turing machine". It has all the same capabilities that an FSM has, plus the ability to read from, and write to, an infinite long tape with a finite set of symbols writable to that tape. Again, the question, what infinite sets can this conceptual machine recognize? Another machine, a push down automaton, has memory capability greater than the FSM, but lesser than the TM. Again the same question. So, yes, in this context, a TM can do anything an FSM can do, but the converse is very much not true. That said, real life computers do not have infinite tape; they are actually very very powerful FSMs. So when we talk about the applicability of these ideas to the practical day-to-day writing of software, there are several layers of metaphor involved in why we care at all.
  - BlueTemplar 4y ago
    Yeah, as I understand it, this is actually more about emulating a (much more simple) FSM on a (finite, therefore pseudo-)TM ? And so another thing that I thought would matter for software development is that you should be able to actually make the FSM write "outside of itself" without losing its FSM-ness, in the sense of not being able to later read it - which makes no sense talking generally, but does make sense in this context of emulation ?
  - KMag 4y ago
    > Another machine, a push down automaton, has memory capability greater than the FSM, but lesser than the TM. What you've written is correct, but someone who's not reading carefully might mistake "capability" for "capacity". Both pushdown automatons and Turing machines have infinite storage capacity, but the Turing machine can seek to any position in its infinite tape while the pushdown atomaton can only access the top of its infinite stack.