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

precisely the inadequacy of a functional account of mental states. The
functionalist account of mentality fails to capture what seem to be
essential aspects of our mental states – their subjective qualitative
aspects. There just is something that it is like to see blue, or to be in
pain, or to taste chocolate ice cream, and one might think that any
theory which fails to give an account of such qualia is explanatorily
inadequate.
With these di
fficult philosophical issues to ruminate on, it is time to
turn our attention to a formal account of computation.

51

---

C H A P T E R 7
FORMAL SYSTEMS
In the previous chapters, we have considered the question of what
minds might be and sketched out the space of possible responses to
this question. In doing so we have seen a progression of philosoph-
ical theories of mind and considered arguments and objections per-
taining to each.
In the following three chapters, we are going to be working our way
towards a precise formal account of what computers are.
Unlike the question of what minds might be – which is ripe for the-
orisation – there is something that it is to be a computer and specify-
ing that something is a purely descriptive exercise which involves
delving into theoretical computer science and teasing out some
foundational material.
In these chapters, I presuppose no understanding whatsoever of
computer science, mathematics or any formal discipline. If you have
an aversion to symbols then do not fear. The introduction here is
deliberately slow and gentle and there are numerous exercises to aid
understanding.
We will start in this chapter by defining formal systems and playing
with some toy (simple) formal systems to get a basic feel for symbol
manipulation. We are then going to spend the next chapter investi-
gating a particular kind of formal system: a register machine. We will
use the concept of a register machine – and related concepts involved
in its explication (like program) – to give a precise characterisation of
computability.
With this rigorous definition of computability, we can then speak
authoritatively (and correctly) about computing, computers and
computation. We are going to play with some toy register machine
programs to get a feel for the syntactic nature of computation.
We will also have a look at some more di
fficult and complicated
register machine programs (for those who are amenable to
such things and enjoy a challenge). These more di
fficult challenge
52

---

exercises can be skipped without prejudice by those who have no
taste for them.
Finally, we complete our survey of computational theory in
Chapter 9 by seeing how we can use the very clever method of Gödel
coding to define a universal machine – a machine which can compute
any computable function. We shall also discuss just what it is to be com-
putable – what falls within the limits of the computable and what falls
outside.
Armed with a sound knowledge of computational theory, we will
have precise formal definitions and some subtle distinctions at our
disposal. Deploying these, we will be able to correctly and responsi-
bly characterise the theory that is our central concern. That will be
our first aim in Chapter 10.
7.1 EFFECTIVITY
It is highly likely that every reader of this book has at some stage in
their life played a game of at least one of the following: chess,
draughts, backgammon, go, Chinese checkers or – at the very least –
tic-tac-toe (aka noughts and crosses). If you understand how at least
one of these games is played (most of us can grasp tic-tac-toe), then
regardless of how good or bad you are in playing them, you already
understand the principles underlying formal systems. We’ll begin our
examination of formal systems by simply making explicit what you
already grasp implicitly.
Chess exemplifies the important features of formal systems nicely,
so I will make reference to it throughout this chapter. Don’t be con-
cerned if you don’t particularly understand the rules of, or strategy
behind, chess – nothing I will say hinges on such an understanding.
To begin drawing out the features of formal systems, let’s consider
the chess board configurations depicted in Figure 7.1.
It is immediately apparent that the two boards are in di
fferent con-
figurations, or states. Furthermore, we can all agree on a description
of how the two depicted states di
ffer: one of the white pieces has
moved two squares towards the black pieces. We can be more precise
than that though. If we label the horizontal from ‘a’ to ‘h’ left to right,
and the vertical from ‘1’ to ‘8’ bottom to top, then we can say:
[1]
The piece which was in square f2 in state A is in square f4 in
state B.
We can, if we know about chess, add layers of interpretation to [1]. At
the first level of interpretation we can say that a pawn which was in
 
53

---

square f2 in state A is in square f4 in state B. At the next level of inter-
pretation we can say that the transition from state A to state B repre-
sents a valid move in chess – a move made according to the rules of the
game. We can also say that state A represents the beginning configura-
tion, or initial state, of a chess game. At yet another level of interpre-
tation we might say that the move depicted is an interesting or dull move.
However, none of this interpretation concerns us for the moment.
We just want to concentrate on [1] and use it to bring out some crucial
features of chess, without which the game could not be played – fea-
tures so obvious that you have probably never had cause to reflect on
them.
What interests us about [1] is that given a chessboard in state A and
labelled as we have described, [1] carries all the information required
to recreate state B – even if we know absolutely nothing about chess.
In fact, we do not even need to recognise the states as configurations
of a chess board in order to apply the information in [1] to state A and
generate state B.
Let us recast [1] in terms of a task, or procedure, as:
[2]
Take the piece in square f2 and move it to square f4.
Presented with a labelled chess board configured in state A and told
[2], we could easily achieve the task without any understanding of
the task’s significance, without any interpretation of its meaning.
Obviously, we need to interpret the meaning, in natural language, of
the words describing the task, but the task itself can be carried out
54
  