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

Exercise 7.6
Give derivations in [BIN] for the states:
(a) 1001
(b) 0100101
(c) 000111
7.6 FORMALITY AND ISOMORPHISM
There is one last point to make concerning formal systems before we
move on and do something more interesting with them. It is import-
ant to appreciate that the only important or relevant properties of
formal systems are formal properties – properties of form.
For the purposes of the operations of a formal system, it is
never important how the system is physically realised. Consider chess
again. The pieces could be carved of wood or sculpted in stone, they
could be symbols on paper or on an electronic screen, they could be
coins or some other tokens pressed into impromptu service, they
could even be people on a su
fficiently large board.
The only features relevant to the distinguishing of states and the
application of rules are the arrangements of the system in e
ffectively
distinguishable forms.
Another way of saying this is that the operations of a formal
system are entirely independent of the medium (or substrate) in which
they are instantiated.
This should remind you of the substrate independence claimed by
functionalist theories of mind. For a functionalist, the only relevant
things to know about mental states are functions. Similarly, when con-
sidering formal systems, the only relevant things to know about are
forms.
 
67

---

The operations of a formal system are also entirely independent of
any interpretation of the system. While formal systems are, in princi-
ple, interpretable (I can, for instance, interpret a whole range of
instantiated formal systems as games of chess), I do not need to
engage in any interpretive work in order to be able to apply rules to
states – I need merely follow algorithmic procedures.
So, as is probably obvious to you by now, if am investigating some
system [A] which has all and only the same formal properties of some
system [B] then I just am investigating system [B]. If two systems are
formally equivalent then they are instantiations of the same system.
Whether I play chess with pieces, symbols, coins or people, I am
playing chess.
If two systems are formally equivalent – if they have all and only
the same formal properties – then we will say they are isomorphic to
each other, or isomorphisms of the same formal system.
A formal system [A] is isomorphic to a formal system [B] i
ff we can
derive [B] from [A] through uniform substitution of symbols. For
instance, consider the system specified below:
[S1]
Ø is a state
[S2]
If X is a state then so is Xa and Xb
[S3]
Initial state is: aabb
[R1]
aaXb
→ bX
[R2]
XbY 
→ aaXb
where X and Y are string variables
It should be fairly clear that the above example is isomorphic to the
original presentation of [STR]. In fact take any symbol you like and
substitute it uniformly for a, and similarly for b, and the result will be
another isomorphism of [STR]. The term ‘symbol’ can be interpreted
quite broadly here to include physical tokens such as coins or people –
we could, for instance, use ordered queues of men and women to
investigate [STR] (provided we could e
ffectively distinguish them).
The point of interest here is that for any formal system we might
care to investigate, there will be an isomorphic symbol system. This is
good news if we are interested in applying automated methods to the
investigation of formal systems.
Now that we have a su
fficient understanding of formal systems, their
features and their operations, it is time to put formal systems to the
68
  

---

use for which we have introduced them. In the following chapter, we
will see how we can use a particular kind of formal system to do com-