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

Figure 8.2
Progression of squares.

---

The Fibonacci sequence progresses as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . .
Let fib(x) be the function whose output is the xth Fibonacci
number.
Write a register machine program to compute fib(x).
Hint: fib(1) 

 0; fib(2) 
 1; fib(x  1) 
 fib(x1)  fib(x)
84
  

---

C H A P T E R 9
UNIVERSAL MACHINES
This chapter completes our exposition of computational theory. So
far, we have discussed formal systems broadly and we have used a
special kind of formal system – a register machine – to define compu-
tation and computability.
In doing so, we gained some insight into what is computable and
what is not. We saw, for instance, in section 8.4 that there is no
e
ffective procedure for determining whether or not a given program
will halt. Since register machines are bound by constraints of
e
ffectivity, we can say that there is, therefore, no register machine
which can determine, of any given program, whether or not it will
halt. Consequently, since computability is defined in terms of register
machines, we can say that the halting problem is not computable.
We also know from section 8.5 that the objects of computation are
functions and we have a precise formal definition of what it is to
compute a function. So we know that at least some functions are com-
putable and that only functions are computable.
There are still, however, important questions left unanswered. For
one thing, we have no account of the limits of computation. We do
not yet know precisely which functions are computable.
We are also still left wanting of a formal account of e
ffectivity
and algorithmicity. Recall from section 7.2 that we defined e
ffectivity
only informally in terms of algorithmicity. We said that a procedure
is e
ffective, just in case there is an algorithm for carrying it out.
However, the notion of an algorithm was also only fleshed out
informally, in terms of a mechanical procedure or a set of instruc-
tions which can be carried out without any understanding or
interpretation.
The first thing we will do in this chapter is to give a precise answer
to the question of the limits of computation by tying our informal
notion of e
ffectivity to our formal account of computability, thereby
delivering a formal definition of algorithmicity.
85

---

With this account in hand, we are then going to develop a descrip-
tion of a single machine which can compute any computable func-
tion – a computer.
9.1 CHURCH/TURING THESIS
The halting problem is a particular instance of the Entscheidungs-
problem – or decision problem – which was of interest to mathemat-
icians and logicians well before there was a formal theory of
computation. The decision problem for a particular formal system
refers to the question of whether or not there is an e
ffective procedure
for determining, of any given state of the system, whether or not it is
generated in the system. If there is such a procedure, the system is said
to be decidable.
For the sake of only those readers who may have an understanding
of modern logic, let me say the following. The question of whether or
not a particular logical system is decidable is the question of whether
or not there is a method for showing, for any arbitrary sentence of the
language of the system, whether or not that sentence is provable in the
system. However, the concept of provability reduces to the concept of