Operators, Functions, and Properties – part 29

In this series, we’ve been looking at simple machines where pushing a button invokes an operator that changes the state of the machine.  Stopwatches, coffee makers, calculators are all examples of such machines – some simpler than others.  Many of the operators we’ve encountered are operators that work on a single number going in, and produce a single number coming out.  By stringing together these kinds of operators, we can get rich and surprising behavior.

In this post, I’d like to introduce and look at some fairly simple operators (operating on single numbers) that don’t look like arithmetic at all.

The first two act like filters.  The one on the left makes sure that the number coming out is at most 11.  Yet as long as the number going in is less than 11, it is passed through without modification.  The one on the right does a similar thing, but makes sure the number coming out is at least 3.

The symbols used here for each of these filters is intended to evoke the image of the graph of each of the functions.  I like the name lid for the operator on the left, and bottom for the name of the operator on the right.

Here is the graph for our lid function:

and here is the graph for our bottom function:

As simple as these operators may seem, if you try to find operators or functions with these descriptions on the internet, you may be surprised.  In these forms, they are not in widespread use.   Historically, there are two other functions that are in widespread use, min and max, and our bottom and lid functions turn out to be special cases of the min and max functions.  In case you’re not familiar with min and max, min stands for minimum and max stands for maximum.  The minimum of a set of numbers is the smallest of them, and the maximum of a set of number is the largest of them.

The picture above shows a min operator and a max operator, each taking two numbers as input.  Below, you’ll see how these operators can be used to build the bottom and lid operators.

As before, we’ve given the min operator two inputs, and the same for the max operator.  However, one of these inputs is fixed.  The overall effect of a fixed input of 11 using the min operator is that the result can never get bigger than 11, after all if the input is bigger than 11, the min operator will select 11 as the minimum.  If the input to the min operator is less than 11, the min operator will select that input.  (Of course, if the input is exactly 11, the min operator will produce an output of 11, and it could do so by selecting either one of the inputs.)  Similarly, the output of the max operator with a fixed input of 3 will never drop below 3.

If you are like me, these results look backwards and counter-intuitive.  It seems strange to me, at first glance, that the min operator will produce an output that is at most 11, or that the max operator will produce an output that is never below 3.  And yet, they do work as advertised.

So, do we need the bottom and lid operators if we already have the widely-known and accepted min and max operators?  Certainly, the world has survived well without these.  A full answer would have to address both the cost of introducing new notation and terminology, as well as the cost of any confusion when using the min and max operators in the configurations as shown above.

Posted in Uncategorized | Tagged , , , , , | Leave a comment

Operators, Functions, and Properties – part 28

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.

Posted in Uncategorized | Tagged , , , , , , | 1 Comment

Operators, Functions, and Properties – part 27

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 state is in blue, the buttons are red, and the operators are shown as boxes in black.  black arrows represent single numbers)

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.

Posted in Uncategorized | 1 Comment

Operators, Functions, and Properties – part 26

In the previous post in this series, we linked two state machines together, weakly, by arranging to press their Start buttons at the same time and to press their Next buttons at the same time.  As a result, we got a contraption that could crank out the following number pairs:

We will now show a single state machine that produces the same number pairs:

To make this happen, the state of the state machine consists of a pair of numbers.  As in previous posts, those components of the state are given a name – here exponent and power.  If you follow what happens with the exponent component of the state, you see that it is set to 0 when the start button is pressed, and that one is added to it each time the next button is pressed.  Similarly, the power component starts at 1 and is doubled each time the next button is pressed.  This is consistent with the two state machines in the previous post, and is consistent with the table of number pairs that we are trying to generate.  As you can see, the core operations of the state machine are relatively simple: +1 and × 2; most of the details of the state machine have to do with keeping track of what is being done to what, and what triggers what is done when.

Posted in Uncategorized | Tagged , , , , , , | 2 Comments

Operators, Functions, and Properties – part 25

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 2^{20}?  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 k, the state of the “× 2” machine is 2 ^ k.

In the next blog post in this series, we’ll model the same behavior using a single state machine.

Posted in Uncategorized | Tagged , , , , , | 1 Comment

Operators, Functions, and Properties – part 24

In the previous post in this series, we started to model recurrence relationships with state machines:

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?

Posted in Uncategorized | Tagged , , , , , , , | 1 Comment

Operators, Functions, and Properties – part 23

In this series, we’ve been looking at operators as something that modifies the state of some machine or device, usually triggered by the pushing of a button.  We’ve looked quite a bit at operators that operate on numbers, for example in this post, and connected it to the mathematics of middle school, specifically the transition from arithmetic to algebra.  We also looked a lot at operators that operate on state that isn’t just a single number; in fact, we worked through – in considerable detail – the design of a state machine for a simple four-function calculator.  In our previous post in this series, we brought the design work of the four-function calculator to a point where we can now take a break from it.  (It’s not that the design is fully done, or beyond criticism – we can actually learn a lot about black boxes by comparing a proposed model with the real thing and looking for differences in their behavior.  But it isn’t something we need to do right away.)

What I would like to do next is to apply the state machine model to what are sometimes called sequences, sometimes called series, and what are known by others as recurrence relations.  Most of us are familiar with the type of question: “what is the next number in the sequence 10, 13, 16, 19, …?” where you are supposed to notice that the numbers n the sequence are each three higher than the number preceding them.  All this relates directly to the state machine model we’ve been using:

If the state of the machine is just a number, and the button is labeled something like “Next”, then a starting state of 10 and an operator of “+ 3” will match the behavior of the sequence  10, 13, 16, 19, and pressing Next one more time will get us a state of 22.  This is shown below:

You’ll notice I’ve also added an explicit “Start” button, so we can reset the thing, and it also gives us a way to show the starting value in a static representation so we don’t have to rely on a video of the thing to see what the starting state was.  What I haven’t made explicit, but assume, is that the state is shown on a screen so we can see what the state is.

I’ll leave you with some teasers, to be followed up on later.  Can you see what the behavior of each of the following machines is?

To refresh on notation, in the second one of these, we use the notation “10 -” for “subtract from 10”, and in the third one of these, we use the notation “9 ÷” for “divide into 9”, as we introduced here.

Posted in Uncategorized | Tagged , , , , , , , , , | 2 Comments

Groupings, Shopping Lists, and Vectors: The Series

This is a series on vector algebra, but it hasn’t wrapped up yet.  Here are the installments as of now:

Quantity – Different Kinds of Numbers: Vectors – it really all started with this post.  But I didn’t know it yet at the time…

Groupings, Shopping Lists, and Vectors – part 1 – where we take off on a journey: why vector algebra might be important, and how come the traditional textbook approach sucks most of the juice out of it.

Groupings, Shopping Lists, and Vectors – part 2 – a shopping scenario as a starting point for what is essential about vectors: that you know which stuff and how much of each.

Groupings, Shopping Lists, and Vectors – part 3 – a natural notation for vectors different from that in textbooks, which we might call annotated vectors

Groupings, Shopping Lists, and Vectors – part 4 – vector addition seen as combining shopping lists or cash register receipts

Groupings, Shopping Lists, and Vectors – part 5 – vector addition as an entry point into the distributive property

Groupings, Shopping Lists, and Vectors – part 6 – extended prices: introducing inner products

Groupings, Shopping Lists, and Vectors – part 7 – various situations where inner products show up

Groupings, Shopping Lists, and Vectors – part 8 – weighted averages of test scores: matrix times a vector

Groupings, Shopping Lists, and Vectors – part 9 – matrix times a vector, shown in 3D!

Groupings, Shopping Lists, and Vectors – part 10 – matrix multiplication, starting from a shopping list

Groupings, Shopping Lists, and Vectors – part 11 – a further look at matrix multiplication

Groupings, Shopping Lists, and Vectors – part 12 – projective drawings described in terms of matrix multiplication

Groupings, Shopping Lists, and Vectors – part 13 – revisiting vectors and matrices: how do they relate?

Groupings, Shopping Lists, and Vectors – part 14 – how does this treatment compare with textbook treatments?

Groupings, Shopping Lists, and Vectors – part 15 – a look at Excel, showing extended price calculations

Groupings, Shopping Lists, and Vectors – part 16 – vector inner products, shown in Excel

Groupings, Shopping Lists, and Vectors – part 17 – showing matrix multiplication in a regular pattern using Excel

Groupings, Shopping Lists, and Vectors – part 18 – why matrices in textbooks are square.  first look at solving equations

Groupings, Shopping Lists, and Vectors – part 19 – more on solving equations and square matrices

Groupings, Shopping Lists, and Vectors – part 20 – introduction to transformations, using pounds/shillings/guineas

Groupings, Shopping Lists, and Vectors – part 21 – graphing of pound/shilling/guinea situations – showing coordinate axes that are not at right angles

Groupings, Shopping Lists, and Vectors – part 22 – more graphing of pound/shilling/guinea situations

Groupings, Shopping Lists, and Vectors – part 23 – looks at linear combinations, and a geometric model for vector addition

Groupings, Shopping Lists, and Vectors – part 24 – looks at money exchange as a vector addition

Posted in Uncategorized | Tagged , , , , , , , | Leave a comment

Operators, Functions, and Properties – part 22

In this series, we’ve lately been modeling a four-function calculator as a state machine.  A state machine moves from state to state based on operators that are invoked through button presses.  Operators  take their input, do something with it, and then produce an output.  All the information needed to produce a unique output is present on the inputs (that’s what makes it an operator).

In the previous post, we designed an operator that’s useful for implementing the “=” key of the calculator.  We’ll repeat the diagram here, but for a description you will need to refer to the previous post.

I think it is high time that I present a full design of the simple four-function calculator, even though that will make this blog post very long.  At least it will be mostly diagrams; we will have opportunity in later posts to analyze this design and to note its limitations.  In a sense, this design will bring together a lot of material that was developed earlier in this series; this includes some notational conventions – by no means is this post meant to stand alone.

Remember that we’ve been looking at a very inexpensive four-function calculator, and even so have chosen to ignore many of its keys:

Our approach has been to design a state machine: a machine with state (memory) where the state gets modified under the influence of pressing keys.  Each key invokes an operator that uses the state and modifies it as appropriate:

We’ll show the following operators in detail: the plus-key operator, the clear-key operator, the clear-entry-key operator, the equals-key operator, and the 2-key operator.  The minus-key operator, multiply-key operator, divide-key operator are essentially the same as the plus-key operator; the 0-9 key operators are essentially the same as the 2-key operator.  We start with the equals-key operator:

In this diagram, the blue lines represent the entire state, with its four named components.  Compared to the diagram above it, there is one extra component to the state – we saw the need for it here.  The black arrows represent simple values, often numbers (e.g. 0), but sometimes text (e.g. “none”) – in our presentation, numbers are distinguished from text by having all text in quotes.

Here is the clear-key operator:

In contrast with this clear-key operator, the clear entry operator will clear only some components of the state, and leave other components of the state alone:

Below is the operator for the plus key:

It may be surprise how similar this operator is to the equals key operator.  The “+” key really doesn’t do any adding, it just marks that adding is to be done in the future.  What it does do is handle any pent-up operations: if the user had pressed these keys in sequence:  C 3 × 5 +, then the pressing of the + forces the multiplication to be done, so that the calculator is left in the same state as if C 15 + had been pressed.

The digit key operators, here represented by the 2-key operator, can in some sense be the most surprising.  As we saw in earlier posts, they cause a multiplication:

To complete our presentation of the design, we show the “screen driver”: the logic that determines what is shown on the calculator’s screen.

This is a completion of sorts: we now have a design.  Soon we will find its limitations, and some of those limitations we’ll have an opportunity to fix.  For now – there’s our calculator as a finite state machine.

Posted in Uncategorized | Tagged , , , , , | 2 Comments

Operators, Functions, and Properties – part 21

In this series we’ve been looking at operators, which we have visualized as boxes with a value (or multiple values) going in, and a single value coming out.  We pictured these boxes as little machines, which sit there waiting for values to be put on their inputs so that they  can then produce a value on their output.  The work of producing these values on the output may involve calculation, or look-up, or other logic; what is key is that the inputs provide everything that is needed to determine the output.  Such operators can be combined with other operators, by connecting the output of one to the input of another.  Through such operators we can investigate and understand many of the key ideas of algebra but using a very different (and for sixth and seventh graders, a more natural) system of notation.

Lately, we have been playing with such operators to model the workings of a simple four-function calculator and seeing if the concepts and notations we’ve introduced are powerful enough for something like that.  In the last post, we showed some look-up operators.  I’d like to show another notation for the look-up operator, one which makes it look like a switch.

The box shown has four inputs: a, b, c and s; and one output: o.  The box selects one of a, b, or c to be connected through to o, and which one is picked depends on the value of s.  The labels shown in the box, at the end of the lines for a, b, c indicate the values that s is compared against.  If s has the value “fri”, then a is connected through to o; if s has the value “sat”, then b is connected through to o; if s has any other value (“else”) then c is connected through to o.  The effect is that s chooses one of a, b, and c.  Though on the surface, this box may look different from our look-up table in the prior post, it is equivalent to it.  Also, it is not essential that this box have four inputs, it could have any number of inputs on the left, one of which is to be connected through to the output based on the switch value s.

We’re now ready to take another look at the four-function calculator, and model its states and operators.

The logic that drives the calculator screen is now ready to be shown in its final form:

where the  blue line indicates, as before, the state of the machine; the value on the right is the value that is to be shown on the calculator’s screen.

In the diagram above, we are looking at what happens when the “=” is pressed.  Depending on what operation symbol was pressed before, “+”, “-“, “×” or “÷”, something needs to happen with the two numbers that have been collected (in the .LeftValue and .RightValue components of the state, respectively), based on the value of the PendingOp component of the state.  The green box on the right is the box we want to build, taking a left value and a right value and a value for the pending operator, and producing a single value, which is the result of the operation we are supposed to perform.  The diagram on the left is the contents of the green box, is one way that the green box could have been built based on the values coming in.  Basically, we have the left value L and the right value L being combined as addition, subtraction, multiplication, and division, and then one of those values is selected based on the value of op.

Designing the green box is likely to be fruitful, because we can anticipate that the actions in the green box aren’t taken only when the “=” is pressed: something similar clearly happens when you press “+” the second time in “4+7+5=” and in other cases where the four functions are repeated, even without ever pressing “=”.

We’ll expand on this idea in the next post.

Posted in Uncategorized | Tagged , , , , , | 2 Comments