4.1.1 Formal systems
The computer is an interpreted automatic formal system. Therefore, it must be, first of all, a formal system. Many board games are formal systems too; so let's define such systems using the game of chess as an example. A formal system comprises three components:
- A set of tokens. These tokens may be of one token-type only, or of several different types. In chess, for instance, the tokens are the chess pieces: 32 of them, of six types. Tokens may be simple or complex, but we don't need to discuss this here.
- A starting state. This is a certain disposition of tokens with which the system is setup at the beginning of play. In chess, as you know, the start position looks like Figure 11.
- From this starting state, the tokens can be manipulated according to a set of rules. Each rule allows the system to move into a new state. In chess the rules stipulate how pieces can be moved legally around the board, the constraints on these movements, how pieces are captured, and so on. These rules can be quite complex. For example, a bishop can move any number of squares diagonally forwards or backwards from its current position, with the constraint that it cannot move onto a square occupied by a piece of its own colour, or over a square occupied by a piece of any colour. If any piece moves to a square occupied by a piece of the opposing colour, then that piece is said to be captured and is removed from the board. The rules of other board games may be simpler, but they are in exactly the same spirit.
Applying a rule legally moves the system into a new state. In chess these states are the board positions, as in Figure 12. Some of these positions may be specially designated as winning positions, but although this adds interest and excitement to games, it is not an essential feature of a formal system.
These three properties are sufficient to define a formal system fully. But formal systems have several important features that we need to be clear about.
First of all, they are discrete. What does this mean? Just this: for a formal system to work at all it must be possible to read and write tokens successfully. In our chess example, reading a token means recognising a particular piece, what type it is and what position it is in, etc.; writing a token means moving it to a new position. Formal systems must have a positive, reliable method of reading and writing. Here, positive and reliable have special meanings:
positive means that a token must be read and written with absolute success. This might sound a bit enigmatic, but it is simply the point Turing was making in the passage you considered in SAQ 7. A token is either recognised or it is not recognised; it is either written to a certain place, or it is not written to that place. There can be no half measures, no fractions, no degrees of uncertainty. This becomes clearer if we consider our chess example again. A knight in a cheap chess set may be a slightly different shape from the other knights; never mind – it is still a knight and not a bishop or a pawn. The knight may not be quite at the centre of square a4, it may even be close to one of the edges: that doesn't matter; it is still on a4, without qualification or doubt. If a piece is precisely on the border between two squares then the system must make a decision as to which of the two it is actually on. It cannot settle for an indeterminate answer, like 'halfway between a4 and b4'. It must decide on either a4 or b4. If it cannot make such a decision, it must make no decision.
reliable just means that the system must have an extremely high likelihood of success in reading and writing tokens. Of course, absolute perfection cannot be guaranteed, but the chances of success must be very high.
A simpler example might help. Haugeland asks us to consider a multi-position switch – let's say it's a three-position rocker switch, the positions being On, Off and Auto. The system has to be able to read the position of the switch. Quite likely, each time it is in a certain position its precise angle may be minutely different. But this doesn't matter: the switch must be read as either Off or On or Auto – it can never be some combination of, or compromise between, these. Similarly, when the switch is read as being at a certain position, a particular circuit must be opened or closed. A circuit can't be half opened or, say, the On and the Auto circuits both opened together. It's one or the other, all or nothing. It is a discrete system.
- Purely formal systems have the property of medium-independence. It does not matter what the tokens are made of, or how the system is realised physically. Again, our chess example is useful here. Of course, chess pieces can be made of wood, plastic, ivory, steel, or whatever. Chess has even been played with living people as pieces. This doesn't affect the nature of the game at all. Stretching the imagination a bit, one could play chess with ships at sea, or with each individual square of the board in a different county, or (given a super-technology) with an assembly of asteroids. As you know, chess can be played by computers, with no physical board or pieces at all. All that matters is that the tokens can be read and written, the 64board positions are identifiable and writeable, and the rules. You can see echoes here of the question I posed earlier about Hobbes' view of intelligence as computation with symbols.
- Given this, it follows that the formal system is self-contained – a closed world. In chess, it doesn't matter who is playing, where they are playing, what the weather is like, and so on. The only issues that are relevant are the positions of the tokens and the legality of each move, within the rules of the game. Even more importantly, the tokens themselves have no intrinsic meaning. It doesn't matter whether the knight token is shaped like a horse, or a piece of broccoli, or (as in computer chess) is just a pattern of voltages. The knight token is just that – a token. The only meaning a token has is the purely formal meaning that comes from what the rules allow one to do with it.
A formal system must be finitely playable. Again, this idea needs to be spelled out. A minimum definition of a finitely playable formal system is that in any state of the system a finite player must be able to:
- — deduce whether every possible move is legal or not;
- — find at least one legal move, or be certain that there are none.
Unfortunately, this doesn't take us much further forward. What is a finite player? Well, a useful definition from our point of view is this: for every state of the system, a finite player must be capable of deciding on each of the two points above by means of an algorithm.
I assume most of you know what an algorithm is already. If you want, just check your understanding against mine with the following brief question.
What is an algorithm?
I expect most of you wrote something along the lines of 'a set of steps for arriving at a certain result'. You may have added that after each step, the next step is fully obvious, with no alternatives. This is quite right, but there are two other points to add. First of all, an algorithm is infallible: it is guaranteed to provide the expected result, provided it is followed correctly. Secondly, an algorithm must be finite: it must be able to reach the result in a finite number of steps (although the number of steps may be as large as you like).
Now let's expand our discussion and look at automatic formal systems.