Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence
Download 1.05 Mb. Pdf ko'rish
|
document (2)
rider on e
ffective procedures. A procedure only counts as effective if it can be carried out in finite time. Counting the molecules in this book is an e ffective procedure. They are all presently configured in a solid and are pretty much sitting still, so we could, in principle, set up a very fine three-dimensional grid for reference and simply enumerate the molecules in each grid cube in order. It would take a very, very long time, but finite time. Counting the natural numbers, on the other hand, is not an e ffective procedure. Although the process is mechanical – name zero; name the successor of the last number you named; repeat the previous step until you can go no further – it cannot be completed in finite time. Every natural number has a successor – there are infinitely many of them. So implementing this process is not e ffective. 56 Now that we have developed a good understanding of e ffect- ivity, it is time to put the concept to work in characterising formal systems. 7.2 STATES AND RULES Formal systems are composed of two collections: a collection of states and a collection of rules. The specification of any given formal system consists in the specifications of its states and of its rules. We can define states over any entities we choose, provided distin- guishing between any two given states is e ffective. To give a few examples, we can define states as configurations of a game board, as configurations of a finite array of switches, as distri- butions of people in a finite array of theatre seats, or as distributions of mail in a finite array of pigeon holes. There must be only finitely many entities to define states over, otherwise any two states will not be e ffectively distinguishable. There can, however, be infinitely many states in the collection – many of the formal systems we will meet have infinitely many states, defined recur- sively over only a few entities. We will see how this trick is achieved in a moment. All of the above examples of states employ physical objects as tokens – pieces, switches, people, mail – and states are distinguished by the discrete arrangements of these tokens. We could, however, just as easily use symbols on paper as tokens and define states over strings of these symbols (provided of course that the strings are e ffectively distinguishable). All of the formal systems we will be playing with in our survey of computational theory will be just such symbol systems. Once we have defined a collection of states, we need to specify a collection of rules. Rules operate on states to generate other states. Rules, like states, are constrained only by considerations of e ffectivity. States can be defined over anything you like, provided any given two are e ffectively distinguishable. Similarly, rules can be anything you like provided they meet two constraints. Firstly, determining whether a given rule applies to a given state must be e ffective. Typically not all rules will apply to all states. Secondly, if a rule applies to a state, it must e ffectively deliver a finite set of possible output states. So rules take states, e ffectively modify them, and return distinct states. 57 Now that we know how to specify a formal system and what the constraints are on states and rules, let’s exemplify with our first toy formal system. 7.3 SPECIFICATION We want to discuss the properties and operations of formal systems, so let’s define a symbol system to play with. Let’s call it [STR] – it will be a string system. States of this system will be finite strings of the symbols ■ and ◊. To give a few examples: ■■ is a state of [STR], ◊◊■■◊■◊◊■ is a state of [STR] and ◊ is a state of [STR]. It should be fairly clear that any two states will be e ffectively dis- tinguishable. It may not be as clear that while there are only two types of symbols which we are defining states over, and while there can be only finitely many tokens of these in any given state, there are infinitely Download 1.05 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling