The idea is that we have a device with two buttons and a screen; after we press the Start button, we can press the Next button any number of times, and we see a sequence of values play out on the screen. Though the Start value is important, the fundamental structure of the sequence of values comes from the nature of the operator invoked by the Next button.
In this post, I’d like to show how such sequences can be simulated in a spreadsheet. There are many ways to do that; I’ll just show one:
In this spreadsheet, the “state” column represents the sequence of states the state machine goes through. For each state, the value in the “next” column indicates what the next state will be. The formula for the C2 cell is shown: =B2+3. That tells Excel to take the value of the current state, in B2, and add 3 to it. The formula for the B3 cell is not visible in the picture, but it is very simple: =C2. The new current state is the old next state. All the cells below B3 get their formula simply from copying and pasting the content of B3. All the cells below C2 get their formula from copying and pasting the content of C2.
Similarly, we can make a spreadsheet corresponding to:
and this is shown below:
where you can see the Excel formula used for the cell C2 – it matches the operator even if the notation is different: the notation is adapted to Excel’s needs and conventions. The formulas for the cells below are again simply copied and pasted from what is in C2. The cells in the B column are identical to those in the previous example.
You may notice that this state machine has some very interesting behavior: once the state of the state machine settles on the value “3”, then the next value of the state is also 3, and from that point on, the state will forever remain 3. This behavior is often called “steady state” in physics, and is often called a “fixpoint” or “fixed point” in mathematics.
What is especially interesting about this spreadsheet is that the steady state isn’t even particularly dependent on the start value:
Here, we use the exact same formula as before, but we used a starting value of 10 – and still got to a state of “3” in just a few steps. If you have access to Excel yourself, you may want to play with different starting values, and observe the behavior. Do you always end up with a steady state (or fixpoint)? What range of starting values will lead to this fixpoint of 3?