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

Figure 7.2
A non-generated state.

---

Let’s look at an example: suppose we wanted a derivation of the
state 
◊■■ in the system [STR]. Here’s a derivation which does the job:
1.
■■◊◊
initial state
2.
■■■◊◊
[R2] 

 ■■◊



 ø
3.
◊■■◊
[R1] 

 ■■◊
4.
■■◊■■■◊
[R2] 

 ◊■■
 
 ø
5.
■■■■◊
[R2] 

 ■■ 
 
 ■■◊
6.
◊■■
[R1] 

 ■■
The annotations on the right tell us how the state has been obtained –
which rule was used and how the string variables in the rule have been
instantiated. So, for example, state 2 was derived from state 1 (the
initial state) by applying [R2] to it and taking  to be 
■■◊ and 
 to
be ø (empty), resulting in an instantiation of the form 
■■◊ (where
 is 
■■◊), namely ■■■■◊◊.
But note that we could have applied [R2] to the initial state in a
di
fferent way. We could have taken  to be ■■ and 
 to be ◊, resulting
in 
■■■■◊. This means that [STR] is a non-deterministic formal system.
A system is deterministic if, for any given state, at most one rule
applies to it and in only one way. If more than one rule applies to any
particular state of the system, or if one rule applies to a particular
state of the system in more than one way, then the system is non-
deterministic.
Exercise 7.2
How many di
fferent ways can you apply [R2] to the state
■■■■◊◊ and what would the output be in each case? What
about the states 
■◊◊■◊◊ and ◊◊◊■■? What is the pattern?
You may have noticed that the result of applying [R2] to the initial
state in the alternative way we discussed (taking  to be 
■■ rather
than 
■■◊) is identical to state 5 in the derivation. This means that we
can actually get from the initial state to state 5 in the example in only
one step (rather than four).
It will often be the case that there will be more than one way of
deriving a given state. Often, we are interested in finding the simplest
(i.e. shortest) derivation.