In the past I often referred to the equivalence between state machines and coroutines as a kind of obvious fact that doesn't need any additional explanation. It was brought to my attention, however, that that may not always be the case.
This article therefore doesn't attempt to express and deep and ground-breaking truth, rather, it illustrates the equivalence of state machines and coroutines using a practical example.
The example is stolen from Wikipedia's article on finite state machines:
A turnstile, used to control access to subways and amusement park rides, is a gate with three rotating arms at waist height, one across the entryway. Initially the arms are locked, blocking the entry, preventing patrons from passing through. Depositing a coin or token in a slot on the turnstile unlocks the arms, allowing a single customer to push through. After the customer passes through, the arms are locked again until another coin is inserted.
Wikipedia presents the state machine in question in the following manner:
And here's my attempt to rewrite the state machine as a coroutine in Go:
December 15th, 2018
Of course, a coroutine can model any (finite) state machine, that’s not rocket science. To show equivalence, however, one also needs to show that a (finite) state machine can model any coroutine…but this is probably impossible. 😀
For example, how would you model a coroutine which acts like a Turing machine? The coroutine gets the input of the TM from an input channel, runs a secret TM in the coroutine and outputs result of the TM computation through an output channel. Good luck with that.
If you can find a way to do this, then you’d have proven that FSM is equivalent to TM (since a TM can model a FSM), but this conclusion is demonstrably false.
I don't think that your example with the Turing machine is valid here. It's not the computation of the coroutine function code itself that is captured with the FSM, just the state transitions are expressed with the FSM. In other words FSM only models the yield and resume parts of a coroutine (and you cannot encode a Turing machine into only that, probably :) ).
That's what I suppose Martin meant. As it often happens in computer science, the word coroutine is heavily overloaded, so the title of this article may be a bit misleading based on what you consider to be a coroutine :)
I guess the wording was a little bit unfortunate. The article links to wikipedia article about FSMs, but what I was talking about here were state machines as used in practice. Consider TCP state machine: It kind of looks like an FSM, however, there's additional state in the implementation, e.g. CWND.
When you think of state machines that way, they are actually Turing complete, i.e. computationally equivalent to coroutines.
Formally, the transformation from state machine to coroutine and vice versa can be done automatically: "State" corresponds to a location in a coroutine where the execution is suspended (<- or select). Additional state, such as CWND, corresponds to coroutine's local variables. "Action" corresponds to the code between two suspension points.
You might want to read about cellular automata if you look for something to model concurrency. This is even more fun.
Post preview:
Close preview