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

participants in very short order.
This is not, however, ipso facto an indictment of the Turing test, but
rather of the current state of play in artificial intelligence.
Perhaps a behavioural test of this kind, while a good indicator
under certain strong conditions, simply does not resolve the question
satisfactorily one way or another in problem cases. In such instances
it is not obvious what other methods we might employ to determine
the presence or absence of a mind.
Exercise 10.3
Would a version of the Turing test involving a number of
judges and unrestricted in duration serve as a reliable
indicator of mentality? Can you think of any other conditions

111

---

or constraints we might build in to the test to increase its
reliability?
Let’s pause now and think about where we are and where we are
going. So far in this book, we have introduced various philosophical
problems associated with understanding the mind and examined a
number of theories which propose answers to these questions. We
have also introduced some rudimentary neuroanatomy to get a feel
for how brains work, given that there is clearly some important rela-
tion between brains and minds.
Of the philosophical theories of mind we have covered, function-
alism was the least problematic and most satisfactory. However, it left
us wanting to know more about the relevant functions in question. In
order that we might be well prepared to understand a particular way
of answering this, we then rigorously developed a precise account of
computation.
Armed with this understanding, we have now examined a particu-
lar way of fleshing out functionalism which supposes that the func-
tions in question are computations – namely computationalism. We
have also lent some consideration to the question of the appropriate
conditions under which we should attribute mentality. There will be
much more to say about this as we progress.
In the coming chapters we are going to see how a commitment to
computationalism confers a methodology for artificial intelligence
research. We will be concentrating on various computational prob-
lems which must be solved in order to equip a device with the capacity
to reason and use language.
Along the way we will be gathering evidence which bears on the
tenability of computationalism – an issue we will explicitly return to
at the beginning of Chapter 17 when we begin to mount serious chal-
lenges and sophisticated philosophical objections to the theory.
Now it is time to begin telling the story of artificial intelligence –
a story which begins with the concept of search.
112
  

---

C H A P T E R 1 1
SEARCH
Given the computationalist hypothesis as we have described it, inves-
tigating mentality involves investigating the operations of the formal
system [MIND] and its constituents.
The classical or symbol systems approach to artificial intelligence
involves trying to determine the algorithms for the cognitive functions
involved in [MIND] and investigating their associated formal sys-
tems.
Many of the problems in the classical artificial intelligence tradition
reduce to determining whether or not a certain state can be generated
in a particular formal system, or to finding a particular generated state
of a system. In other words, many artificial intelligence problems
reduce to the problem of searching for a particular state.
In this chapter, we are going to briefly run through various
methods for searching the generation tree of a formal system. You
may wish to refer to section 7.5 to refresh your understanding of gen-
eration trees and the associated terminology.
11.1 TOP DOWN, BOTTOM UP
One method of determining whether a state of a formal system is gen-
erated, or finding a derivation for a particular state of the system, is
to construct the entire generation tree for the system. If the state we
are interested appears on the tree it is a generated state and we can
read o
ff its derivation(s) by following the branches back up to the root
node.
For instance, suppose we are investigating the system [BIN] from
section 7.5 and we are interested in whether the state 01 is generated.
We can construct a generation tree for [BIN] beginning from the initial
state and working our way down through all the possible ways in which
rules can be applied to each node. Figure 11.1 gives a generation tree
for [BIN] which shows that (and how) the state 01 is generated.
113

---

A search of this kind is known as a top-down search. Often, however,
it will be more e
fficient to begin with the state we are trying to derive
and work backwards through the rules to see if we can get back to
the initial state. This kind of search is called a bottom up search.
Figure 11.2 depicts a bottom up search in [BIN] for the state 01.
One advantage of using a top-down search is that it is comprehen-
sive. Every generated state appears on a completed top-down tree.
Bottom-up searches, however, have the advantage of delivering
all and only the possible derivations for the solution state, if there
are any.
A major consideration in determining whether or not a top-down
search or a bottom-up search will be more e
ffective is the associated
branching factor. The branching factor of a tree – the average number
of descendants below each node – determines the complexity of the
tree so ideally we want to minimise it. As Figures 11.1 and 11.2 demon-
strate, the branching factor of a top-down search in a system will often
be distinct from the branching factor of a bottom-up search. In the
case of [BIN], a bottom-up search proves to be more e
fficient.