Numbers and Arithmetic III
Repeat Machines
In this article we will extend our machine-based interpretation of numbers to account for multiplication. In the last article we looked at interpretations of numbers as states and as instructions. The interpretation as instructions was introduced to account for addition. There is at least one aspect of both the state and instruction interpretations, which seems unsatisfactory. We believe that numbers have universal application and yet each possible Do-It machine provides a different interpretation of numbers. This is true even when the Do-It machines are constrained to be similar in certain respects such as having an infinity of possible states and states for all integers. We believe that there is a commonality to the models, which allows us to apply intuitions gained from one to the others, but what is our basis for this belief? We would like a single model of numbers, which captures what is common to all these different models.
If we examine the manner in which our state and instruction interpretations were constructed we observe that what is common to the interpretations is the act of repeating an instruction. Regardless of our choice of machine the interpretation of 2 is the instruction obtained by repeating the unit instruction twice. The interpretation –2 is the instruction obtained by un-unit instruction twice. This observation leads to the idea of interpreting a number not as the result of repeating an operation, an interpretation which will differ depending on the nature of the operation, but as the repeating operator itself[1]. Thus 2 would be interpreted as the operator which given an instruction constructs a new instruction which repeats the given instruction twice.
For any instruction J we can construct a sequence of repeated instructions 0*J, 1*J, 2*J, …[2], where “n*J” is read “repeat n J”, in the same way that we constructed I0, I1, … from the unit instruction for a Do-It machine. Thus 0*J = DoNothing, 1*J = J, 2*J = (J ; J), 3*J = (J ; J ; J), and so on. In general we have (n+1)*J = (J ; n*J) = (n*J ; J) = (J ; … ; J) where J is repeated n+1 times. In particular for the unit instruction I, we have n*I = In. For example
3*“Go Forward one square” =
(“Go forward one square” ; “Go forward one square” ; “Go forward one square”) =
“Go forward 3 squares”.
3*“Go Forward 2 squares” =
(“Go forward 2 squares” ; “Go forward 2 squares” ; “Go forward 2 squares”) =
“Go forward 6 squares”.
(n*J ; m*J) = (n + m)*J
Note
Proof: If J is the unit instruction I we have (n*J ; m*J) = (n*I ; m*I) = (In ; Im ) = In+n = (n+m)*I = (n+m)*J. But if J isn’t the unit instruction we can make a new machine in which it is the unit instruction.
Now for each n we define an input/output machine, Rn, called the Repeat n machine, which accepts instructions as input and for input instruction J outputs the instruction n*J. For example R0 outputs DoNothing for any input J; R1 is the identity machine, outputting J on input J; R2 outputs (J ; J) on input J.
We can “build” the Rn for n > 0, using the identity machine, a sequencing machine we will call the Plus machine, and a “duplicating” machine we will call Dup. The Plus machine takes two input instructions, I, and J as input and produce the instruction (I ; J) as output. The Dup machine takes one input instruction, I, and outputs 2 outputs both of which are I – it makes a duplicate copy of I.
For any input/output machines R and S which take one instruction as input and produce one instruction as output we define a new input/output machine R+S as in the following diagram.
For example R2+R3 is
and as the diagram demonstrates R2+R3 = R5. In general we have
and so Rn+Rm = R(n+m).
We can thus construct Rn for n > 0 as follows. R1 is the identity for instructions. R2 = R1+R1. R3= R2 +R1, R4 = R3+R1, … Rn+1 = Rn+R1, ….
It is possible to build a very nice physical model of repeat machines using pulleys. The drawing of connected pulleys below is borrowed from a wonderful web site from the University of Texas.[3]
Motion transmission
with pulleys and belts.
As you can learn from the University of Texas site, a pulley is a grooved wheel around which a rope or belt fits. The rope or belt is coupled by friction to the pulley so that rotation of the pulley pulls the rope or belt and a pull of the rope or belt turns the pulley. In the standard belted pulley arrangement two pulleys are connected by a straight belt so that a right hand or left hand turn of one pulley results in a corresponding right hand or left hand turn of the other. For the crossed belt arrangement the direction of the turn is reversed so that a right hand turn of one pulley results in a left hand turn of the other and vice versa. The ratio of the angular rotation of the two pulleys in a belted arrangement is the same as the ratio of the diameters of the pulleys. For example, if one pulley has twice the diameter of its partner in a belted arrangement, then one complete turn of the larger pulley will result in two complete turns of the smaller. Multiple belted pulley assemblies can be connected using compound pulleys in which two pulleys are welded together rotating around the same shaft. A belt from the second pulley, which we’ll call the connector pulley, on the shaft then transmits the rotation of the first pulley to the connected assembly. You can observe many such assemblies in action by looking under the hood of a car.
We will represent a repeat machine, Rn, as a belted pulley assembly in which the ration of the two pulleys is n, and each of the pulleys is welded to a fixed size connector pulley as in the drawing below.
An R3 Machine
The pulley assembly above is an instance of a “Repeat 3” machine. The diameter of the larger pulley is three times that of the smaller so that one turn of the larger pulley will result in 3 turns of the smaller. The connector pulleys on all our machines will be assumed to be of the same diameter. For each such machine one of the connectors, in this case the one on the larger pulley, will be designated as the input connector, and the other will be designated the output connector. In this model of the numbers, an instruction is represented by rotations of the wheels with one complete rotation being taken as the unit instruction. We can imagine for example that a pulley is attached to our “robot” so that one complete turn to the right of the robot pulley moves the robot one unit to the right and one complete turn to the left of the robot pulley causes the robot to move one unit to the left. We transmit input to the repeat machine by a rotation, either to the right or the left of the input connector which results in a rotation of the output pulley which is transmitted via the output connector to the receive of the output rotation. For the machine above any input rotation is in effect repeated three times in the output.
For non-negative integers n we can interpret n as Rn. We now have three kinds of interpretations of numbers: one as states, another as instructions, and now as repeat machines. Note that we have a natural correspondence between these interpretations. The repeat machine interpretation of n, Rn ,when input the unit instruction I for a Do-It machine outputs the instruction interpretation of n, In, which when executed with the machine in its start state results in the state interpretation of n, Sn. We interpret addition for repeat machines by interpreting n + m as Rn + Rm which as we’ve seen = R(n+m). Next we interpret multiplication in terms of connection.
We interpret “n
x m” as the result of connecting Rm to Rn which we’ll
denote by Rm*Rn
For example
we will interpret (2 x 5) as R5*R2
Of
course one of the properties of multiplication we’ll want to prove is that
order doesn’t matter but in the definition above we’ve switched the order of m
and n in the interpretation to conform to the convention[4]
that “n x m” is thought of as “n many ms” so for example we think of “2 x 5” as
two fives rather than five twos which would correspond to R2*R5
Below we’ve illustrated what the interpretation of 5 x 2 for our pulley machines. Each turn of the input pulley for R2 results in 2 turns of the output pulley which in turn results in 2 turns of the R5 input pulley each of which results in 5 turns of the R5 output pulley for a total of 10 turns of the R5 output pulley.
Next we will derive some properties of multiplication based on our interpretation. We start with an identity principle for multiplication. R1 is the identity machine for instructions and so for any n, Rn*R1 = R1*Rn = Rn. So
For any
n, 1 x n = n x 1 = n. (Identity Principle for Multiplication)
As for 0, since R0 outputs DoNothing for every input and n*DoNothing = DoNothing we have
For any
n, 0 x n = n x 0 = 0. (Zero Principle for Multiplication)
The grouping (or associative) law of multiplication follows immediately from the grouping law for connection. We have (m x (n x p)) = (Rp*Rn)*Rm = Rp*(Rn*Rm) = ((m x n) x p).[5]
For any m,n, and p we have (m x (n x p)) = ((m x n) x p) (Grouping Principle for Multiplication)
Before proving the commutative law I’ll tell a little story that helped me to understand why order doesn’t matter in multiplication. I was playing a piece in band. The piece was in 4/4 time, meaning that there were 4 beats to each measure, except for 4 measures when the piece changed to waltz time which has 3 beats in each measure. So for those measures instead of
um pa pa pa um pa pa pa um pa pa pa it went
um pa pa um pa pa um pa pa um pa pa
The conductor missed the change from 4/4 to waltz time and so he continued conducting 4 beats to the measure. When we complained to him he said “What’s the difference? 3 measures of 4 or 4 measures of 3 it’s 12 beats. Beats is Beats!” This argument definitely does not work for music because it is not the case that beats is beats. However it does work for numbers because units is units.
We’ll prove the claim that order doesn’t matter for 3 x 4 and 4 x 3 but keep the proof sufficiently general that it can be applied to arbitrary m x n and n x m. We’ll be comparing the output of the R3*R4 and R4*R3. Let’s add some pizzazz to our R3 machine and have it color code it’s output. Whenever it repeats an instruction 3 times it will color the first occurrence red, the second occurrence green, and third occurrence blue. R4 will replicate an input instruction exactly as it is. Let’s take a look at the output for R3*R4 and R4*R3 for a given input J.
So we see that the colors are alternating in the output of R3*R4 but are grouped together in the output of R4*R3 , all reds preceding all greens preceding all blues. We further see that in the output of R4*R3 the three parts are 4*J, 4*J, and 4*J. Since “J”s is “J”s regardless of color we can shuffle the “J”s in the output of R3*R4 so that all reds precede all greens which precede all blues. So after shuffling the output of R3*R4 will have the form ((J; … ;J);(J; … ;J);(J; … ;J)).
Now we want to show that each of the uniform colored sections of the shuffled instruction is equivalent to 4*J. To show that the red part is equivalent to 4*J we modify the Do-It machine for J to treat green and blue instructions as DoNothing instructions. The shuffled instruction is still equivalent on the modified machine to the original alternating one because DoNothing commutes with all instructions. Executing the shuffled instruction on the modified machine is equivalent to executing just the red part of the instruction on the original machine because the green and blue parts are ignored. Also, for the modified machine, the output of R3 , (J;J;J), for input J, is equivalent to J, again because the green and blue are instructions are ignored, so the output of R3*R4 on input J will be equivalent on the modified machine to the output of R4 on input J, which is 4* J. Thus the red part of the shuffled instruction is equivalent to 4*J on the original machine. In the same way we can show that the green and blue parts of the shuffled instruction are equivalent to 4*J and so the shuffled instruction is equivalent on the original machine to the output of R4*R3 on the original machine.
Nothing special about 3 and 4 was used in the argument above. For the general case of m and n we, in the same way, can color code the output of Rm , shuffle the output of Rm*Rn so that the elements of each color are contiguous and argue that each contiguous section is equivalent to n*J and so the output of Rm*Rn is equivalent to the output of Rn*Rm . Thus,
For all m, n we have (m x n) = (n x m) (The commutative principle for multiplication)
The next principle we prove states that multiplication can be “distributed” across the elements of a sum. We have
For all m,n,
and p we have (p x (m+n)) = ((p x m) + (p x n)) (Distributive Principle for Multiplication over
Addition)
The proof of this boils down to the commutative principle and a very simple but very valuable observation which we’ll call the copy machine observation: For any instruction input/output machines Q,R, and S the following two assemblies are equivalent.
Remember that Dup is a copy machine that makes two copies of the “original”. Q is a change we want to make in a document. In the first diagram we make the change in the original before making the copies. In the second we make copies and then make the change in each of the copies. What gets passed out is the same.
Using this we can prove (p x (m+n)) = ((p x m) + (p x
n)). Because multiplication is
commutative it suffices to show that ((m + n) x p) = ((m x p)+(n x p)). ((m + n) x p) is represented by Rp*(Rm
+ Rn )which has the following assembly.
((m x p)+(n x p)) is represented by (Rp*Rm + Rp*Rn) which has the following assembly
By the copy machine observation these two assemblies are equivalent.
Before going on there is one piece of business we should take care of. If you look you’ll notice that nowhere above have we actually shown that m*n is a number! We we’ve given a representation of it in terms of machines but we haven’t shown the representing machine is equivalent to a repeat machine. This is another of a closure principle.
For any m and n there is a
number p such that m x n = p The
Closure Principle for Multiplication
Take any number m. From the principles proved above we know that
m x 0 = 0
m x 1= m =(m x 0) + m
m x 2 = m x (1+1) = (m x 1) + (m x 1) = (m x 1)+ m,
m x 3 = m x (2 + 1) = (m x 2) + (m x 1) = (m x 2) + m
…
m x (n + 1) = (m x n) + (m x 1) = (m x n) + m
…
The point of this sequence of equations is that starting with m x 0 = 0 we can obtain m x n for the next value of n, n = 1,2, … by adding m to the previous value and since numbers are closed under addition the result is again a number.
This style of mathematical argument which computes some value or demonstrates that some property is true for all values of n by computing the value or demonstrating the truth of the property for n = 0, and then showing how the value or truth for each succeeding value of n can be computed or follows from the values or truth for previous values, is called mathematical induction. We’ve actually used this principle before, e.g. to prove that numbers are closed under addition, though we haven’t described it formally. Here’s one version of the principle.
In order
to show that some property holds for all non-negative whole numbers it
suffices to show that also hold for n + 1
The Principle of Mathematical Induction
For example, the closure principle for multiplication stated that if m is a non-negative whole number then for any number n, m x n is a non-negative whole number. Using the principle of mathematical induction to prove this it suffices to show:
- m x 0 is a non-negative whole number
- If m x n is a non-negative whole number then m x (n + 1) is a non-negative whole number.
The proof above showed that:
- m x 0 = 0 which is a non-negative whole number
- m x (n + 1) = m x n + m. Suppose m x n is a non-negative whole number. Then m x n + m is also a non-negative whole number and so m x (n+1) is a non-negative whole number.
Thus by the principle of mathematical induction, m x n is a non-negative whole number for all non-negative whole numbers n.
Why should we believe the principle of mathematical induction? Suppose some property satisfies the two conditions in the principle. From the first condition we know the property is true of 0. From the second condition the fact that the property is true for 0 implies that it must also be true for 1 which, again using the second condition, implies that it must be true of 2, which it must be true of 3 and so on. Since all non-negative whole numbers can be obtained by starting with 0 and successively adding 1, the property must be true of all non-negative whole numbers.
One of the
important uses of multiplication is to convert between different units of
measurement. Suppose for example that I
have a Do-It machine for adding liquid to a bowl. I take my zero state to be an empty bowl and since I have a one-ounce
measure I take my unit instruction to be “add one ounce of liquid.” Now I’m trying to prepare a recipe and it
turns out that the recipe assumes that the unit of liquid measure is a
cup! So when the recipe says “add 1
unit of liquid” it means “add one cup of liquid”. So my problem is how to adapt my ounce adding machine to recipe
instructions which assume 1 unit of liquid means 1 cup? Let’s use colors to distinguish instructions
which assume cup measure from instructions which assume ounce measure, say blue
for cup instructions and red for ounce instructions. So now I
describe my problem as, “My machine executes red instructions but the recipes
have blue instructions.” So what we
need is a way of converting blue instructions to red instructions. I consult a book about weights and measures
and discover that “1 cup = 8 ounces” which means that adding 1 cup is the same
as adding 1 ounce 8 times. In terms of
blue and red,
“Add 1 unit liquid” = 8*“Add
1 unit liquid”
1 unit = 1 cup 1 unit = 1 ounce
So we convert from cup instructions to ounce instructions by multiplying by 8.
Similarly to convert quart to cup we multiply by 4 and then by compounding to convert quart to ounce we form
Next we extend multiplication to the negative integers. The key is how do we interpret –1. We will of course interpret it as a kind of repeat machine R-1. But what should R-1 do? If we input the unit instruction, I, for a Do-It machine, we expect R-1 to output I–1 = -I, the uninstruction for I. Since any instruction of a Do-It machine except DoNothing can be taken to be a unit instruction for a Do-It machine R-1 should map every instruction J to –J. Like all repeat instructions it should also map DoNothing to DoNothing and since DoNothing = -DoNothing, we have for all J, R-1 takes J to –J.
The pulley machine for R-1 has a crossed belt. A right hand turn is converted to a left hand turn and a left hand turn is converted into a right hand turn.
Since R-1 takes J to –J for any instruction J, it must also take –J to –(-J) = J for any J. So
R-1*R-1
= R1
This is nicely illustrated by our pulley machines. We see that connecting two crossed belt machines is equivalent to a straight belt machine. The first machine reverses the orientation of the turn (e.g., turning right hand turns into left hand turns) and the second machine will then reverse the orientation back to the original orientation (e.g., turning the left hand turns back into right hand turns. )
We now can define repeat machines R-n for all n by taking R-0 to be R0 , R-2 = R-1 + R-1 ,
R-3 = R-2 + R-1 , and in general R-(n+1) = R-n + R-1 . So we have
R-n takes any instruction J to n*(-J)
In terms of our pulley machines we obtain R-n from Rn by crossing the belt. For example
The machine above converts 1 right hand turn into 3 left hand turns and 1 left hand turn into 3 right hand turns.
We now can interpret a negative whole number –n as R-n.
We extend multiplication to include all integers, positive or negative, by interpreting
For any integers i,j we interpret (i x j) as Rj*Ri
We note that the identity and grouping principles continue to hold because they are general properties of connection.
For any integers i,j,k
By connecting pulley machines we can observe how negative numbers multiply. The assemblies below illustrate ((-2) x 5) = -10, (2 x (-5)) = -10, and ((-2) x (-5)) = 10
In each case one input turn will result in 10 output turns. In the first two cases where just one of the belts is crossed, the orientation of the output turns will be reversed from the input. In the third case, where both belts are crossed the reversals of orientation will cancel and the original orientation of the turn will be preserved.
The general rules for multiplying negative numbers are
(-m) x n = -(m x n) (-2) x 5 = -(2 x 5) = -10 m x (-n) = -(m x n) 2 x (-5) = -(2 x 5) = -10 (-m) x (-n) = (m x n) (-2) x (-5) = (2 x 5) = 10
We can formally prove this by proving a sequence of propositions.
For any J, n*(-J) = -(n*J)
We prove this using the principle of mathematical induction.
- (Proof for n = 0.) By definition 0*(-J) = DoNothing;
Also, -(0*J) = -(DoNothing) = DoNothing.
- (Proof that if true for n then must be true for n+1.)
Suppose that for any J, n*(-J) = -(n*J).
We must show that (n+1)*(-J) = -((n+1)*J).
By definition, (n+1)*(-J) = (n*(-J);1*(-J)) =
= (n*(-J) ; (-J)) , because by definition for any instruction K, 1*K = K,
=(-(n*J) ; -J) , by our assumption that the proposition is true for n,
= -(J ; n*J), by the principle that –(K ; L) = (-L ; -K),
= -(1+n)*J, definition,
=-((n+1)*J).
The two requirements of the principle of mathematical induction are proved to the proposition is proved.
For any n, (n x (–1)) = ((-1) x n) = -n
Proof:
-n is represented by R-n
(n x (-1)) is represented by R-1*Rn
((-1) x n) is represented by Rn*R-1
We want to show that for any instruction J the output of the three machines on input J is the same. The outputs are computed below and are equivalent.
J n*(-J) = -(n*J)
(-m) x n = -(m x n)
Proof:
(-m) = ((-1) x m) so using the grouping law we have,
(-m) x n = ((-1) x m) x n) = (-1) x (m x n) = -(m x n)
m x (-n) = -(m x n)
Proof:
(-n) = ((-1) x n) so using the grouping law and the two previous propositions,
m x (-n) = m x ((-1) x n) = (m x (-1)) x n = (-m) x n = -(m x n)
(-m) x (-n) = (m x n)
Proof:
By the proposition proved earlier we have (-m) = (m x (-1)) and (-n) = ((-1) x n)
So (-m) x (-n) = (m x (-1)) x ((-1) x n)
= (m x ((-1) x (-1))) x n, by the grouping principle
= (m x 1) x n, ((-1)x(-1)) = 1 proved earlier)
= m x n, identity principle.
Finally we show that the remaining multiplication principles extend to all integers.
(-m) x 0 = 0 x (-m) = -(m x 0) = -0 = 0 (Zero Law for Multiplication)
For all integers i and j we have i x j = j x i (Commutative Law for Multiplication)
Proof: We know that the commutative law holds for positive integers. We have three additional cases to consider.
- Case i = -m, j = -n: i x j = (-m) x (-n) = m x n = n x m = (-n) x (-m) = j x i.
- Case i = -m, j = n: i x j = (-m) x n = -(m x n) = -(n x m) = n x (-m) = j x i.
- Case i = m, j = -n: i x j = m x (-n) = -(m x n) = -(n x m) = (-n) x m = j x i.
Finally we have the distributive law
For any integer i, j, and k we have i x (j + k) = (i x
j) + (i x k) (Distributive Principle for Multiplication Over
Addition)
Proof: The previous proof of the distributive principle only depended on the commutative principle which we know holds for all integers, and the copy machine observation which is a general principle for input/output machines.
In the next article we will turn our repeat machines around to get un-repeat machines and use them to study division and fractions.