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

generation. If we take the initial state of the system to be its axioms
and the proof theory of the system to be its rules, then decidability
simply amounts to whether or not one can show, of any arbitrary sen-
tence, whether or not it is included in some state derived from the
initial state in accordance with the rules. Those readers who have done
a first course in logic will know that the propositional calculus is
decidable, but the predicate calculus is not.
Do not be concerned if the previous paragraph means little or
nothing to you. It is merely intended as an aside for those with some
exposure to logic.
It was in the course of arguing that a particular logical system is
not decidable (the predicate calculus for those for whom that means
something) in his 1936 paper – On Computable Numbers, with an
Application to the Entscheidungsproblem – that the British math-
ematician Alan Turing formally defined computability and, in doing
so, laid the foundation for what has become computer science.
Turing defined computability in terms of theoretical machines
which are now known as Turing machines. It is far more common in
the computational theory literature to see talk of Turing machines
than it is to see talk of register machines. Turing machine com-
putability and register machine computability are, however, provably
equivalent – they can compute all and only the same functions.
86
  

---

Wherever you see talk of Turing machines, or Turing computability,
you can substitute this with register machines and register machine
computability.
I chose to employ register machines for an initial presentation
of computational theory for two reasons. Firstly, simple register
machines are readily amenable to physical implementation with a col-
lection of tokens (coins, buttons, etc.). This can serve as a great aid to
understanding their operations. Secondly, while register machines
and Turing machines are functionally equivalent, the mechanics of
register machine operations are closer to the way computation is actu-
ally implemented in computers as we know them
In his 1936 paper, Turing argued that all and only those procedures
which were algorithmic could be computed by Turing (register)
machines.
In another paper published in 1936, an American mathematician,
Alonzo Church, argued that the informal notion of e
ffective calcula-
bility could be understood (at least for calculations over positive inte-
gers) in terms of the formal notion of a recursive function. In both
cases, Church and Turing aimed to tie a notion which was well under-
stood informally – that of algorithmicity, or e
ffectivity – to a concept
for which there was a precise formal definition.
The Church/Turing thesis, as it is now commonly referred to, can
be expressed quite concisely as: all and only e
ffective procedures are
computable functions.
It is important to appreciate that the use of ‘computable’ in the
Church/Turing thesis refers to a particular formal understanding of
computability, namely register machine computability as we have
defined it. This may not seem terribly important but there is consid-
erable scope for misinterpreting the Church/Turing thesis if one does
not keep this in mind and it is common to see such misunderstanding
in the literature.
It is also worth pointing out that the equivalence between e
ffective
procedures and computable functions is a thesis and not a theorem. In
other words, it is a proposed equivalence but it is not a proven one.
There seems, however, by the very nature of the thesis, to be little
chance of actually proving it, since it equates a formal notion with
an informal one. One direction of the thesis – that all computable
functions are e
ffective procedures – is obvious since we have defined
computability in terms of e
ffective procedures. The other direction –
that only computable functions are e
ffective procedures, or that
all e
ffective procedures are computable functions – is less obvious. It
is the case, though, that since 1936 we have amassed considerable
 
87

---

evidence in favour of the thesis and run across no counter-examples
to it.
So the Church/Turing thesis provides us with answers to both of
the questions we identified at the beginning of this chapter. We now
know precisely which functions are computable – all and only those
which are algorithmic. We also now have a formal characterisation of
e
ffectivity/algorithmicity – precisely that which we gave for com-
putability in section 8.5.
According to the Church/Turing thesis, there is a register machine
program for any given algorithm (since all e
ffective procedures are
register machine computable). Add to this the fact that register
machine programs are deterministic formal systems, and that the
operations of any given deterministic formal system are algorithmic,
and we can see that algorithmic procedures, e