Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence
Download 1.05 Mb. Pdf ko'rish
|
document (2)
many states. This may be clearer in a moment when we give a formal
specification of states using recursive definition; however, we first need to help ourselves to a few more concepts. Firstly, we need the concept of an initial state. Specifications of formal systems often include an initial state, or beginning configur- ation of the system. All board games have an initial state – state A in Figure 7.1 represents the initial state of chess. Secondly, there is a special and important state of this system (and typically of string systems in general) and this is the empty string. The empty string is precisely that – a string of no symbols at all. We will write it as ø. It is important to remember that the empty string is a string, and – by stipulation – is a state of [STR]. The need for the empty string will become apparent in a moment. We will also need to employ string variables which we will write as or . String variables stand for strings – any string you like (includ- ing the empty string). We need to make use of string variables and the empty string in order to formally specify rules of su fficient generality. Again, this will become apparent in a moment. Finally, we need to represent string concatenation. String concate- nation simply means joining two strings together – i.e. writing them one after the other. We will write the concatenation of two strings and as – i.e. their typographical concatenation. So, if is standing for the string ■■◊ and is standing for the string ◊■ then will be ■■◊◊■ and will be ◊■■■◊. Note that ø ø ø . In other words, any string is identical to its concatenation with the empty string, regardless of 58 where you put it. In simpler terms, tacking on nothing always leaves you with what you started with. Before we give the complete formal specification of [STR], let’s first just give an informal description of how the rules of this system will work. [STR] will have only two rules. Rule one will say that we can take any state which begins with two boxes and ends with a diamond (and has whatever you like – including nothing – in between) and output a state which begins with a diamond and is followed by whatever came between the two boxes and the diamond in the input state (which may be nothing). Rule two will say that we can take any state which has a diamond in it somewhere (and has anything you like – including nothing – before and after the diamond) and output a state which begins with two boxes, ends with a diamond, and in between has whatever it was that came before the diamond in the input state. Explaining the rules informally like this is rather laborious. However, the formal specification is quite concise and tidy, as the fol- lowing demonstrates. [STR] [S1] ø is a state [S2] If is a state then so is ■ and ◊ [S3] Initial state is: ■■◊◊ [R1] ■■◊ → ◊ [R2] ◊ → ■■◊ Now, let’s carefully interpret this formal specification and make sure that it captures the system we have informally described. The first thing to note about the formal specification is that, while giving an informal description of the system took many wordy para- graphs, the formal specification is given in five short lines. There is great economy of expression to be had in formalisations. It may not be clear, on first examination, that [S1] and [S2] capture all and only the states of this system – this is an example of recursive definition. [S1] is the base clause – it simply stipulates that the empty string counts as a state. All the work is done in [S2] – the recursive clause – which says that if you take any state and tack on a ■ or a ◊ the result will be a state. A little thought should su ffice to show that any finite string of the symbols ■ and ◊ can be constructed through repeated applications of [S2], given [S1]. [S3] merely stipulates the initial state. 59 The astute reader may wonder whether [S1] and [S2] capture only the states of the system – the worry being that they do not seem to explicitly rule out infinitely long strings. We need not be concerned, however – if you take any string of finite length and add one symbol, the result will always be a string of finite length. We have already given informal readings of [R1] and [R2]. Work back and forth between those two paragraphs and their formal speci- fication above until you are convinced that [R1] and [R2] do in fact capture the content of those paragraphs. The left-hand side (LHS) of the arrow of each rule describes the form of input states and the right- hand side (RHS) describes the form of output states. It should be clear now why we want to use string variables. Using string variables lets us refer to a class of strings which share the same form (e.g. any string which begins with . . . and ends with . . . ). String variables always refer to the same string in the LHS and the RHS of the rule – that is precisely the point in using them. Whatever you take to be in the input side of a rule must be the same in the output side of that rule. There are no restrictions on string variables between rules though: having taken to be one string in the application of one rule has no bearing on what can be in further applications of rules, or even in further applications of the same rule. If this is not yet clear it should become so in a moment when we examine the operations of the system. It may still not be terribly clear why we want to be able to refer to the empty string, so let’s demonstrate its use. Rule [R1] will apply to the initial state ■■◊◊. In this case, what is in between the initial ■■ and the final ◊ is a single ◊, so in applying the rule we take to be ◊, in which case the output of [R1] will be ◊◊. Another way of saying this is that the initial state is of the form required to apply [R1], namely the form ■■◊ (where in this case ◊). Hence, if we apply the rule, we get an output state of the form ◊ (where ◊), namely ◊◊. Rule [R1] will also apply to the state ■■◊ as it is of the form ■■◊ (where ø). By similar reasoning [R2] will apply to the states ◊, ■◊ and ◊■. This is why we need the empty string. 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