3 ms·
It's unfortunate that the article (and Wikipedia, too), use "state machine" to refer to a finite state machines. In program semantics and formal verification, t
by pron 9y ago
It's unfortunate that the article (and Wikipedia, too), use "state machine" to refer to a finite state machines. In program semantics and formal verification, the term state machine is a common term of art, but it refers to either a finite- or an infinite- state machine, with infinite being the presumed default unless otherwise stated. If people come to associate the concept of a state machine with the useful but more limited narrowly applicable concept of a finite state machine, they may miss out on this important and general concept.
In program semantics and formal verification, a state machine is a mathematical mechanism for describing an often nondeterministic discrete (software or hardware) system as a mathematical relation, →, on states, where if `s → t` (i.e., the pair <s,t> is in the relation), then a transition from state `s` to state `t` is possible. For example, both Turing machines and the lambda calculus are often naturally described as state machines. A finite state machine is just a state machine with a finite number of states.
- braythwayt 9y agoThere are more generalized concepts of great interest, including infinite state machines and (as mentioned elsewhere in this discussion) hierarchal state machines. However... A blog post with the stated aim of alerting programmers to the opportunities for refactoring a convoluted domain model into something with more structure has to start somewhere, and leave something out. The great thing about discussions like this is that more experienced programmers such as yourself can chime in with exactly this kind of observation. I invite you to post a link or two for others to read. I'm sure the community will appreciate it.
- pron 9y agoOh, I was merely commenting on the use of the unqualified "state machines" as referring only to finite state machines. Wikipedia indeed claims this is the default meaning (i.e., finite unless stated otherwise), but I am not familiar with it being the default, and, in any event, don't think it should be, as that would be confusing.
- braythwayt 9y agoThanks for the reply! Now as to my request... Any particular essay or other resource about infinite state machines you'd care to suggest?
- pron 9y agohttps://lamport.azurewebsites.net/pubs/state-machine.pdf https://lamport.azurewebsites.net/pubs/state-machine.pdf
- lou1306 9y agoMay I chime in? A gentle introduction to process algebras [^1] shows some examples of how you can represent programs as (possibly infinite) state machines. Essentially you define some operators to compose smaller programs (aka. processes) into larger ones, hence the name "process algebra". These definitions allow you to "see" your process as a generalization of a state machine known as a labeled transition system [^2]. And then you can exploit this representation to verify properties about the process. Lots of fun! [^1]: https://pdfs.semanticscholar.org/12d9/eae1638729aeb237b5be445ee91ecdd3c5d7.pdf https://pdfs.semanticscholar.org/12d9/eae1638729aeb237b5be44... [^2]: These rules are called an operational semantics. There are other ways of giving semantics to a formal system: for instance, denotational semantics exploit recursive mathematical definitions. Each way has its pros and cons.
- pron 9y agoState machines (that contain both labeled and unlabeled transition systems) may indeed serve as operational semantics of some formalisms, but they can be denotational semantics of others, or even studied completely separately from any programming formalism. Not only process algebras, but even the lambda calculus is naturally expressed as a state machine, where the states represent the expression, and transitions represent possible reductions (lambda calculus is nondeterministic).
- kitd 9y agoAgreed. I have worked with Petri Nets before now, which I found less restrictive than FSMs (which are just a subset of PNs). But giving your classes explicit state is certainly very valuable. I even wrote a tool that would take an ASCII-art diagram of a PN embedded in the comments of a class, and generate the state definitions and methods within the class.