Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence

Exercise 8.2
Write a register machine program which copies the contents
of R
1
into both R
2
and R
3
, leaving R
1
empty. Assume we
begin with R
2
and R
3
both empty.
All the di
fficulty in writing register machine programs resides in deter-
mining the algorithm. Once we have determined the stepwise process
which is guaranteed to deliver the result, translating this into register
machine code is quite straightforward. This is why employing phys-
ical tokens is useful – they help us work stepwise through potential
algorithmic procedures.
The algorithm for Exercise 8.2 is as follows. First try to take a stone
away from the first pile. If you are successful, put one stone in the
second pile and one stone in the third pile. When the first pile is empty,
its contents will have been copied into both the second and third piles.
Translating this into register machine code gives us:
1
D 1 2
4
2
I
2 3
3
I
3 1
Exercise 8.3
Write a register machine program which copies the contents
of R
1
into R
2
but preserves the contents of R
1
. Assume we
begin with R
2
and R
3
both empty.
Very often we will want to copy the value of a register into another
register, but without losing the value from the first register. Since the
only way to copy a value is to decrement the register containing it
while incrementing the target register we always lose the contents of
the first register. We can use the same process to put the value back

79

---

into the first register again, but then we lose it from the target regis-
ter and find ourselves back where we started.
The way around this dilemma is to use a working register. Very
often, we will need to employ working registers in programs to store
values during the computation.
In this case, what we need to do is copy the contents of R
1
into both
R
2
and R
3
, then copy the contents of R
3
back into R
1
. R
3
is our
working register – its only function is to keep a copy of the value ini-
tially in R
1
so that we can put it back once we have finished copying
it into R
2
.
We can simply extend our solution to Exercise 8.3 as follows:
1
D
1
2
4
2
I
2
3
3
I
3
1
4
D
3
5
6
5
I
1
4
The solutions to Exercises 8.2 and 8.3 do not, strictly speaking,
compute ‘copying’ functions. Recall from our definition of what it is
to compute a function that computations always terminate with the
result in R
1
. So the solution to Exercise 8.2 actually computes the
function which maps any input onto the value 0 – f (x) 

 0 – and
the solution to Exercise 8.3 computes the function which maps any
input onto itself – f (x) 

 x.
Our interest, however, is not in the functions which these programs
compute but rather in the methods they employ. The method of
copying without loss is one which will feature frequently in our pro-
grams. The point of the last two exercises has simply been to develop
a useful piece of code which we can employ as a subroutine in further
programs.
We will need to employ the method of copying without loss to solve
the following exercise.