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

rider on e
ffective procedures. A procedure only counts as effective if
it can be carried out in finite time.
Counting the molecules in this book is an e
ffective procedure. They
are all presently configured in a solid and are pretty much sitting still,
so we could, in principle, set up a very fine three-dimensional grid for
reference and simply enumerate the molecules in each grid cube in
order. It would take a very, very long time, but finite time.
Counting the natural numbers, on the other hand, is not an
e
ffective procedure. Although the process is mechanical – name zero;
name the successor of the last number you named; repeat the previous
step until you can go no further – it cannot be completed in finite time.
Every natural number has a successor – there are infinitely many of
them. So implementing this process is not e
ffective.
56
  

---

Now that we have developed a good understanding of e
ffect-
ivity, it is time to put the concept to work in characterising formal
systems.
7.2 STATES AND RULES
Formal systems are composed of two collections: a collection of
states and a collection of rules. The specification of any given
formal system consists in the specifications of its states and of its
rules.
We can define states over any entities we choose, provided distin-
guishing between any two given states is e
ffective.
To give a few examples, we can define states as configurations of a
game board, as configurations of a finite array of switches, as distri-
butions of people in a finite array of theatre seats, or as distributions
of mail in a finite array of pigeon holes.
There must be only finitely many entities to define states over,
otherwise any two states will not be e
ffectively distinguishable. There
can, however, be infinitely many states in the collection – many of the
formal systems we will meet have infinitely many states, defined recur-
sively over only a few entities. We will see how this trick is achieved in
a moment.
All of the above examples of states employ physical objects as
tokens – pieces, switches, people, mail – and states are distinguished
by the discrete arrangements of these tokens. We could, however,
just as easily use symbols on paper as tokens and define states over
strings of these symbols (provided of course that the strings are
e
ffectively distinguishable). All of the formal systems we will be
playing with in our survey of computational theory will be just such
symbol systems.
Once we have defined a collection of states, we need to specify a
collection of rules. Rules operate on states to generate other states.
Rules, like states, are constrained only by considerations of e
ffectivity.
States can be defined over anything you like, provided any given two
are e
ffectively distinguishable. Similarly, rules can be anything you
like provided they meet two constraints.
Firstly, determining whether a given rule applies to a given state
must be e
ffective. Typically not all rules will apply to all states.
Secondly, if a rule applies to a state, it must e
ffectively deliver a finite
set of possible output states.
So rules take states, e
ffectively modify them, and return distinct
states.
 
57

---

Now that we know how to specify a formal system and what the
constraints are on states and rules, let’s exemplify with our first toy
formal system.
7.3 SPECIFICATION
We want to discuss the properties and operations of formal systems,
so let’s define a symbol system to play with. Let’s call it [STR] – it will
be a string system.
States of this system will be finite strings of the symbols 
■ and ◊.
To give a few examples:
■■ is a state of [STR], ◊◊■■◊■◊◊■ is a
state of [STR] and 
◊ is a state of [STR].
It should be fairly clear that any two states will be e
ffectively dis-
tinguishable. It may not be as clear that while there are only two types
of symbols which we are defining states over, and while there can be
only finitely many tokens of these in any given state, there are infinitely