In the last installment in this series, we showed a state machine that produced powers of two while keeping track of which power of two it was. Each time you press “next” the next power of two is produced.
The basic operators “+ 1” and “× 2” can produce quite complex behavior when coupled with state (memory).
In the above state machines, the operators acting on the exponent component of the state and the operators acting on the power component of the state are almost entirely independent and separate of each other; however, they are carefully synchronized with each other. It is quite easy to construct state machines where the components have more interaction with each other, and it is quite interesting to see what can be produced in this way.
Below is a state machine that only relies on addition and is yet able to produce squares:
As you can see, the operator that produces the next square component uses as input both the previous value of the square component and the value of the difference component. The three strands that produce the new component values are not only synchronized, they are also coupled. As we cycle through states by repeatedly pushing the “next” button, we get:
The mathematics of why these particular additions generate perfect squares is important and interesting, a topic I’m planning to get back to. In this post, I want to touch on a larger topic. State machines, using basic operations and multi-component states and cyclical activation of operators, can model very complex behavior. This is not a new insight – Charles Babbage invented something he called the Difference Engine in 1822 or earlier, but couldn’t get his design built according to the tolerances he needed (his was a machine with wheels and gear trains).
The principles underlying his design were exactly those of a state machine with simple operators operating on state. His goal was to automate the creation of mathematical and astronomical tables, which until then were computed by hand, and which he had observed to be extraordinarily error-prone and tedious work.
In our age, these ideas still apply, though their application tends to be hidden under the covers of microchips and standard software libraries.