The prior post in this series showed that we can get complex and rich behavior from combining simple operators and feeding their output back to their input (through what is called “state”, and the whole arrangement is known as a state machine).  The machine we looked at in the last post produces a sequence of squares:

and not only does it produce perfect square numbers, one after another, as the “next” button is pressed, it produces pairs of counter and square (I’m deliberately ignoring the difference component here).  So after a number of “next” presses, we might see

and a little while later

and it might occur to us that if we wanted to find the square of 37, we could hit “start” and then press “next” till the counter showed 37.  This gives us one particularly way of computing the square of 37.  Now, this may not be your favorite way, and it may not be the most efficient way.   And when it comes to computing squares, there are lots of other ways as well.

Yet the idea of generating pairs of values (here counter and square) until one comes by that has the right value for counter, and then looking at the matching square value – this is a general idea that has lots of practically useful applications.  It also allows us a broader take on what a function is.   A number goes in: “37”, and a number comes out. Though it involves operators, it does so in a rather involved way, with twists and turns.  Still – the process is reproducible.  Do the same sequence again, and the same number will come out.

The state machine of the kind we’ve shown here gets us close to the essence of what are known as primitive recursive functions.