In this series, we’ve looked at operators in various ways. Recently, we’ve looked at state machines that invoke the same operator repeatedly, and generate a sequence of numbers in doing so. Conversely, sequences of numbers can often be modeled as a state machine. In the previous post, we showed how those kinds of state machines can be simulated rather straightforwardly in a spreadsheet like Excel. One of the examples in that post was a state machine that converged to a particular state and, once in that particular state, stayed in that same state from then on. Such operators, whose repeated invocation moves closer and closer toward a specific value, are of great practical import. For example, the state machine we looked at:
converges rapidly to a value that is the square root of the number in the first box (here 9). If you changed that number to 25, the state machine would converge to a state of 5, and if you changed the number 9 to the number 2, the machine would converge to a state of 1.4142… This is quite a practical way to compute square roots, and Wikipedia claims that this method was already known to the ancient Babylonians.
In the situations where the repeated pressing of “Next” does not get us closer and closer to a particular value, it is usually very important to keep track of how many times the button has been pushed.
This state machine:
is quite useful to generate powers of 2. When you hit the “start” button, the state is set to 1, and subsequent presses of “next” will generate 2, 4, 8, 16,… But how would I use this machine to get me ? After “start”, I’d have to press the “next” button precisely 20 times. This is not difficult, but it is very error prone.
Fortunately, counting is itself the process of generating a sequence, and it is a sequence that can be generated by a state machine in a very straightforward way. This leads us to consider the following:
In this diagram, we have a state machine on the left that generates a counting sequence: 0, 1, 2, 3, …; and the powers-of-two machine on the right that generates the sequence 1, 2, 4, 8, …, and the idea is that we can couple these two machines, so that they move in sync with each other. We might think of a big Start button that, when pressed, causes both of the start buttons shown to be pressed, and a big Next button that, when pressed, causes both of the next buttons to be pressed. When the two machines are coupled this way into a single machine with two screens, we can think of the states as being coupled also. On hitting Start, the screens show 0;1, after hitting Next we see 1;2 and after hitting Next again we see 2;4. No matter how often we hit the Next button, the state of the “+ 1” machine will always indicate how many times we’ve multiplied by 2 in the “× 2” machine. Another way of saying this is that when the state of the “+1” machine is , the state of the “× 2” machine is .
In the next blog post in this series, we’ll model the same behavior using a single state machine.