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

partial functions, in contradistinction to total func-
tions whose output is defined for all possible inputs (of the
appropriate type).
Addition and multiplication are total functions. Their input types
are real numbers and their output is defined for any possible pair of
real numbers.
Division, on the other hand, is a partial function. It also takes real
numbers as input but its output is not defined for certain input pairs
(division by 0 is undefined).
The number n of inputs which a function takes is known as the
adicity of the function. Addition and multiplication have an adicity
of 2. The squaring function has an adicity of 1.
The noun adicity also has adjectival cognates with appropriate
numeric prefixes. We would say, for instance, that squaring is a
monadic function, and that addition and multiplication are dyadic
functions. Less technically, we can also refer to these as one-place
functions, two-place functions, etc.
We know have all the terminology we require to give a precise
formal definition of what it is to compute, as follows.
If f is a function with adicity n, then program P is said to compute f
if:
when P is run with 1 in the pc, x
1
, . . . , x
n
in R
1
, . . . , R
n
and all
other registers empty then:

77

---

• If f (x
1
, . . . , x
n
) is undefined then the computation never ter-
minates
• If f (x
1
, . . . , x
n
) 

 m then the computation terminates with m
in R
1.
This is quite a dense definition so let’s unpack it and consider some
examples.
The first thing to note is that the objects of computation are func-
tions. The definition above stipulates conditions under which we can
say a given register machine program computes a function.
The definition is read as follows. Firstly, there is an initial condition
which states that the program should be run with 1 in the pc, the n
inputs of the function in the first n registers, and all other registers
empty.
So, for example, to determine whether the program [ADD] com-
putes the dyadic addition function f (x
1
, x
2
) 

 x
1
 x
2
we first satisfy
this initial condition by clearing all the registers and putting 1 in the
pc, x
1
in R
1
and x
2
in R
2
. We then run the program.
Since addition is a total function, we know that its output will be
defined. That is to say, there will be an m which is the result of com-
puting the function. Hence, for the program [ADD] to be said to
compute the addition function, it must, according to our definition
above, terminate with x
1
 x
2
in R
1
.
The program [ADD] does, in fact, always terminate with x
1
 x
2 
in
R
1 
when the stipulated inistial conditions are met. Consequently, we
can now say (with the authority of the demonstrated satisfaction of
formal conditions) that the program [ADD] computes the dyadic
addition function.
We now have the precise formal account of computation we
wanted to develop. We can use this to define computability as follows.
A function is computable i
ff there is a register machine program
which computes it.
So, to recap, the operations of register machines are computations.
The objects of computation are functions – register machines
compute functions. To compute a function is to satisfy the formal con-
ditions laid out above. To say that a function is computable is to say
that there is at least one register machine which will compute it.
78
  

---

8.6 BUILDING PROGRAMS
In the remainder of this chapter we will be developing methods for
constructing register machine programs to implement algorithms. We
are going to write programs to compute various functions. In each
case, I will set an exercise and then work through a possible solution.
Attempting the exercises before reading the solution will aid signifi-
cantly in consolidating your understanding of this material.