Numbers and Arithmetic II
Do-It Machines
In the
previous article we used the concept of machine as a basis for understanding
certain kinds of problems and problem solving strategies. While that discussion considered problems
involving numbers and operations on numbers there was no attempt there to
explain the behavior of numbers themselves.
In this article we will begin the development of an interpretation of
numbers based on machines with the goal of providing an intuitive basis for understanding
elementary arithmetic. The concept of
number has evolved over the course of human history and within each individual
evolves over the course of his or her intellectual development. Our development in this and the following articles
reflects that evolutionary process. In
this section we begin with the concept of number as a description of some
object or system of objects.
The most common use of numbers in the everyday world is to describe the state of changing or at least potentially changing systems. I have three candy bars. At one time I had zero candy bars and in the very near future I will have two. In the fairy tale there were three little pigs. There might have been more or less and if the wolf had had his way there would have eventually have been zero. The speed of light is according to current theories an absolute constant in our universe whose value is (approximately) 299,792,458 meters/second. If the universe were different the speed might vary according to the reference frame of the observer or at least might have had a different value and in fact does have a different value if we express the speed in miles/hour instead of meters/second. If the universe, both real and conceivable, consisted of just one unchanging object then there would be no need for numbers or any other descriptive terms. Descriptions are used to distinguish differences between objects in a system of objects or between different states of a given object.
We will
attempt to capture the notion of a changing system as a kind of machine we will
call a Do-It machine. A Do-It
machine consists of two parts:
- A configuration of things called
the state of the Do-It machine;
- A device called the changer, which changes the state of
the machine.
As the
diagram indicates the Do-It machine has an Input but no Output. The input to a Do-It machine is an
instruction to the Changer to change the State in some way. The Changer reads the instruction and tries
to execute it.
Here are some
examples of Do-It machines:
- A Mobile Robot
o The
State consists of a robot positioned on some square on a sidewalk
o An
instruction for this machine is a command to move forward or backwards some
number of squares.
- A Block stacking machine
o The
State consists of a stack of some number of blocks.
o An
instruction for this machine is a command to add or remove some number of
blocks from the stack.
- A Penny Placing Machine
o The
State consists of a row of some number of pennies spaced a certain constant
distance apart.
o An
instruction is a command to add or remove some number of pennies.
Other
examples are hands raising or lowering fingers and board games. For a board game the state is the
configuration of pieces on the board and an instruction is an allowable move in
the game.
We have been
purposely vague about the nature of state so that we can apply the
concept as generally as possible. We
will make only two assumptions about these machines:
- I can decide whether or not two
states of the machine are the same.
- The machine is not random. If some instruction I causes the machine to change from
state A to state B then whenever the machine is in
state A if I feed it instruction
I it will change to state B.
In the first assumption above it is only necessary that we be able to recognize whether states of a given machine are the same. It is not necessary for our purposes to be able to recognize whether states from two different machines are equivalent in some sense. For example, if I had another penny placing machine which placed its pennies nearer together or further apart, or a block stacking machine which used blocks of a different size, I would not be required to be able to recognize any sort of equivalence between states in the corresponding different machines. In particular the kinds of conservation principles discovered by Piaget, which for example would imply that the spacing between the pennies doesnt affect the count, are not required for this analysis. We are perfectly happy to compare only rows of pennies where the spacing is the same or even live in a universe where the spacing actually could affect the number of pennies!
Our first
attempt at interpreting numbers uses the states of a Do-It machine. Given a Do-It machine we select a particular
state, which we will call the zero state and
a particular instruction, which we'll call the unit instruction. Here are
some natural choices:
- For the block-stacking machine we
choose the stack with no blocks as the zero state and the instruction
stack one block as the unit instruction.
- For the penny placing machines we
take the zero state to be the state with no pennies in the row and take
the unit instruction to be add one penny to the row.
- For the Robot machine we choose a
particular square as the start square and take as the zero state the
state with the Robot in the start square.
The unit instruction is taken to be go forward one square.
- For a fingers machine we take
the zero state to be the hand with all fingers down and take the unit
instruction to be raise one finger.
Given a
choice of Do-It machine, zero state, and unit instruction we can interpret the
whole numbers as states of the machine.
We will call the interpretation of the number n, the n-state of the machine. We
interpret 0 as the zero state, 1 as the result of executing the unit
instruction in the 0 state, 2 as the result of executing the unit instruction
while in the 1-state, 3 as the result of executing the unit instruction while
in the 2-state and so on. In general
the n-state is the state that results from executing the unit instruction n
times starting from the zero state.
Here are the
interpretations of 0,1,2, and 3 for some of the machines we've discussed
- Robot Machine
- Block Stacking Machine
- Penny Placing Machine
The concept
of number as state is probably the first to develop. How good is it as a model?
In other words how faithfully and simply do properties and behavior of
the states reflect the properties and behavior of numbers? To some extent it depends on the choice of
Do-It machine. The fingers machine for
example breaks down if we try to execute raise a finger while the machine is
in the 10-state. For another kind of
problem that can come up consider the following machine.
The state of
this machine is determined by the rotational position of a wheel with four
possible positions, conveniently labeled 0,1,2, and 3. The changer accepts instructions to rotate
the wheel some number of positions to the right or the left. We take the zero-state to be the position in
which the label 0 is on top and we take the unit instruction to be Turn 1
position to the right. Here are the
states 0 through 4
States 0 through
3 seem like reasonable interpretations of the corresponding numbers but state 4
is identical to state 0. If we keep
going we'll see that state 5 is identical to state 1, state 6 is identical to
state 2, state 7 is identical to state 3 and state 8 is identical to state 0
and so on. In general states 0,4,8,12,
... are identical as are states 1,5,9,13, ... as are states 2,6,10,14, ... as
are states 3,7,11,15,.... Using this
device as our model of numbers might lead us to believe that 0 = 4 for example.
So for the
states of a Do-It machine to serve as a model for the whole numbers we require
that the sequence of states starting at the 0-state never ends and never
repeats. For real machines of course
these requirements would be impossible to satisfy. Eventually we'll run out of blocks or pennies or the sidewalk
will end or wrap around the earth or the stack will collapse or get smashed by
a comet etc. However we can imagine
ideal versions of these machines which don't suffer from these difficulties and
even for real machines if the number of states we reach before reaching the end
or wrapping back around is sufficiently large and our experiments deal with
sufficiently small numbers we shouldn't be led too far astray. This is after all how we get away with using
our fingers to represent numbers for some period of time in our lives.
There are at least two aspects of the whole number system that the state interpretation can model well. One is the concept of a never-ending system. While we may understand that the universe is actually limited, in our imagination we can imagine that no matter how high the stack we can always add one more block or add one more penny to a chain. Another aspect of the whole numbers that states can model well is the ordering of the numbers. Many Do-It machines have a natural ordering of their states. The height of the stack or the length of the penny chain or the left to right ordering of robot positions are natural orderings for our examples above. Assuming our choice of unit instruction is such that executing it takes the machine to a larger state in the natural ordering of states then the ordering of states corresponds to the ordering of the natural numbers. Thus as n increases, the height of the stack grows, the length of the penny chain gets longer, the robot moves further to the right.
The states of a Do-It machine can also serve as notations for numbers. We will call such notations numerals. The states of a blackboard machine with the empty blackboard as 0 state and a unit instruction of Make a stroke mark is a primitive example of such numerals. Our decimal numeration system is a more sophisticated example and among other things much more concise. Regardless of what numeration system is presented we can imagine a machine that creates the successive numerals as states. These numerals are independent of any interpretation of them as numbers. Children for example can learn the pattern of the decimal numerals without any real understanding of the meaning of the notation. In the following we assume that we have such a numeration system, lets take it to be the decimal system. Our job then is to assign interpretations to these numerals.
It is not so clear how well the state interpretations can aid our intuitive understanding of the basic operations of arithmetic and their properties. In fact it is not even clear how to interpret the operations in the state model. The problem is that the arithmetic operators operate on two numbers so our interpretation would have to involve two states of the machine simultaneously but a given machine can be in only one state at a time. My robot cant simultaneously be at position 5 and 3 for example which would seem to be necessary if I were to somehow combine these states. There is a kind of work around however.
There is a way of interpreting addition in terms of states that well call the relative interpretation of addition. We can illustrate the method with a problem. Suppose TwoMileTown is 2 miles down the road from StartTown and NextTown is three miles down the road from TwoMileTown. How far is NextTown from StartTown? For this problem we take our Do-It machine to be a road marker on the road. The start state has the marker at StartTown. The Unit instruction is move the marker 1 mile down the road. Our question then becomes, what is the state of the machine when the marker is at next town?
We
know that NextTown is 3 miles down the road from TwoMileTown. Using the relative interpretation we
temporarily change our machine to take TwoMileTown as the start state and
configure the machine so that the marker is at the 3-mile position for that
machine. We then leave the machine in
that state and see what state that is relative to the original machine which
has StartTown as the 0 state. In the
diagram above the relative states are represented in the bottom part of the
figure.
We
can also illustrate the relative interpretation with an addition slide rule. The slide rule looks like this.
It
has two identically marked off rulers, one above the other. The bottom one is fixed but the top one can
slide. In terms of the example, the
bottom one represents the states relative to StartTown and the top one will be
used to represent the states relative to TwoMileTown. The result slider (also called a cursor) is used to read off
the result. To compute the position of
NextTown we configure the slide rule as follows.
We
slide the top ruler over so that its 0 state is immediately above the 2 state
of the bottom rule. This corresponds to
the fact that TwoMileTown is two miles down the road from StartTown. We then move the result slider over until
the line is over the 3-state on the top ruler.
This corresponds to the fact that NextTown is 3 miles down the road from
TwoMileTown. Then we read the state on
the bottom ruler to see what the state of NextTown is relative to
StartTown. And of course the answer is
5 = 2+3.
While
this approach leads to a reasonable addition computing device, its hard to see
how we can use this model to get much intuition about the general meaning of
addition and its properties. This leads
us to consider a somewhat more abstract model of number. In this model we interpret
number not as a state of the device but as an instruction to the device.
The idea of the instruction interpretation is quite simple. Rather than interpreting a number n to be the n-state of the machine, we interpret it to be an instruction which when executed in the 0-state causes the machine to enter the n-state and we interpret addition as the sequencing of instructions. Thus for the fingers machine the sum 2 + 3 will be represented by the instruction raise two fingers and then raise three fingers. And Then is the name we will use for the sequencing operator. We describe this more formally below.
First, in order to interpret 0, we equip every Do-It machine with a DoNothing instruction which when executed causes no change in the machine's state. Examples of the DoNothing instruction for machines we have discusses are put no blocks on the stack, don't move in either direction, don't raise or lower any fingers.
Next, in
order to make new instructions we introduce an operation on instructions which
we will call, And Then. If I
and J are instructions for a
Do-It machine M then (I;J)[1]
read I and then J is an instruction for M. To execute (I;J), M first executes I
and then executes J. For example, (Go
two squares forward; Go one square forward) is equivalent to the instruction
Go three squares forward. (Go two
squares forward; Go two squares backwards) is equivalent to DoNothing. The notion of equivalence or sameness we use for instructions I
and J is that for any state s,
the state of the machine after executing I from state s
will be the same as the result of executing J from state s. For example, executing (Go two
squares forward; Go one square forward) when the robot is on square 5 leaves
the robot on square 8 and executing Go three squares forward with the robot
on square 5 will also leave the robot on square 8 and so the two instructions
leave the robot in the same final state and this will be true no matter what
the beginning state.
If the And
Then operation seems a lot like the Connection
operation on I/O-machines then your intuition is sound. In fact there is a way to view Do-It
machines, instructions, and the And Then
operation so that the correspondence is exact though it may seem a little
strange. When you're riding in car you
usually think of the world as being fixed and the car and you changing
within the unchanging world. But if you try you can think instead that you
and the car are fixed and the world including the road and the trees and fences
and the sky and all the rest is being change by moving past you.
The idea is the same here.
The usual way of viewing an instruction is as an input to a Do-It machine
that then acts on the instruction possibly changing its state.
But if you
try you can think of the Instruction
as the machine and the State of the
Do-It machine as the input, which the Instruction acts on to produce a new
state.
For
example we can view me and the dress state of my feet as a Do-It machine. If Im in the state of bare feet and I
execute the put on socks instruction
then I change to my socked feet state.
On the other hand we can view the put on socks instruction as the
socker machine that we talked about in the previous article, which takes me
with bare feet as input and produces me with socked feet as output. Under this instruction as input/output machine
interpretation, the result of sequencing instructions I and J looks like:
I J State
C State
B State
A
The Do-It machine starts in State A. We execute instruction I, which causes the machine to enter State B, and then we execute J which causes the machine to enter State C. This exactly corresponds in our input/output interpretation of instructions to connecting the I machine to the J machine. This idea of switching the roles of the operator and the operand is extremely useful and is associated with the mathematical term duality because of the two ways we have of viewing operand and operator. Thus an instruction can be viewed as an input or as a machine. Note that under this dual interpretation the DoNothing instruction becomes the identity machine.
We next point
out properties of And Then analogous
to the laws of connection noted in the previous chapter. Using the correspondence between And Then
and connection we could derive these laws immediately from the laws of
connection. However it will be about as
easy and more instructive to observe why they're true directly. The first is the grouping law:
Suppose I,J,
and K are instructions for a Do-It machine M then ((I;J);K ) is equivalent to
(I;(J;K)). In other words how we group
the instructions doesnt affect the final result.
As an example consider a laundry machine that cleans clothes. Take I to be the instruction Wash the laundry, J to be the instruction Dry the laundry, and K the instruction Fold the laundry. Then ((I;J);K) is the instruction Wash and dry the laundry and then fold the laundry. (I;(J;K)) is the instruction Wash the laundry and then dry and fold the laundry. In either case the instruction means first wash the laundry then dry the laundry and finally fold the laundry. Whether we group drying with washing or drying with folding or just treat them as three independent operations makes no difference to what is actually done.
To prove the grouping law formally, let s be any starting state for the machine. Suppose executing I causes the machine to go from s to s, that executing J takes the machine from s to s, and that executing K takes the machine from s to s. Suppose the machine is in state s and we execute ((I;J);K). To execute this instruction we first execute (I;J). To execute (I;J) we first execute I, which takes the machine from state s to state s, and then execute J which takes the machine from state s to state s. So executing (I;J) takes the machine from s to s. Finally, executing K takes the machine from state s to s. So ((I;J);K) takes the machine from s to s. Ill leave it to you to argue in a similar way that (I;(J;K)) also takes the machine from state s to s. [Hint: start by showing that (J;K) takes s to s.] Thus for any state s, executing ((I;J);K) in start state s leaves the machine in the same state as executing (I;(J;K)) in start state s. So the instructions are equivalent.
As we would
expect based on our experience with connecting input/output machines, the order
in which the instructions are executed definitely can make a difference. Clearly the result of washing and then
drying the laundry is very different than the result of drying and then washing the laundry!
The identity law for And Then states that for any instruction I, (I;DoNothing) is equivalent to I and (DoNothing;I) is equivalent to
I. To prove this let s be any state and
suppose I takes the machine from state s to state s. Suppose the machine is in state s. To execute (I;DoNothing) we first execute I, which takes
the machine from s to s and then execute DoNothing which leaves the
state in s. Thus (I;DoNothing) takes
the machine from state s to state s.
Similarly you can show that (DoNothing;I) takes the machine from s to
s. [Hint: Executing DoNothing when the machine is in state s leaves the
machine in state s.] Thus for any state
s the instructions I, (I;DoNothing), and (DoNothing;I) result in the same
state. So the instructions are
equivalent.
Now let M be
some Do-It machine and let I be the unit instruction for M, For each numeral n starting with 0 we construct an
instruction In for M as follows. We take I0 to be the DoNothing instruction for M. I1 is I. I2 is (I1;I) =
(I;I). I3 is (I2;I)
= I;I;I. And so on. In+1 is (In;I) = (I;I;
... ;I) where I is repeated n+1 times.
Thus for our Robot machine we interpret 0 as stay put, 1 as Go forward
1 square, 2 as Go forward one square and then Go forward one square, 3 as
Go forward one square and then Go forward one square and then Go forward one
square. So in general the effect of In is to send the robot forward n squares. We call these instructions the whole number
instructions for M. We call
In the instruction interpretation of n for M.
Notice that there is a direct correspondence between the state interpretation and the instruction interpretation of n: the result of executing In with the machine in the 0-state is the n-state.
It follows from this observation and the assumption that the states do not repeat that the instructions do not repeat.
We next observe certain properties of the whole number instruction which follow from the way they are constructed. The first observation is that the whole number instructions are constructed by a sequential process which starts with the DoNothing instruction as I0 and then constructs each successive instruction by sequencing the previous instruction with I1. The whole number instructions are the instructions which appear at some point in this process. This implies that for any two whole number instructions Im and In one of three possibilities must hold: In and Im appear at the same point in the construction in which they are identical; Im appears before In in the construction; In appears before Im in the construction. This will allow us to use order of appearance to define an ordering of the constructions.
The next observation depends on the fact, stated in the grouping law, that we can group the instructions in a sequence any way we like without changing what the instruction does. Now let Im be some whole number instruction. Then we can view the construction of the instructions constructed after Im as in the following.
I0 , I1 , (I1
; I1) = I2 ,
, Im , (Im ; I1) = Im+1, (Im ; (I1 ; I1))
= (Im ; I2) ,
,
(Im ; Ik) ,
From this we can conclude that if Im and Ik are whole number instructions then (Im ; Ik) is also a whole number instruction, that is there is an n such that (Im ; Ik) =In. Further since states do not repeat the n is unique. This is an example of a closure principle. This one says that the collection of whole number instructions is closed under sequencing. (You cant get out of the whole number instruction room by sequencing two of them.)
Third let Im and In be two whole number instructions and assume Im appears before In. Then In must appear at some point in the process which generates the successive states starting from m:
Im , (Im ; I1) = Im+1, (Im ; (I1 ; I1))
= (Im ; I2) = Im+2 ,
, (Im ; Ik) = In
,
From this together with the first observation we see that for all Im and In, either Im = In, or for some k, (Im ; Ik) = In , or for some k,
(In ;
Ik) = Im.
For any numerals m and n, if Im =
In then m = n. For whole numbers instructions Im
and In there is a unique k such that (Im ; In)
= Ik We define the ordering of the whole
number instructions by: For whole
numbers instructions Im and In, Im < In
if Im appears
before In in the construction of the whole number instructions. If
Im < In we
also write m < n. For all whole number instructions Im
and In exactly one of the following holds: For all whole number instructions Im
and In , If Im
< In then there
is a unique k such that (Im ; Ik) = In.
In this case we write k = n m
Having interpreted numbers as instructions we interpret addition as the And Then operator. Thus (m + n) is interpreted by (Im;In) and = to the unique k such that (Im ; In) = Ik
In the
diagrams below we have represented the robot instructions I0, I1,
I2, and I3 as arrows which point in the direction the
robot moves and whose length is the distance by which the robot moves.
I1
This provides
us with a nice geometric interpretation of addition. We place the two arrows corresponding to the numbers head to tail
and take the sum to be the arrow from the head of the first to the tail of the
second. For example, to add 2 and 3
We thus take (2 + 3) to be 5.
What properties
of addition can we observe from the sequencing interpretation of addition? The associative
law of addition follows immediately from the grouping law of
sequencing. (i + (j + k)) is
represented by (Ii;(Ij;Ik)) which is
equivalent to ((Ii;Ij);Ik) by the grouping
law, and the latter represents
((i+j)+k).
The identity law of addition states that for
all numbers m, (0 + m) = m and (m + 0) = m.
This follows
immediately from the identity law for the DoNothing instruction. (0 + m) is
represented by (I0 ; Im) = (DoNothing ; Im) which is equivalent to
Im which represents m and similarly for (m + 0).
The commutative law of addition states that
for all numbers m and n, (m + n) = (n + m).
Now this does not follow so immediately. Remember that it is not in
general true that (I;J) is equivalent to (J;I) for any old instructions I and
J. (The example we gave earlier was
that washing followed by drying is not equivalent to drying followed by
washing.) So the fact that (Im;In)
is equivalent to (In;Im) depends something special about
instructions representing numbers. We
note two special cases when (I;J) is equivalent
to (J;I). One is when either I or J is
the DoNothing instruction.
(DoNothing ; J) = (J ; DoNothing) = J
The other is
when I is equivalent to J.
(I;I) = (I;I)
Did you see that we switched the order of the two occurrences of I in the equation above? Probably not! To make it clearer, lets agree that Do-It machines never care about the color of an instruction. We can then use color to follow what happens to instructions when we move them around the same way a doctor uses radioactive isotopes to trace chemicals in your blood.
(I;I)=( I;I)
For example from the point of view of the machine:
(Go forward 1 square ; Go forward
1 square) is the same instruction as:
(Go forward 1 square ; Go forward 1 square)
These special cases plus the grouping law imply that in any sequence of identical instructions we can shuffle the order any way we like. For example,
((I;I;I);(I;I)) = (I;I;I;I;I) = ((I;I);( I;I);I) = ((I;I);(I; I);I) = (I;( I;I);( I;I)) =
(I; (I; I); (I; I)) = (( I;I); ( I;I); I) = ((I; I); (I; I); I) = (I; (I;I);(I;I)) =
(I; (I;I);(I;I)) = ((I;I);(I;I;I)))
Now taking I to be the unit instruction for our machine, ((I;I;I);(I;I)) is our interpretation of 3+2 and ((I;I);(I;I;I))) is our interpretation of 2+3. In general, for any m and n greater than 0, the interpretation of m+n will look like ((I; ;I);(I; ;I)) where the green Is are repeated m times and the red Is are repeated m times. Then by shuffling we can see that this is the same as
((I; ;I );(I; ;I)) which represents n+m. The identity law shows that the interpretation of n+0, (In;DoNothing), is equivalent to (DoNothing; In) which represents 0+n.
Now that weve
interpreted addition in terms of instructions and used that interpretation to
verify the basic properties of addition we move on to subtraction.
Subtraction is about unadding. If adding is putting in then subtracting is taking out. If adding is going forward then subtracting is going backward. If adding is turning a wheel to the right then subtracting is turning the wheel to the left. So what we need in order to talk about subtraction is the notion of an un-instruction. For example, Go backwards two squares is the un-instruction for Go forward two squares and Remove two blocks from the top of the stack is the un-instruction for Put two blocks on the stack. Now there are a couple of issues with un-instructions which we need to take up before we go on. These issues also relate to the notion of un-machine for input/output machines but we chose to ignore them in the previous article. The issues have to do with when an uninstruction exists and on what states it can be executed. (The analogous issues for un-machines are when an un-machine exists and on what input is it defined.)
Well start by presenting a pictorial representation of an instruction. Executing an instruction takes the machine from whatever state its in before the instruction is executed to some possibly different state. We can picture this by representing the starting and finishing states on two parallel lines and representing the instruction by a collection of arrows each of which takes some before state to some after state. Heres an example for the Put two blocks on the stack instruction.
From the diagram we see that Put two blocks on the stack takes the 0-state to the 2-state, the 1-state to the 3-state, the 2-state to the 4-state and so on. To see what Put two blocks on the stack will do when the machine is in a given state you find the state on the top line and follow the arrow to find the resulting state on the bottom line. What does the diagram for the un-instruction look like? Well it has to do just the opposite of what the instruction does. In this case it needs to take the 2-state to the 0-state, the 3-state to the 1-state and so on. To get the diagram for the uninstruction all we have to do is turn the arrows around.
When we look at the diagram for the Remove two blocks from the stack instruction we notice that there are no arrows for states 0 and 1. Well that makes sense. If the stack has fewer than two blocks on it than you cant remove 2 blocks. What will the machine do if there are fewer than two blocks and we try to execute the Remove two blocks instruction? We can imagine that it makes an obnoxious noise and flashes lights and puts some weird symbols on a screen like calculators do when you divide by 0. But it cannot execute the instruction! Thus in order to consider un-instructions we must accept the idea that there are instructions for which there are states in which the instruction cannot be executed. In reality we run into this situation all the time. You are driving your car and want to make a turn onto a one-way street going the wrong way. You cant do it and if you try youll get a ticket or have a horrible accident.
Well say that a state s is acceptable for an instruction I if I can be executed when the machine is in state s. So for example, the acceptable states for the Remove two blocks. instruction are the states in which the stack of blocks has at least two blocks. States in which the stack has fewer than two blocks are unacceptable. In general well say that a state t is a target state for instruction I is there is some state s such that executing I in state s results in state t. In this case we may say that t is the target of s under I. In terms of our arrows diagrams the target states are the ones hit by an arrow shot by an acceptable state.
We can always put two blocks on the stack so all states of the stack are acceptable to Put two blocks on the stack. On the other hand after executing Put two blocks on the stack the stack will always have at least two blocks on it, so the target states for Put two blocks on the stack are the states with at least two blocks. If an instruction has an un-instruction the acceptable states for the un-instruction are the target states of the instruction and the target states of the un-instruction are the acceptable states of the instruction. So the acceptable states for Remove two blocks will be states with at least two blocks and all states will be target states.
This realization that not all states may be acceptable to a given instruction requires us to slightly modify our definition of what it means to say two instructions are the same to require that the acceptable states for the two instructions be the same.
Instructions I and J are the same if:
- The acceptable states of I and J are the same.
- Whenever s is an acceptable state for I and J then the result of executing I in state s is the same as the result of executing J in state s.
Does every instruction have an uninstruction? If I do something can I always undo it. How many times have you wished that was true! Unfortunately its not. There are at least two possible reasons why we might not be able to undo an instruction. One is that while we might know what wed like to do, were not physically able to do it. An example of this might be dropping and smashing a piece of fine china. I know what the plate looked like but I cant reconstruct it from all the little pieces. Another possible reason for being unable to undo something is that I dont actually know what the previous state was. Most o us have at one time or another taken something apart, perhaps a toy or an appliance or (in my case) an automobile in order to see how it works or to fix some problem, only to realize after weve got the pieces piled on the floor that we have no idea how the parts are supposed to fit back together. There are many ways the parts could be put back together but I dont know which one is the correct one! This second case is the one that will interest us here.
Consider the instruction Remove all the blocks from the stack. The arrows diagram for this instruction looks like
Does this instruction have an uninstruction? Lets try turning the arrows around.
The problem with this diagram is that we have more than one arrow coming out of state 0. (In fact there are lots of them!) Which one do we follow to undo the result of remove all blocks? If we find an empty stack after all the blocks were removed how can we know how many blocks were on the stack before they were removed? We cant! So for the example of the Remove all blocks instruction there is no un-instruction. In general, for an instruction to have an un-instruction the instruction cant take two different starting states to the same result state.
We summarize the observations we have made above in the following definition and facts.
We say
instruction J is an un-instruction for instruction I if
So for example
Remove the top two blocks from the stack is the un-instruction for Put two
blocks on the stack because:
- If I put two blocks on the stack and
then take two blocks off the stack the result will be to leave the stack
unchanged.
- The acceptable state for Remove the
top two blocks from the stack are the states in which there are at least
two blocks and these are exactly the target states of Put two blocks on
the stack.
We have the
following facts about un-instructions:
As an example of
the first point, since putting 2 blocks on a stack with 7 blocks results in a
stack with 9 blocks, removing 2 blocks from a stack with 9 blocks must result
in a stack with 7 blocks. In terms of
the arrow diagrams this fact just says to get the arrow diagram for the
un-instruction for I just turn the arrows of Is arrow diagram around.
As an example of
the second point, if putting 2 blocks
on the stack results in a stack with 9 blocks then there must have been 7
blocks on the stack before putting the 2 blocks on. Theres no different state
of the stack that could have resulted in 9 blocks on the stack. If there were then we wouldnt know how to
undo putting two blocks on the stack.
As an example of
the third point, any instruction that undoes putting two blocks on the stack
must be equivalent to the take two blocks off the stack instruction.
As an example of
the fourth point, since remove two blocks from the stack undoes put two
blocks on the stack we know that put two blocks on the stack undoes remove
two blocks from the stack. In terms of
the arrow diagrams this just says that if you turn the arrows around and then
turn them around again you get the original diagram back.
Lets prove the
facts above in the general case.
- Suppose s has target t under I. Since J is an un-instruction of I we
know that the result of executing (I;J) in state s leaves us back in state
s. To execute (I;J) in state s we
first execute I in state s which results in state t and then we execute J
which must result in state s. So,
executing J in state t must result in state s.
- Suppose I has an un-instruction J and
states s1 and s2 have the same target t under I. By the previous fact we know that s1 must be the target of t
under J and we know that s2 must (also) be the target of t under J so s1
and s2 must be the same.
- Suppose J and K are both un-instructions
for I. From the definition of
un-instruction the implies that the acceptable states of J and K are the
same because they are exactly the target states of I. We just have to show that J and K must
have the same result for the target states of I. Let t be a target state of I and let s
by the state which targets t under I.
We know from the previous fact that there is only one such state. We know from the first fact then, that
s must be the target of t under J and s must (also) be the target of t under
K. So J and K have the same result
for all the target states of I.
- Suppose J is the un-instruction for I. From the definition of un-instruction, the acceptable states for J must be the target states of I and by the first fact each state acceptable to I will be the target under J of its target under I. So the acceptable states for I are exactly the target states of J as required. Also, if t is the target of s under I, then by the first fact, s is the target of t under J and so t is the target of t under (J ; I). Thus (J;I) = DoNothing on the states acceptable to J.
- DoNothing clearly has the same acceptable states as itself and for any state s acceptable to DoNothing, s targets s so (the target) s targets (the source) s under DoNothing
As we discussed in connection with cupcakes and ice-cream sundaes we can undo a sequence of instructions by undoing each of the instructions in the reverse order in which they were executed. Thus to undo the result of put on your socks and then put on your shoes you take off your shoes and then take off your socks.
The general fact is: Suppose I and J are instructions with un-instructions un-I and un-J.
Then (un-J ; un-I) is the un-instruction for (I ; J).
Heres a proof. First let s be any state acceptable to (I ; J). Suppose t is target of s under I and u is
the target of t under J. Then u is the
target of t under un-J and s is the target of t under un-I and so s is the
target of u under (un-J ; un-I). This
shows that ((I ; J);(un-J;un-I)) = DoNothing on states acceptable to (I ; J). It remains to show that the states
acceptable to (un-J ; un-I) are exactly the targets of (I ; J). The argument we just gave shows that any
target of (I ; J) is acceptable to (un-J ; un-I). Suppose u is acceptable to (un-J ; un-I). Let t be the target of u under un-J and let
s be the target of t under un-I. Then t
is the target of s under I and u is the target of t under J so u is the target
of s under (I ; J). Thus the states
acceptable to (un-J ; un-I) are exactly the targets of (I ; J).
We now define a subtraction operation for instructions. Suppose I, and J, are instructions for some DO-IT machine and un-J exists. Then we define I subtract J also written I J to be the instruction (I ; un-J).
So if I is put on your winter clothes and J is take off your hat then executing I J would leave you in a state with all your winter clothes except your hat on.
Now we can use subtraction of instructions to represent subtraction of numbers. Suppose we have a Do-It machine with a unit instruction I1 which has an un-instruction un-I1. We will write I-1 for un-I1. Recall that we define I0 to be the DoNothing instruction, I2 to be (I1;I1), I3 to be (I1;I1;I1 ) and so on. Similarly we define I-2 to be (I-1;I-1), I-3 to be (I-1;I-1;I-1) and so on.
For the block
stacking machine I-1 is Remove one block, I-2 is equivalent to Remove two blocks, and in general I-n is equivalent to Remove n blocks.
For our robot machine I-n
is Move backwards n steps.
The diagrams
above show the results of executing In and I-n for n =
1,2, and 3 for the robot machine with the robot starting in the middle square of
the diagram. Note that I-1
is un-I1 and un-I2 = un-(I1;I1) = (un-I1;un-I1)
= (I-1;I-1) = I-2 and un-I3 = un-(I1;I1;I1)
= (un-I1;un-I1;un-I1) = (I-1;I-1;I-1)
= I-3, and so on. In
general: I-n = un-In
and In = un-I-n
.
We will call these new instructions, i.e., instructions of the form I-n, negative instructions. We will call instructions of the form Im where m is greater than or equal to 0, non-negative instructions, and where m is greater than 0, positive instructions. We are going to interpret (n m) by (Im;I-n).
For any m,n If n < m then (Im ; I-n ) = Im-n If m = n, (Im ; I-n ) = I0 If m < n then
(Im ; I-n )
= I-(n m )
Before proving this in general lets work through some examples. Consider (I4 ; I-2 ). For our block machine this is the instruction
Stack 4 blocks and then un-Stack two blocks. Of course this is equivalent to I2, Stack two blocks. We can see this from the definitions as follows. I4 = (I1;I1;I1;I1 ) and I-2 = (I-1;I-1). Here weve colored the positive unit instructions and the negative unit instructions red. Since I-1= un-I1, (I1; I-1) = DoNothing. So, remembering that we can group sequences of instructions any way we want and that we can always remove DoNothing from a sequence of instructions without changing the instruction we have,
(I4 ; I-2 ) = ((I1;I1;I1;I1);(I-1;I-1)) = (I1;I1;I1;(I1;I-1);I-1) = (I1;I1;I1;DoNothing;I-1) = (I1;I1;I1;I-1) = (I1;I1;(I1;I-1)) = (I1;I1;DoNothing) = (I1;I1) = I2 .
The general idea in simplifying a sequence consisting of a positive followed by a negative instruction is to cancel pairs of positive and negative unit instructions (blue and red instructions) until weve canceled all the negative instructions or all the positive instructions or both. As examples of the latter two cases consider (I2 ; I-4 ) and (I2 ; I-2).
For the first we have,
(I2 ; I-4 ) = ((I1;I1);(I-1;I-1;I-1;I-1)) = (I1;(I1;I-1);I-1;I-1;I-1) = (I1;DoNothing;I-1;I-1;I-1) = (I1;I-1;I-1;I-1) = ((I1;I-1);I-1;I-1) = (DoNothing;I-1;I-1) = (I-1;I-1) = I-2 .
For example, the instruction Stack two blocks and then Un-stack four blocks is equivalent to the instruction Un-stack two blocks.
For (I2 ; I-2), we have
(I2 ; I-2) = ((I1;I1);(I-1;I-1)) = (I1;(I1;I-1);I-1)
= (I1;DoNothing;I-1)
= (I1;I-1) = DoNothing
Thus, Stack two blocks and then Un-stack two blocks is equivalent to doing nothing. (Of course we didnt really need to go through the primitive cancellation process because we know already that I-2 = un-I2.)
Next we prove the result in general and illustrate it with the robot machine.
For n < m, we have defined (m n) to be the unique k such that
(In ; Ik ) = Im so (In ; Im-n ) = Im
(Im ; I-n ) = ((In ; Im-n ) ; I-n ), substituting (In ; Im-n ) for Im
= ((Im-n ; In) ; I-n ),
Sequencing whole number instructions is commutative
= (Im-n ; (In ; I-n )), Regrouping
= (Im-n ; DoNothing)
, I-n is un-In
= Im-n , identity principle.
For n = m we have
(Im ; I-n ) = (Im ; I-m ) = DoNothing, because I-m is un-Im
Finally, for m < n, we have In = (Im ; In-m ) = (In-m ; Im) so
I-n = un-In = un-(In-m ; Im) = (un-Im ; un-In-m ) = (I-m ; I-(n m))
(Im ; I-n ) = (Im ; (I-m ; I-(n m))), substituting for In
= ((Im ; I-m ) ; I-(n m)), regrouping
= (DoNothing ; I-(n m)), I-m
is un-Im
= I-(n m)), identity principle
For m < n, (Im ; I-n ) = I-(n m) (I2 ; I-4 ) = I-2 (2 + -4) = -(4 2) = -2
We now interpret the subtraction operation, n m, by the instruction In Im = (In ; I-m). For example the following shows the instruction and state interpretations of 4 3 for the robot machine.
(I4;I-3) moves the robot 4 squares to the right and then moves it 3 squares to the left for a net change of 1 square to the right.
So far we havent said anything about what practical use addition and subtraction have. The primary use of addition is to determine what effect a given change in state will have. For example, suppose I have 3 apples in a basket and I add 7 more apples to the basket? In terms of our machine model we have a basket of apples machine with a start state of no apples and a unit instruction Add 1 apple to the basket. So our problem can be stated as What is the effect of executing the I7 instruction (add 7 apples) when the basket is in the 3 state (has 3 apples)? We can state the method for solving this type of problem as a general principle.
Addition method principle: If a Do-It machine
is in the m-state and we execute In then the result will be the (m+n)-state.
Proof: Executing Im from the 0-state puts the machine in the m-state. So executing In from the m-state is equivalent to executing (Im;In) = Im+n from the 0-state which puts the machine in the (m+n)-state.
For the apple problem above, the starting state is 3, n is 7, so the final state will be the (3+7)=10-state.
The primary importance of subtraction is in solving problems of the form: How do I get from here to there? In terms of Do-It machines this problem takes the form: What instruction do I execute to change the state of my machine from its current state to a desired state? The method follows from the following proposition.
For any m , n (Im ; (In ; I-m )) = In .
Proof: (Im
; (In ; I-m )) =
((Im ; In ) ; I-m ) by the grouping law
= ((In ; Im ) ; I-m ) , because sequencing whole number
instructions commutes
= (In ; (Im ; I-m )) , by
the grouping law
= (In ; DoNothing ), because I-m = un-Im
= In , by the identity principle.
For example, I have 3 apples in my basket and I want 10. How many do I have to add? In terms of our apple basket machine, were in state 3, we want to be in state 10, what apple adding instruction should we execute?
Subtraction method principle 1: If a Do-It
machine is in the m-state then executing (In ; I-m) will put the
machine in the n-state.
Proof: Executing In from the 0-state puts the
machine in the n-state. So, using the
proposition above, executing (Im ; (In ; I-m )) will take the machine from the 0-state to
the n-state. Executing Im will take the machine from the 0-state to
the m-state so executing (In ; I-m ) must take the machine from the m-state to
the n-state.
For our apple problem this principle tells us that to get the basket in the state with 10 apples we execute (I10 ; I-3 )= I10 3 =I7. As another example, illustrated below, if our robot is in square 1 and we want to move it to square 4 we execute I(4-1) = I3 , which will move the robot three squares to the right.
We can also
use subtraction to solve problems of the form: If executing Im puts
the machine in state n what was the state of the machine prior to executing Im. For example, after putting 7 apples in my
basket I had 10 apples. How many apples
did I have before putting the 7 apples in?
Subtraction method principle 2: If executing
Im puts the machine in state n then executing I-m from state n
puts the machine in the state it was in prior to executing Im .
Proof: Let s be the state of the machine prior to executing Im . Then s targets n under Im so n targets s under I-m .
So, for our apple basket example, if after putting in 7 apples we have 10 apples, then prior to putting in the 7 apples there were (10 7) = 3 apples.
In the examples we have given applying the two subtraction principles, the target state, n, has been greater than the source state, m. Now you might ask what do the principles mean in the case when the source, m, is greater than the target, n? Lets consider some examples of what happens when we attempt to apply the two principles in the case that n < m.
As an example of the first principle in this case suppose that I have 7 apples in my basket (My machine is in the 7 state) and I want to have 5. Heres a case where the target is less than the beginning state. The first principle tells me to execute (I5 ; I-7) = I-2 which for my apple basket machine is the instruction Remove 2 apples from the basket. This is a perfectly reasonable instruction and solves my problem.
Now lets consider an example of the second principle for this case. Consider the problem: After adding 5 apples to the basket there were 3 apples in the basket. How many apples were in the basket before adding the 5? Obviously this is a nonsense problem and that shows up when we attempt to apply I-5 , Remove 5 apples, to a basket with only 3 apples in it. For the apple basket machine, the 3 state is not an acceptable state for I-5 .
On the other hand consider the analogous problem for our robot machine assuming the sidewalks extends in both directions. For this machine there are states corresponding to the negative instructions. We will label these negative states with the label of the negative instruction which when executed in state 0 produces the negative state. Thus for this machine there is a state, the 2 state, which targets the 3 state under I-5 .
All of this of course is leading us to the terrifying topic of Negative Numbers. Lets review how we got here. We started with an unending sequence of numerals 0, 1, 2, . We wanted to assign interpretations to these numerals. We call interpretations of numerals numbers. The simplest interpretation is to interpret numbers as states of a machine. In fact the numerals themselves can be taken to be the states of a machine. The state interpretation accounted for certain properties but not the operators. This led us to the instruction interpretation under the sequencing operation ;. This accounted nicely for addition but needed to be extended to include the negative instructions in order to account for subtraction. For some machines these negative instructions have corresponding states and for others they do not. However, these are perfectly good instructions for all our machines and so it doesnt seem fair that they shouldnt be associated with numbers just because some Do-It machines dont happen to have corresponding states.
We now rectify this injustice by introducing the negative whole numbers -1, -2, -3, interpreted as the negative instructions I-1, I-2, I-3, . In using negative numbers to solve problems we must remember that for some of the machines were interested in, like the apple basket machine, there are no negative states and so if the solution to a problem leads us to require a negative state for such a machine we conclude that the problem has no solution for that machine.
The fact that a mathematical model of a real problem may produce a solution that does not correspond to an actual solution of the real problem should not come as a surprise. This can occur with positive numbers. Suppose that the mathematical model of a problem involving apples produces a solution that requires me to put 1000 apples in the apple basket and suppose my apple basket only holds 100 apples. Our model assumes that we can always add one more apple but in reality this is only true up to state 99. The mathematics is still useful, its just that rather than giving a solution to the actual problem it gives the extremely useful information that as currently configured my actual problem has no actual solution. So I need to get a bigger basket or change the specification of the problem in some other way.[2]
The collection of non-negative and negative whole numbers is called the integers. We next extend our interpretation of addition and subtraction to all the integers and consider to what extent previously obtained results for the whole numbers generalize.
We start by interpreting addition for the integers. There are four cases: m + n, m + -n, m + -n, and -m + -n
(m + n) is interpreted as (Im ; In) = Im+n .
(-m + -n) is interpreted as (I-m ; I-n) =
(un-Im ; un-In) =
un-(In ; Im) =
un-(Im ; In) = I-(m+n)
(m + -n) is interpreted as (Im ; I-n) which as shown earlier, =
I0 , if m = n
I(m n) , if n < m
I-(n m) , if m < n
(-m + n) is interpreted as (I-m ; In) . We consider 3 cases.
Case m = n:
(I-m
; In) = (I-m ; Im) = I0 on states acceptable to I-m
Case m < n: Then In = (Im ; (In ; I-m)) = (Im ; I(n-m))), so,
(I-m ; In) = (I-m ; (Im ; I(n-m))) =
((I-m ; Im ); I(n-m)) =
(I0 ; I(n-m)) on states acceptable to I-m , =
I(n-m) on states acceptable to I-m .
Case n < m: Then Im = (In ; (Im ; I-n)) = (In ; I(m-n))), so,
I-m = un-(In ; I(m-n))) = (un-I(m n) ; un-In) = (I-(m n) ; I-n), so
(I-m ; In) = ((I-(m n) ; I-n) ; In) =
(I-(m n) ; (I-n ; In)) =
(I-(m n) ; DoNothing), on states acceptable to I-m [3],=
I-(m n) , on states acceptable to I-m
Albert Einstein is supposed to have said "Everything should be as simple as possible ... but no simpler." The relevance to our situation is that when interpreting addition of integers for a machine without negative states we have to add provisos concerning acceptable states. We can state the addition rules for integers more simply if we restrict our interpretations to devices with negative states (so that all states are acceptable for all instructions.) Noting that Im is the interpretation of m and I-m is the interpretation of -m we have the following table.
Note that for Do-It machines with states for all integers, addition is commutative, that is for all integers j and k, (j + k) = (k + j). Since addition is interpreted as sequencing it always satisfies the grouping and identity principles. So we have
When interpreting integers for Do-It machines having
states for all integers the following laws of addition hold for any
integers i, j, and k
We will extend subtraction to the integers using the negation operator -. For an instruction I we interpret -I as the instruction un-I. For integer instructions we thus have Im = I-m and I-m = Im. Also for any integers i and j we interpret (i + j) as un-(Ii ; Ij) = (un-Ij ; un-Ii) = (-Ij ; -Ii) which is the interpretation of (-j + -i) which by the commutative law = (-i + -j) for Do-It machines having all integer states. We thus have
We define subtraction using addition and negation.
Our use of subtraction to determine what change to effect to achieve a given state depends on the following principle.
When interpreting integers for Do-It machines with all
integer states we have For any integers i and j, (i + (j i)) = ((i + j) i) = ((j + i) i) = (j + (i
i)) = j + 0 = j
In the next article we will move on to interpreting multiplication and division. This will show us the limitations of the instruction interpretation of numbers and lead us up one more level of abstraction in interpreting numbers.