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

Figure 8.1
Sequence of operations.

---

We now repeat the process. The pc contains 2 and we have a line 2
so we execute that instruction. The instruction on line 2 is an incre-
ment instruction which tells us to increment R
1
(which makes 4 in R
1
)
then put 1 in the pc. The resultant state is represented on the third line
of Figure 8.1.
The pc now contains 1 so we execute the instruction on line 1
again, decrementing R
2
(which leaves 0 in R
2
) and putting 2 in the pc.
We then execute the instruction on line 2 again (since we now have 2
in the pc), incrementing R
1
(which makes 5 in R
1
) and putting 1 in
the pc.
Now we have 1 in the pc, 5 in R
1
and 0 in R
2
. When we try to execute
the instruction on line 1 again, we see we cannot. R
2
is empty so it
cannot be decremented. Instead, we just put 3 in the pc.
When we then come to apply the program again, we see it is no
longer applicable. We have a number in the pc with no corresponding
program line so the program halts. The terminal state we reach is one
in which R
1
contains 5 and in which R
2
is empty.
Exercise 8.1
(a) Run the program [ADD] a few times using di
fferent
initial states. Each initial state should have 1 in the pc but
choose whatever values you like for R
1
and R
2
. Use
pencil and paper if that is all you have but you may find
it helps greatly to use piles of tokens.
(b) The program will always terminate with some value in
R
1
. Compare this, in each case, to the values which R
1
and R
2
took in the initial state. Can you ascertain what
the program is doing?
8.4 COMPUTATION
Having completed Exercise 8.1 you would have noticed that the
program [ADD] always terminates with a number in R
1
which is the
sum of the numbers which were in R
1
and R
2
in the initial state. In
other words, the program [ADD] adds the numbers in R
1
and R
2
and
terminates with their sum in R
1
.
The program does this by virtue of implementing a very simple
algorithm for addition. If we have two piles of things to add, then,
irrespective of how many are in each pile or which pile is the larger,
we can find their sum by implementing the following e
ffective proced-
ure. First try to take one away from one pile. If you are successful, add

75

---

one to the other pile. Repeat until the first pile is empty, at which point
the sum of the two piles will be in the second pile. This is precisely
what the program [ADD] does (where the ‘first pile’ is R
2
and the
‘second pile’ is R
1
).
Given any two numbers x and y, the program [ADD] generates
their sum. Another way of saying this is that the program [ADD]
computes addition.
The previous paragraph marks the first appearance of the concept
which it is the aim of this chapter to explicate, namely computation.
We are on our way to a precise formal account of what it is to
compute. Firstly, however, there are a couple of things we can say
informally about computation.
For any given combination of a register machine program and an
initial state, the sequence of applications of the program is a compu-
tation.
This is what register machines do – they compute. Precisely what it
is they compute we shall come to in a moment.
We might note before we move on that there are some register
machine programs which never terminate. Hence, there are some
computations which never terminate. Consider the one-line register
machine program which reads 1 I 1 1. This program will never termin-
ate; it will simply continue to increment R
1
ad infinitum.
Unfortunately, there is no e
ffective procedure for determining
whether or not any given program will halt. This is the halting
problem well known to computer programmers. There are certain pit-
falls to be wary of in programming, particularly when dealing with
nested loops, which will lead to a program never terminating.
Programmers are taught to be attentive to this and there are methods
and conventions for avoiding non-terminal loops. There is, however,
no algorithm with which we can verify that any given program will
terminate. Certainly there are software verification tools which,
among other things, look for repeated patterns as evidence of likely
non-termination. There are, however, ways to go infinite that do not
involve repetition – think of the sequence of natural numbers, or the
digits of
.
8.5 COMPUTABLE FUNCTIONS
We have so far introduced computation informally as the operations
of a register machine program. We have also seen an example of
something which is not computable. There is no e
ffective procedure
(a fortiori no register machine program) which will determine
76
  

---

whether a given program will halt. Consequently something which
cannot be computed is the question of whether a given computation
will halt.
Precisely what things then are computable? Answering this
question requires a formal characterisation of the notion of
computability which in turn requires a tiny bit of mathematical
terminology.
We need the formal notion of a function. This is a concept which
everyone will be familiar with from grade school arithmetic.
A function f (x
1
, x
2
, . . ., x
n
) 

 m is a mathematical
correlation between some fixed number n of inputs and a unique
output m.
Addition is a function. It takes a fixed number of inputs (two) and
there is a unique output for any given input pair. Multiplication, sub-
traction, division, exponentiation and all the other basic arithmetical
operations are also functions.
Some functions may be undefined for certain inputs. These func-
tions are called