Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence
Download 1.05 Mb. Pdf ko'rish
|
document (2)
putation.
Let me say again that before you continue, it is important to have mastered the material to this point. We will continue building on this foundation in the next two chapters, so if there is anything of which you are uncertain, now is the time to revise. If, on the other hand, you are ready for some more challenging material, read on. 69 C H A P T E R 8 COMPUTABILITY The formal systems we have looked at so far have been very rudi- mentary string systems. Consequently, their useful application is rather limited. We can, however, employ formal systems to rather more interesting and useful ends. In particular, we can use formal systems to do computation. In this chapter, we are going to use a parti- cular kind of deterministic formal system – a register machine – to rig- orously define computability. 8.1 REGISTER MACHINES Register machines are theoretical entities. They can, however, be physically implemented (as can any formal system). Modern digital computers as we know them are implementations of a special kind of register machine, as we will see in the following chapter. Simple register machines, such as the ones we will examine in this chapter, can be straightforwardly implemented with piles of stones, coins or some other physical tokens. If you have a collection of coins or other tokens handy, it is highly likely to be useful to have them with you when working through the examples and exercises in this chapter. The pigeon hole analogy is quite apt when first starting to think about register machines. Recall from section 7.2 that we can define states over any collection of entities we choose, provided any two given states are e ffectively distinguishable. In particular, we could define states as distributions of letters in pigeon holes. This is directly analogous to the way we want to define states of register machines. States of register machines are contents of a finite sequence of registers. Registers are to be understood as discrete containers, hence the pigeon hole analogy. We will refer to these registers as R 0 , R 1 , R 2 , . . . , etc. There may be an infinite number of registers; however, we make the simplifying assumption that only a finite number of them have contents at any given time. 70 The content of a register can be represented as a natural number – the number of items which it contains. So, if we have a pigeon hole with three letters, or a discrete pile of three coins, then we can say we have a register which contains three (items). Precisely what the items are (letters, coins, assorted objects, etc.) matters not at all. Any enti- ties which can form e ffectively distinguishable states can serve as the symbols manipulated in a formal system. A sequence of three pigeon holes containing, one, three and two letters respectively will be isomorphic to a sequence of piles contain- ing one, three and two coins respectively. Both are isomorphic to a register machine with the contents, one, three, two, in the first three registers. States of register machines, then, can be represented as finite sequences of natural numbers. The sequence 1, 4, 16, 2, 27 represents a register machine with 1 in R 0 , 4 in R 1 , 16 in R 2 , 2 in R 3 and 27 in R 4 . In other words, the numerical sequence represents an ordered sequence of five piles containing 1, 4, 16, 2 and 27 things respectively. 8.2 PROGRAMS Register machines are formal systems. We now know what register machine states are – for all intents and purposes they are simply finite sequences of natural numbers. We next need to know what the 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