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

Exercise 7.1
The paragraph above mentions four applications of rules to
states: [R1] to the state 
■■◊ and [R2] to the states ◊, ■◊ and
◊■.
What will the output of these applications be in each case?
How are the string variables instantiated in each case?
60
  

---

Recall that typically, not all rules will apply to all states – determin-
ing whether or not a given rule applies to a given state must be
e
ffective. It should be obvious that neither [R1] nor [R2] will apply to
every state of [STR]. It should be equally obvious that determining
whether either rule applies to a given state is e
ffective.
If you feel you have not quite followed all of the content of this
section, then go back over the material until you are comfortable with
it. We have met many new concepts in the last few pages and have
started using symbolic representations. We will be building on this
understanding in the pages to come so it is important for what follows
that you first master the material to this point.
If you feel comfortable with the material we have covered and had
no di
fficulty with Exercise 7.1 then it is time for us to go on and use
the operations of [STR] to illustrate further concepts.
7.4 GENERATION AND DERIVATION
The operations of formal systems consist in successive applications of
rules to states. Given an initial state, we can help ourselves to a dis-
tinction between states which will arise during the operations of the
system, and those which, while they meet the criteria for possible
states, never actually arise during the operations of the system.
Consider chess for example. States of the system are configurations
of thirty-two (or fewer) tokens of twelve (or fewer) types – subject to
certain restrictions – in an eight-by-eight array. There will, however,
be a very large number of possible states which never arise during a
game of chess. For instance, the state depicted in Figure 7.2 is impos-
sible to achieve from the initial position given the rules of chess.
We will call a state a generated state if it can be obtained from the
initial state through successive applications of rules. Generated states
then will always be the output of some rule. Consequently, there is a
simple e
ffective procedure for ruling out a state as generated. If a state
is generated, it will fit the output form of at least one rule, hence (by
contraposition) if a given state does not fit the output form of any
rule, it cannot be a generated state.
Unfortunately, determining whether a state is generated is not so
straightforward. Fitting the output form of a rule does not guarantee
that a state is generated – this is merely a necessary condition on gener-
ated states: its failure guarantees that we don’t have a generated state,
but its satisfaction does not guarantee that we do have a generated state.
If this is not obvious, here’s an analogous situation. If I’m in
Melbourne then I’m in Australia. So being in Australia is a necessary
 
61

---

condition for being in Melbourne. Hence, if I am not in Australia, I
am guaranteed not to be in Melbourne. However, being in Australia
does not guarantee that I am in Melbourne – I could be in some place
outside Melbourne but within Australia, e.g. Brisbane.
When we are interested in formal systems, we are interested in
determining whether or not certain states are generated. A generated
state is one which can be derived in the system. To show that we can
derive a state in a system is to give a derivation.
A derivation is a demonstration of the successive applications of
rules to states, beginning with the initial state of the system and
ending with the state we are interested in. Formally, a derivation is a
finite sequence of lines, the first of which is the initial state of the
system, the remainder of which are generated states, each obtained
through the application of some rule to the state on the previous line.
62
  