Skip to content
Skip to main content

About this free course

Download this course

Share this free course

Machines, minds and computers
Machines, minds and computers

Start this free course now. Just create an account and sign in. Enrol and complete the course for a free statement of participation or digital badge if available.

4.1.4 Interpreted automatic formal systems

Finally, the matter of Haugeland's point about interpretation. Computers are interpreted automatic formal systems. So what does 'interpretation' mean here?

Interpretation is concerned with the whole question of meaning, and meaning is the province of the study known as semantics. Questions of semantics too often lead one into a philosophical morass that I want to step gingerly around. Let's start with our chess example again. Chess is a formal system. Earlier I claimed that in formal systems the tokens have no intrinsic meaning. But this claim needs to be examined a bit more closely.

SAQ 10

If, say, the knight token in the formal system of chess has any meaning at all, what is it and where does it come from?


I think this question may be easier to answer than it was to phrase. The only meaning the knight token has comes from what the rules allow us to do with it. The knight token is the one that can be moved two squares up (or back) and then one square to the left or right, or one square up (or back) and then two squares to the left or right.

This is why it's irrelevant whether the knight token is made of plastic or of plutonium, or is shaped like a beetle or like Batman. The only meaning it has within the formal system is the characteristic moves it is allowed to make. We can call this sort of meaning the operational semantics of the token.

However, the fact that the tokens of a formal system have this kind of semantics doesn't necessarily mean that such systems are interpreted systems. In interpreted systems, the tokens have another meaning: they stand for, they refer to, things in the world outside the system. Chess is a formal system. It is a formal system that can be automated. But it is not an interpreted formal system. The tokens have no meaning outside the rules of the game. So let's leave chess for a moment and work with another example.

In interpreted systems, the meaning of a token is the thing, or things, in the world that it refers to. They cease to be mere tokens and become symbols, standing for real things. In the jargon, they have a denotational semantics. To take another example, again suggested by Haugeland, suppose we have a system comprising

  1. fourteen tokens, the letters a through to n;
  2. various start states consisting of strings of tokens;
  3. a set of rules, one for each start state, each of which leads to the addition of one or more tokens to the end of the start state. After a single move the system halts.

A couple of examples of the system in action will be enough.

Table 1
Start stateNew state after move
akaaka ce
bkfnbbkfnb b
cgmamicgmami egj

At the moment this looks like a purely formal system, and a pretty pointless one too. But now suppose that each of the various tokens stands for one of the numbers 0 through to 9, or for one of the arithmetic operators +, –, * and / (that is, add, subtract, multiply, divide). For instance, a→7, b→3, k→+, and so on. Substituting objects for the tokens, then, an interpretation of the system makes might look like this:

Table 2
Start stateNew state after move
7 + 73 + 6/3
7 + 7143 + 6/33

... and so on. Our old friend, school arithmetic. However, if you try the following straightforward interpretation:


you get the following nonsensical result:

Table 3
Start stateNew state after move
+ 6 ++6+ *0
–619––619– –
*2 8+8 4*2 8+8 4 025

Clearly, only one set of denotations, one mapping of tokens to numbers, will produce the standard arithmetical system from our examples in Table 1. But which one? Don't bother to try and work it out. There are over 87 billion ways to ascribe fourteen symbols to fourteen numbers and signs. The right interpretation in this case is:

b→3 i→5
c→1 j→0
d→8 k→+
e→ 4 I→–

which you can see will give us correct arithmetical expressions and results for the examples in Table 1. So here is an example of an interpreted formal system. And, as we all know, such systems can be automated. Our pocket calculators tell us so.

That's almost as far as I want to go here. But one final point is important, though. Consider this mapping:


If we then lay out our original examples according to this interpretation, we get:

Table 4
Start stateNew state after move
0+ 00+0 24
26 * 0 * 826 * 0 * 8 469

This is a different kind of nonsense to that of Table 2. The arithmetical expressions in the left-hand column are all quite valid, unlike the jumble of symbols we got in Table 2. However, the results we get after making the move are just plain wrong. The interpretation produces statements that are quite correctly arranged but are simply untrue. So my final point about interpreted formal systems is this: their rules must be designed to be truth-preserving. Every rule that operates on a certain state of the system that is true under a certain interpretation should produce a new state that is also true under that interpretation. I know you'll want to take my word for it, but if you like you can verify that the system I've presented is truth-preserving under the interpretation I offered.

Exercise 12

This discussion all started with my proposal that digital computers are interpreted automatic formal systems, comprising tokens, rules and so on. Write a few notes relating what you know of how digital computers fit into these definitions.


It should be fairly easy to state how the concept of the digital computer fits in with these definitions. Considering the computer running a program as a formal system:

  1. The tokens are the various data structures of the program, distributed across the memory of the machine. These data structures may just be individual bits, or variables, or complex structures such as arrays or objects (or arrays of objects, and so on).
  2. The start state is the initialisation of these data structures to their starting values, or defaults. The control unit of the computer also sets the program counter to the first instruction in the program.
  3. The rulesare embodied in the program, a finite algorithm that specifies exactly how the tokens are to be read and written, and in what order these read/write operations are to take place.

    We should note that the computer has all the other properties of a purely formal system:

  4. It is discrete, because the digital nature of the device means that ultimately it deals only in 1s and 0s, which must be read and written reliably, with absolute success, as 1s and 0s, with no intermediate values allowed.
  5. It is medium-independent. This may seem a bit more perplexing, because we are so used to the idea of computers as silicon-based, electronic devices. However, it is only for reasons of speed, size and practicality that they are so. There is no theoretical reason why a digital computer might not be constructed out of sealing wax or glass beads. Babbage's analytical engine and the abacus are, in their way, computers too.
  6. We know that computers are finitely playable, as the programs they run are, without exception, algorithmic.

Now, obviously a computer is an automatic formal system, as it runs on its own. The referee function is built into the CPU, ensuring the correct starting point of the program and that the algorithm specified in the program is executed in the correct order. The algorithmic nature of the program ensures that each step can be identified positively and reliably.

Finally, a computer is an interpreted system. Computers are tools that we use for our own real-world purposes. What they do, and the results they produce, have a meaning for us. The data inside programs stand for things of interest to us in the world outside the program.

To grasp this last point a little more clearly, consider a meteorological program simulating some portion of the Earth's atmosphere. The program is running on a supercomputer and is being used for weather prediction. Now let's say that at location F734CD61 in the computer's memory is a variable containing a certain value. As far as the machine is concerned this is just a token, and at some point in the execution of the program it is required to write a new value into this slot. However, for the human builders and users of the system the token at F734CD61 has a meaning. It refers to a measurement of atmospheric pressure at a certain spot on the Earth's surface; the new value that is written for the token stands for the pressure to be expected at that spot at a certain time in the future. Although the machine treats the token purely formally, we interpret it: it has been given a human meaning.

These interpreted automatic formal systems, these computers, are a dominant technology of our time. They are clearly immensely capable tools. Given their central role in the artificial intelligence project, it's time to give a little thought to what they can do. More importantly, though, are there things they can't do?