Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence
Download 1.05 Mb. Pdf ko'rish
|
document (2)
generation. If we take the initial state of the system to be its axioms
and the proof theory of the system to be its rules, then decidability simply amounts to whether or not one can show, of any arbitrary sen- tence, whether or not it is included in some state derived from the initial state in accordance with the rules. Those readers who have done a first course in logic will know that the propositional calculus is decidable, but the predicate calculus is not. Do not be concerned if the previous paragraph means little or nothing to you. It is merely intended as an aside for those with some exposure to logic. It was in the course of arguing that a particular logical system is not decidable (the predicate calculus for those for whom that means something) in his 1936 paper – On Computable Numbers, with an Application to the Entscheidungsproblem – that the British math- ematician Alan Turing formally defined computability and, in doing so, laid the foundation for what has become computer science. Turing defined computability in terms of theoretical machines which are now known as Turing machines. It is far more common in the computational theory literature to see talk of Turing machines than it is to see talk of register machines. Turing machine com- putability and register machine computability are, however, provably equivalent – they can compute all and only the same functions. 86 Wherever you see talk of Turing machines, or Turing computability, you can substitute this with register machines and register machine computability. I chose to employ register machines for an initial presentation of computational theory for two reasons. Firstly, simple register machines are readily amenable to physical implementation with a col- lection of tokens (coins, buttons, etc.). This can serve as a great aid to understanding their operations. Secondly, while register machines and Turing machines are functionally equivalent, the mechanics of register machine operations are closer to the way computation is actu- ally implemented in computers as we know them In his 1936 paper, Turing argued that all and only those procedures which were algorithmic could be computed by Turing (register) machines. In another paper published in 1936, an American mathematician, Alonzo Church, argued that the informal notion of e ffective calcula- bility could be understood (at least for calculations over positive inte- gers) in terms of the formal notion of a recursive function. In both cases, Church and Turing aimed to tie a notion which was well under- stood informally – that of algorithmicity, or e ffectivity – to a concept for which there was a precise formal definition. The Church/Turing thesis, as it is now commonly referred to, can be expressed quite concisely as: all and only e ffective procedures are computable functions. It is important to appreciate that the use of ‘computable’ in the Church/Turing thesis refers to a particular formal understanding of computability, namely register machine computability as we have defined it. This may not seem terribly important but there is consid- erable scope for misinterpreting the Church/Turing thesis if one does not keep this in mind and it is common to see such misunderstanding in the literature. It is also worth pointing out that the equivalence between e ffective procedures and computable functions is a thesis and not a theorem. In other words, it is a proposed equivalence but it is not a proven one. There seems, however, by the very nature of the thesis, to be little chance of actually proving it, since it equates a formal notion with an informal one. One direction of the thesis – that all computable functions are e ffective procedures – is obvious since we have defined computability in terms of e ffective procedures. The other direction – that only computable functions are e ffective procedures, or that all e ffective procedures are computable functions – is less obvious. It is the case, though, that since 1936 we have amassed considerable 87 evidence in favour of the thesis and run across no counter-examples to it. So the Church/Turing thesis provides us with answers to both of the questions we identified at the beginning of this chapter. We now know precisely which functions are computable – all and only those which are algorithmic. We also now have a formal characterisation of e ffectivity/algorithmicity – precisely that which we gave for com- putability in section 8.5. According to the Church/Turing thesis, there is a register machine program for any given algorithm (since all e ffective procedures are register machine computable). Add to this the fact that register machine programs are deterministic formal systems, and that the operations of any given deterministic formal system are algorithmic, and we can see that algorithmic procedures, e 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