Classics of CS - Episode 2 - Computing Machinery and Intelligence [Updated]
Alan Turing is definitely in my top 10 favourite scientists. Not only because of ground breaking work in foundation of computer science but because of his power in abstracting problems. Of course, once you could see the right thing everything else will follow. In this episode of Classics of CS I am going to review one of his most famous writings, Computing Machinery and Intelligence.
First I would like to point out 3 interesting observations from the paper before I go through the paper.
First, the paper gives a sense of what was general understanding about thinking computers at his time. The most impressive part of this aspect for me is that when he discusses contrary views to how he poses the question “Can machines think?” 4 out of 9 opinions are completely unscientific, compared to what we understand as science or at least I understand today. These views seem to be just emotional reactions to a new radical view.</div><div><
</div><div>Second, Alan Turing once again, shows off his power of abstraction by posing a simple question such as “Can machines think?” in a different way in order to escape from all philosophical nightmares of defining what thinking is. He achieves this by changing the question to one that is in fact more technological. The technological view of science is not new and very well discussed by Karl Popper, philosopher and mathematician, in his work on scientific knowledge. So how Turing presents the problem? </div><div>
</div><div>The new form of the problem can be described in terms of a game which we call the "imitation game." It is played with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The interrogator stays in a room apart front the other two. The object of the game for the interrogator is to determine which of the other two is the man and which is the woman. He knows them by labels X and Y, and at the end of the game he says either "X is A and Y is B" or "X is B and Y is A." [...] The object of the game for the third player (B) is to help the interrogator. [...] We now ask the question, "What will happen when a machine takes the part of A in this game?" Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman? These questions replace our original, "Can machines think?"</div><div>
</div><div><hr/></div><div> </div><div>Whether this description is an accurate way of describing intelligence or not, which is discussed extensively in the paper, is a valid question but what matters here is that it differs greatly from conventional ways of thinking about intelligence, i.e. what the nature of thinking is?.</div><div>
</div><div>Third important observation for me is his insights and understanding of the future, which I greatly attribute to his power of abstraction. In this paper he touches on many different areas of Computer Science in the future which at his time was more like science fiction. He discusses possible futures for computers playing chess or making conversation with human beings, it is noteworthy to mention that the paper was written in 1950 and deep blue won the chess match against world champion Garry Kasparov in 1997 almost 50 years later. He also discusses possibility of machines learning. His view closely resembles well known methods in Reinforcement Learning and ideas similar to evolutionary algorithms such as genetic programming which was at its very early stages of development at that time.</div><div>
</div><div>I now continue with some highlights of the paper which I hope can be a good motivation to read the paper completely.</div><div>
</div><div>From the description of “imitation game” given above, he later connects the problem to an even more broader view of intelligence, theory of games and strategic behaviour:</div><div>
</div><div>It might be urged that when playing the "imitation game" the best strategy for the machine may possibly be something other than imitation of the behaviour of a man. This may be, but I think it is unlikely that there is any great effect of this kind. In any case there is no intention to investigate here the theory of the game, and it will be assumed that the best strategy is to try to provide answers that would naturally be given by a man.</div><div>
</div><div>After general description of the problem he proceeds with description of what is now known very well as Turing Machine, an abstract model of computation and comparing it with Babage’s analytic machine and Digital computers, in particular Manchester machine and describing universality of such machines, i.e. machines with discrete states. In part 5 he discusses a notion of capacity of a machine as total number of possible states a machine can take on.</div><div>
</div><div>As we have mentioned, digital computers fall within the class of discrete-state machines. But the number of states of which such a machine is capable is usually enormously large. For instance, the number for the machine now working at Manchester is about 2^165,000, i.e., about 10^50,000.</div><div>
</div><div>The logarithm to the base two of the number of states is usually called the "storage capacity" of the machine. Thus the Manchester machine has a storage capacity of about 165,000 ...</div><div>
</div><div>And finally he touches on the importance of Universal Turing Machine which later become the corner stone of future developments in the both practical and theoretical computer science:</div><div>
</div><div>This special property of digital computers, that they can mimic any discrete-state machine, is described by saying that they are universal machines. The existence of machines with this property has the important consequence that, considerations of speed apart, it is unnecessary to design various new machines to do various computing processes. They can all be done with one digital computer, suitably programmed for each case. It 'ill be seen that as a consequence of this all digital computers are in a sense equivalent.</div><div>
</div><div>Next in part 6 he discusses contrary views to the way he described the problem, whether machines can think?. However, before proceeding he makes an interesting prophecy about the future:</div></div><div>
</div><div>I believe that in about fifty years' time it will be possible, to programme computers, with a storage capacity of about 109, to make them play the imitation game so well that an average interrogator will not have more than 70 per cent chance of making the right identification after five minutes of questioning.</div><div>
</div><div>It is interesting how he, just like many other researchers at the beginning of AI era thought of the the problem in a very simplistic manner. To the best of my knowledge the problem he described is not yet solved and his prophecy for sure did not come true by the end of 20th century, other variation and prophecies about this problem can be found in Wikipedia.</div><div>
</div><div>9 possible objections that are discussed are as follows:</div><div><ol><li>The Theological Objection:
Thinking is a function of man's immortal soul. God has given an immortal soul to every man and woman, but not to any other animal or to machines. Hence no animal or machine can think.
This objection, today, has no validity and it is interesting how it took the first position in the list, which shows the atmosphere in which these discussions were taking place.
</li><li>The “Heads in the Sand” Objection:
The consequences of machines thinking would be too dreadful. Let us hope and believe that they cannot do so.
Again this argument is very weak and he gives a short response to it.</li><li>The Mathematical Objection:
The best known of these results is known as Godel's theorem ( 1931 ) and shows that in any sufficiently powerful logical system statements can be formulated which can neither be proved nor disproved within the system, unless possibly the system itself is inconsistent.
This is probably the dominant barrier to achieve the goal of building a thinking machine and he himself had enormous contribution to this area. His response to this challenge, to me at least, is unsatisfactory and that’s why I think the goal he had in mind was not achieved as he was expecting:
The short answer to this argument is that although it is established that there are limitations to the Powers If any particular machine, it has only been stated, without any sort of proof, that no such limitations apply to the human intellect. But I do not think this view can be dismissed quite so lightly. Whenever one of these machines is asked the appropriate critical question, and gives a definite answer, we know that this answer must be wrong, and this gives us a certain feeling of superiority. Is this feeling illusory? It is no doubt quite genuine, but I do not think too much importance should be attached to it.
</li><li>The Argument from Consciousness:</li>
This argument is very, well expressed in Professor Jefferson's Lister Oration for 1949, from which I quote. "Not until a machine can write a sonnet or compose a concerto because of thoughts and emotions felt, and not by the chance fall of symbols, could we agree that machine equals brain-that is, not only write it but know that it had written it. No mechanism could feel (and not merely artificially signal, an easy contrivance) pleasure at its successes, grief when its valves fuse, be warmed by flattery, be made miserable by its mistakes, be charmed by sex, be angry or depressed when it cannot get what it wants."
He makes extensive discussion on flaws of this mode of thinking about the problem which to certain extents is relate to attempts on how to define "thinking" at the beginning of the paper.
In it she states, "The Analytical Engine has no pretensions to originate anything. It can do whatever we know how to order it to perform"
This follows by an answer by Hartree (1949) who adds: "This does not imply that it may not be possible to construct electronic equipment which will 'think for itself,' or in which, in biological terms, one could set up a conditioned reflex, which would serve as a basis for 'learning.' Whether this is possible in principle or not is a stimulating and exciting question, suggested by some of these recent developments But it did not seem that the machines constructed or projected at the time had this property."
Finally he concludes his response with:
[...], I believe, to a fallacy to which philosophers and mathematicians are particularly subject. This is the assumption that as soon as a fact is presented to a mind all consequences of that fact spring into the mind simultaneously with it. It is a very useful assumption under many circumstances, but one too easily forgets that it is false. A natural consequence of doing so is that one then assumes that there is no virtue in the mere working out of consequences from data and general principles.
The nervous system is certainly not a discrete-state machine. A small error in the information about the size of a nervous impulse impinging on a neuron, may make a large difference to the size of the outgoing impulse. It may be argued that, this being so, one cannot expect to be able to mimic the behaviour of the nervous system with a discrete-state system.
This argument focuses on incapability of the discrete state machines compared with continues systems.
His response is for the machine to attach some sensible probability to its responses and we are still not able to distinguish the machine from human being.
It would not be possible for a digital computer to predict exactly what answers the differential analyser would give to a problem, but it would be quite capable of giving the right sort of answer. For instance, if asked to give the value of (actually about 3.1416) it would be reasonable to choose at random between the values 3.12, 3.13, 3.14, 3.15, 3.16 with the probabilities of 0.05, 0.15, 0.55, 0.19, 0.06 (say).
"if each man had a definite set of rules of conduct by which he regulated his life he would be no better than a machine. But there are no such rules, so men cannot be machines."
This last objection is also a variation of objection five with a difference that the kind of disability is telepathy, clairvoyance, precognition and psychokinesis. The difficulty is that we don't have a clear understanding of how these communication mechanisms work but nevertheless they are also a method of communication and therefore:
If telepathy is admitted it will be necessary to tighten our test up. The situation could be regarded as analogous to that which would occur if the interrogator were talking to himself and one of the competitors was listening with his ear to the wall. To put the competitors into a "telepathy-proof room" would satisfy all requirements.
</ol>Next he discusses on possibility of machines learning.
In considering the functions of the mind or the brain we find certain operations which we can explain in purely mechanical terms. This we say does not correspond to the real mind: it is a sort of skin which we must strip off if we are to find the real mind. But then in what remains we find a further skin to be stripped off, and so on. Proceeding in this way do we ever come to the "real" mind, or do we eventually come to the skin which has nothing in it? In the latter case the whole mind is mechanical. (It would not be a discrete-state machine however. We have discussed this.)
Estimates of the storage capacity of the brain vary from 1010 to 1015 binary digits. I incline to the lower values and believe that only a very small fraction is used for the higher types of thinking. Most of it is probably used for the retention of visual impressions, I should be surprised if more than 109 was required for satisfactory playing of the imitation game, at any rate against a blind man. (Note: The capacity of the Encyclopaedia Britannica, 11th edition, is 2 X 109) A storage capacity of 107, would be a very practicable possibility even by present techniques.
<div>In the process of trying to imitate an adult human mind we are bound to think a good deal about the process which has brought it to the state that it is in. We may notice three components.</div><div>
</div><div>(a) The initial state of the mind, say at birth,</div><div>(b) The education to which it has been subjected,</div><div>(c) Other experience, not to be described as education, to which it has been subjected.</div><div>
</div><div>Instead of trying to produce a programme to simulate the adult mind, why not rather try to produce one which simulates the child's?</div>
Our hope is that there is so little mechanism in the child brain that something like it can be easily programmed. The amount of work in the education we can assume, as a first approximation, to be much the same as for the human child.</div><div>
</div><div>So he first considers the possibility of modelling human mind in terms of capacity and then proceeds to lay down a method that forms as a basic program, childlike one in fact, that can evolve and learn.
Our hope is that there is so little mechanism in the child brain that something like it can be easily programmed. The amount of work in the education we can assume, as a first approximation, to be much the same as for the human child. </div><div>
</div><div><div>There is an obvious connection between this process and evolution, by the identifications </div><div>
</div><div>Structure of the child machine = hereditary material</div><div>Changes of the child machine = mutation,</div><div>Natural selection = judgment of the experimenter</div><div>
</div><div>One may hope, however, that this process will be more expeditious than evolution. The survival of the fittest is a slow method for measuring advantages.</div></div><div>
</div><div>and by drawing the connection from evolution to the problem of learning we observe that he is emphasising on Reinforcement Learning methods through punishments and rewards.
We normally associate punishments and rewards with the teaching process. Some simple child machines can be constructed or programmed on this sort of principle. The machine has to be so constructed that events which shortly preceded the occurrence of a punishment signal are unlikely to be repeated, whereas a reward signal increased the probability of repetition of the events which led up to it.
[...]
if the teacher has no other means of communicating to the pupil, the amount of information which can reach him does not exceed the total number of rewards and punishments applied. By the time a child has learnt to repeat "Casabianca" he would probably feel very sore indeed, if the text could only be discovered by a "Twenty Questions" technique, every "NO" taking the form of a blow. It is necessary therefore to have some other "unemotional" channels of communication. If these are available it is possible to teach a machine by punishments and rewards to obey orders given in some language, e.g., a symbolic language. These orders are to be transmitted through the "unemotional" channels. The use of this language will diminish greatly the number of punishments and rewards required.</div><div>
</div><div><div style="font-style:italic">The idea of a learning machine may appear paradoxical to some readers. How can the rules of operation of the machine change? They should describe completely how the machine will react whatever its history might be, whatever changes it might undergo. The rules are thus quite time-invariant. This is quite true. The explanation of the paradox is that the rules which get changed in the learning process are of a rather less pretentious kind, claiming only an ephemeral validity. The reader may draw a parallel with the Constitution of the United States.</div><div style="font-style:italic">
</div><div>Finally he touches on potential application of randomization in learning …</div></div><div>
</div><div>Suppose for instance we wanted to find a number between 50 and 200 which was equal to the square of the sum of its digits, we might start at 51 then try 52 and go on until we got a number that worked. Alternatively we might choose numbers at random until we got a good one. This method has the advantage that it is unnecessary to keep track of the values that have been tried, but the disadvantage that one may try the same one twice, but this is not very important if there are several solutions.</div><div>
</div><div>And concludes with two possible ways to achieve machines that can learn:</div><div>
</div><div><div>We may hope that machines will eventually compete with men in all purely intellectual fields. But which are the best ones to start with? Even this is a difficult decision. Many people think that a very abstract activity, like the playing of chess, would be best. It can also be maintained that it is best to provide the machine with the best sense organs that money can buy, and then teach it to understand and speak English. This process could follow the normal teaching of a child. Things would be pointed out and named, etc. Again I do not know what the right answer is, but I think both approaches should be tried.</div><div>
</div><div>We can only see a short distance ahead, but we can see plenty there that needs to be done.</div></div><div>
</div><div>This paper is indeed one of the most important papers of Alan Turing, and perhaps computer science in general, which gives many insights on how he was thinking about the nature of computing and learnability of machines by means of abstraction.</div></div><div>
</div><div>Update:
</div><div>To follow up this topic, I recently came across a very interesting talk by Dr. Elham Kashefi at School of Informatics, Edinburgh which extends this view of Turing to Quantum computation:
</div><div><div><div class="sites-embed-align-center-wrapping-off"><div class="sites-embed-border-on sites-embed" style="width:425px;"><h4 class="sites-embed-title">Quantum Turing test</h4><div class="sites-embed-content sites-embed-type-youtube"><iframe allowfullscreen="true" class="youtube-player" frameborder="0" height="355" src="//www.youtube.com/embed/3y7JCjaNZLY?rel=0&wmode=opaque" title="YouTube video player" type="text/html" width="425"></iframe></div></div></div></div>
</div>
Leave a Comment