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

many states. This may be clearer in a moment when we give a formal
specification of states using recursive definition; however, we first
need to help ourselves to a few more concepts.
Firstly, we need the concept of an initial state. Specifications of
formal systems often include an initial state, or beginning configur-
ation of the system. All board games have an initial state – state A in
Figure 7.1 represents the initial state of chess.
Secondly, there is a special and important state of this system (and
typically of string systems in general) and this is the empty string. The
empty string is precisely that – a string of no symbols at all. We will
write it as ø. It is important to remember that the empty string is a
string, and – by stipulation – is a state of [STR]. The need for the
empty string will become apparent in a moment.
We will also need to employ string variables which we will write as

 or . String variables stand for strings – any string you like (includ-
ing the empty string). We need to make use of string variables and the
empty string in order to formally specify rules of su
fficient generality.
Again, this will become apparent in a moment.
Finally, we need to represent string concatenation. String concate-
nation simply means joining two strings together – i.e. writing them
one after the other. We will write the concatenation of two strings 

and  as
 – i.e. their typographical concatenation. So, if 
 is
standing for the string 
■■◊ and  is standing for the string ◊■ then

 will be 
■■◊◊■ and 
 will be ◊■■■◊.
Note that ø


 ø
 
 
ø 
 
. In other words, any string
is identical to its concatenation with the empty string, regardless of
58
  

---

where you put it. In simpler terms, tacking on nothing always leaves
you with what you started with.
Before we give the complete formal specification of [STR], let’s first
just give an informal description of how the rules of this system will
work.
[STR] will have only two rules. Rule one will say that we can take
any state which begins with two boxes and ends with a diamond (and
has whatever you like – including nothing – in between) and output a
state which begins with a diamond and is followed by whatever came
between the two boxes and the diamond in the input state (which may
be nothing).
Rule two will say that we can take any state which has a diamond
in it somewhere (and has anything you like – including nothing –
before and after the diamond) and output a state which begins with
two boxes, ends with a diamond, and in between has whatever it was
that came before the diamond in the input state.
Explaining the rules informally like this is rather laborious.
However, the formal specification is quite concise and tidy, as the fol-
lowing demonstrates.
[STR]
[S1]
ø is a state
[S2]
If  is a state then so is 
■ and ◊
[S3]
Initial state is:
■■◊◊
[R1]
■■◊ →
◊
[R2]

◊
 →
■■◊
Now, let’s carefully interpret this formal specification and make sure
that it captures the system we have informally described.
The first thing to note about the formal specification is that, while
giving an informal description of the system took many wordy para-
graphs, the formal specification is given in five short lines. There is
great economy of expression to be had in formalisations.
It may not be clear, on first examination, that [S1] and [S2] capture
all and only the states of this system – this is an example of recursive
definition. [S1] is the base clause – it simply stipulates that the empty
string counts as a state. All the work is done in [S2] – the recursive
clause – which says that if you take any state and tack on a 
■ or a ◊
the result will be a state. A little thought should su
ffice to show that
any finite string of the symbols 
■ and ◊ can be constructed through
repeated applications of [S2], given [S1]. [S3] merely stipulates the
initial state.
 
59

---

The astute reader may wonder whether [S1] and [S2] capture only
the states of the system – the worry being that they do not seem to
explicitly rule out infinitely long strings. We need not be concerned,
however – if you take any string of finite length and add one symbol,
the result will always be a string of finite length.
We have already given informal readings of [R1] and [R2]. Work
back and forth between those two paragraphs and their formal speci-
fication above until you are convinced that [R1] and [R2] do in fact
capture the content of those paragraphs. The left-hand side (LHS) of
the arrow of each rule describes the form of input states and the right-
hand side (RHS) describes the form of output states.
It should be clear now why we want to use string variables. Using
string variables lets us refer to a class of strings which share the same
form (e.g. any string which begins with . . . and ends with . . . ). String
variables always refer to the same string in the LHS and the RHS of the
rule – that is precisely the point in using them. Whatever you take  to
be in the input side of a rule must be the same in the output side of that
rule. There are no restrictions on string variables between rules though:
having taken  to be one string in the application of one rule has no
bearing on what  can be in further applications of rules, or even in
further applications of the same rule. If this is not yet clear it should
become so in a moment when we examine the operations of the system.
It may still not be terribly clear why we want to be able to refer to
the empty string, so let’s demonstrate its use.
Rule [R1] will apply to the initial state 
■■◊◊. In this case, what is
in between the initial 
■■ and the final ◊ is a single ◊, so in applying
the rule we take  to be 
◊, in which case the output of [R1] will be ◊◊.
Another way of saying this is that the initial state is of the form
required to apply [R1], namely the form 
■■◊ (where in this case 

 ◊). Hence, if we apply the rule, we get an output state of the form
◊ (where  
 ◊), namely ◊◊.
Rule [R1] will also apply to the state 
■■◊ as it is of the form
■■◊ (where  
 ø). By similar reasoning [R2] will apply to the
states 
◊, ■◊ and ◊■. This is why we need the empty string.