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

putation.
Let me say again that before you continue, it is important to have
mastered the material to this point. We will continue building on this
foundation in the next two chapters, so if there is anything of which
you are uncertain, now is the time to revise. If, on the other hand, you
are ready for some more challenging material, read on.
 
69

---

C H A P T E R 8
COMPUTABILITY
The formal systems we have looked at so far have been very rudi-
mentary string systems. Consequently, their useful application is
rather limited. We can, however, employ formal systems to rather
more interesting and useful ends. In particular, we can use formal
systems to do computation. In this chapter, we are going to use a parti-
cular kind of deterministic formal system – a register machine – to rig-
orously define computability.
8.1 REGISTER MACHINES
Register machines are theoretical entities. They can, however, be
physically implemented (as can any formal system). Modern digital
computers as we know them are implementations of a special kind of
register machine, as we will see in the following chapter.
Simple register machines, such as the ones we will examine in this
chapter, can be straightforwardly implemented with piles of stones,
coins or some other physical tokens. If you have a collection of coins
or other tokens handy, it is highly likely to be useful to have them with
you when working through the examples and exercises in this chapter.
The pigeon hole analogy is quite apt when first starting to think
about register machines. Recall from section 7.2 that we can define
states over any collection of entities we choose, provided any two
given states are e
ffectively distinguishable. In particular, we could
define states as distributions of letters in pigeon holes. This is directly
analogous to the way we want to define states of register machines.
States of register machines are contents of a finite sequence of
registers. Registers are to be understood as discrete containers, hence
the pigeon hole analogy. We will refer to these registers as R
0
, R
1
,
R
2
, . . . , etc. There may be an infinite number of registers; however,
we make the simplifying assumption that only a finite number of
them have contents at any given time.
70

---

The content of a register can be represented as a natural number –
the number of items which it contains. So, if we have a pigeon hole
with three letters, or a discrete pile of three coins, then we can say we
have a register which contains three (items). Precisely what the items
are (letters, coins, assorted objects, etc.) matters not at all. Any enti-
ties which can form e
ffectively distinguishable states can serve as the
symbols manipulated in a formal system.
A sequence of three pigeon holes containing, one, three and two
letters respectively will be isomorphic to a sequence of piles contain-
ing one, three and two coins respectively. Both are isomorphic to a
register machine with the contents, one, three, two, in the first three
registers.
States of register machines, then, can be represented as finite
sequences of natural numbers. The sequence 1, 4, 16, 2, 27 represents
a register machine with 1 in R
0
, 4 in R
1
, 16 in R
2
, 2 in R
3
and 27 in
R
4
. In other words, the numerical sequence represents an ordered
sequence of five piles containing 1, 4, 16, 2 and 27 things respectively.
8.2 PROGRAMS
Register machines are formal systems. We now know what register
machine states are – for all intents and purposes they are simply
finite sequences of natural numbers. We next need to know what the