Jaewoo Song
Jaewoo Song

Categories

  • Tech

Few of those majoring in computer science would not know “Alan Turing”.

Alan Mathison Turing (1912 ~ 1954), who was an English scientist, played a major role in creating the foundation of modern computer architecture.

The “Turing machine”, an automaton he suggested, became the basic concept of computing machines, which was the beginning of the “Von Neumann architecture,” a program-based computer structure that most modern computers follow.

He was a researcher who had worked in various fields such as mechanical engineering, mathematics, computer science and pychology, etc. and contributed greatly to the decoding of the German encryption system, “Enigma”, leading the World War II the victory for the Allies. (And the movie about that story, “The Imitation Game”, is one of my favorite.)

He is still the person I admire the most and the person an engineering student who studies the computer should not overlook along with “John von Neumann”.


And as a researcher interested in artificial intelligence, his most impressive work to me would be the “Turing Test”, which has been a standard for evaluating an AI’s performance.

In this post, I will have a brief review of the paper, Turing, A. M. (1950). Computing Machinery and Intelligence, which proposed the Turing Test and deep consideration on a thinking machine (Artificial Intelligence), which leads to the theory of a learning machine.



The Imitation Game

In the beginning, Turing asks a rather philosophical question: “Can machines think?”

And in answer to the question, he presents the famous Imitation Game (Turing Test), which has the following structure.


Assume that there are three people, $A$(a man), $B$(a woman) and $C$(an interrogator).

Without knowing the identity of $A$ and $B$, $C$ can only recognize two people as labels $X$ and $Y$ and asks them several questions.

$A$ and $B$ should answer the questions respectively, but the purpose of $A$ is to deceive $C$ to induce misidentification and $B$ should help $C$ to identify them properly.

For example, if $C$ asks “Will $X$ please tell me the length of his or her hair?”, $A$ cheats $C$ with an answer like “My hair is shingled, and the longest strands are about nine inches long.” and B can assist $C$ with a statement such as “I am the woman, don’t listen to him!”.


Turing asks if a machine can play the game well enough as $A$.

And this can be replaced by the initial problem from him, “Can machines think?”.


So the basic description of the game is as follows.

The description of the imitation game.


These are the examples of questions and answers which can be provided in the game.

The example Q&As of the imitation game.


Turing states that criticism may arise that the game itself is designed too disadvantageous for the machine.

Because a person is much slower and also can give a wrong answer that a machine is unlikely to give, which makes the interrogator be able to decide so easily.

But again, he argues that this objection is pointless.

… if, nevertheless, a machine can be constructed to play the imitation game satisfactorily, we need not be troubled by this objection.

… the best strategy is to try to provide answers that would naturally be given by a man.


In my opinion, the thinking machine Turing pursues is the one which understands the human incompleteness and gives a human-like answer.

That is, I think this is a kind of perspective that if a machine can make a mistake or conceal its intention by purpose, that is a truly “thinking machine”.

Furthermore, it fits today’s argument saying that the moment when the AI becomes really scary is not when it just imitates the correct answer, but when it intentionally deceives us after judging what a person might do naturally.



Digital Computers

Turing defines “a machine” in a little bit restricted way suggesting that only a particular kind of machine called “digital computer” is permitted to participate in the game.

This seems too narrow and rash, but he states that actually since a digital computer has no difficulty in following human computations, we can just set the definition of a machine into this without special problems in the real world.


The digital computer consists of three main parts.


  • Store => Memory unit
  • Executive unit => Process unit (Logic unit)
  • Control => Control unit


These are very similar to components which modern computer architecture has.

Store is a part that stores various information, which can be seen as memo paper or a rule book for humans.

Executive unit performs each operation and this is the same as the human calculation ability.

And control plays a role in controlling the overall process to follow the pre-defined table of instructions in proper order, which is not different with the basic logic of human computer.

In summary, to perform a certain function, computer stores various information, such as commands and numbers, in the store and calculates it under the control of the control unit.


An interesting part is that Turing considers not only simple arithmetic operations, but also more complicated ones.

For instance, there are instructions like below.

The examples of the loop and the condition in digital computer instructions.


They look like a conditional statement and a loop which are very familiar to us.

With Turing’s statement below, we can see that a digital computer can conduct advanced operations such as repeating certain functions or determining if a certain condition is satisfied.

Instructions of these latter types are very important because they make it possible for a sequence of operations to be repeated over and over again until some condition is fulfilled, …


That is, Turing thought that a digital computer can mimic the actions of a human computer very similarly.

… they can in fact mimic the actions of a human computer very closely.


Of course, a computer cannot take orders in raw human language.

So he mentions “Programming” as a process of making instructions into understandable forms for a machine, which can also be seen as the programming we know nowadays.

He says that a digital computer can perform what all “discrete-state machines” can do just with proper programming without designing a new machine, which makes it “universal”.


A discrete-state machine is a simple form of automata that can transfer to the next state according to the current state and input.

Even though we know that there are no strictly discrete situations and everything is continuous, Turing says we can ignore the intermediate states.

For example, when we flip a switch, there are definitely intermediate steps from previous to next, but we do not care about them since we just want one of two states, on or off.


Anyway, the paper shows us a simple discrete state machine as follows.

The example of a simple discrete state machine.


As we can see, generally we can predict the next state easily if we know the current state and what input might come.

Of course in many real cases, a small error in the initial condition can make a huge effect on later results, and Turing argues that the property that this phenomenon does not occur with a discrete state machine is important.

In other words, even in the case of real machines, accurate knowledge of each state can guarantee accurate next predictions.


Additionally, he makes an important assumption that in order to make a digital computer substitute all discrete-state machines, it has to have infinite storage.

Like a human computer is provided with a huge number of papers, a machine also has to get sufficiently large storage and Turing says it is not impossible as follows.

Of course only a finite part can have been used at any one time. Likewise only a finite amount can have been constructed, but we can imagine more and more being added as required.

This is because as a matter of course, a digital computer should write all combinations from symbols it has stored in the paper and adequate memory space can guarantee sufficiently fast operation speed.


As we have discussed so far, with large memory and well-constructed instruction table, a discrete state machine can predict what to do next very well and there is no reason why a digital computer can do it, as he says.

Eventually a digital computer is universal and with good programming it can perform various tasks instead of other machines.


In my personal opinion, all these statements are closely connected to the “Church-Turing thesis”, which means that all effective computations and algorithms can be conducted with a “Turing machine”.

In other words, a digital computer Turing suggests in this paper can be seen as a Turing machine which becomes a basis of Von Neumann architecture and it seems that this turing machine can perform all computations which other machines can do, so we can assume this single digital computer as a representative machine for the imitation game.

Eventually, Turing finishes the discussion on the definition of machines after stating that it would be enough for us to consider “a machine” in the initial question “Can machines think?” as just a digital computer $C$.



Contrary Views on the Main Question

This part is about various possible contrary views on the main topic, “Can machines think?” and Turing’s refutations accordingly.

Although it takes up quite a lot, I think most of the contents look not technical, but more philosophical and abstract, so I will briefly summarize this part and go to the next chapter, which is my favorite in this paper.

Turing suggests these possible opposite views and replies as follows.


  1. The Theological Objection: God gave souls to humans but not to other animals or machines. Thus the machine cannot think.

    • Turing says that this view implies a serious restriction of the omnipotence of the Almighty. Also he says this theological point of view is not an interesting refutation with his present knowledge.
  2. The ‘Heads in the Sand’ Objection: The consequences of machines thinking would be too dreadful so let us hope that they cannot.

    • Turing argues that no refutation is required for this and consolation would be more appropriate.
  3. The Mathematical Objection: There are various mathematical logics that can show the limitations of the powers of discrete-state machines, such as Gödel’s theorem and results from Church, Kleen, Rosser, and Turing.

    • Turing thinks that it has only been stated, without any sort of proof, that no such limitations apply to the human intellect. Additionally, he states that too much importance should not be attached to a feeling of superiority when we think the machine’s answer is wrong.
  4. The argument from Consciousness: No machine has a consciousness of itself. So it cannot feel pleasure, grief, angry, etc.

    • Turing points out that the most extreme case of this view can be sure that a machine thinks after being the machine and feeling oneself thinking. In the same view, it is the only way for us to know that a person thinks, but we generally assume that everyone thinks as a polite convention.
  5. Arguments from Various Disabilities: If we can make machines able to do all the things, but we will never be able to make one to do $X$. ($X$ can be various: be kind, resourceful, make mistakes, enjoy strawberries and cream, learn from experience, be the subject of its own thought, etc.)

    • Turing says that this view came from a principle of scientific induction which concludes that diversity of tasks is necessary property of a machine in general. And like he mentioned before, this is caused by the lack of storage, so adequate memory space can solve it.

    • He replies to each example more specifically as follows. First, it is idiotic to make a machine do such things like enjoying strawberries and cream. And in the case of mistake, he says we should not be confused between errors of functioning and errors of conclusion and there is no reason why a machine can make a mistake to fool the interrogator(to perform the imitation game well). Lastly, a machine can be its own subject matter, for example when solving an equation, even if in a human point of view it seems not.

  6. Lady Lovelace’s Objection: Machines have no basis for self-thinking and learning. In other words, machines can’t really do anything new.

    • Turing says he is in thorough agreement with this and he is sometimes surprised with unexpected results from a machine too. But he also says that he does not throw any doubt on his credibility, which leads to the next chapter about a learning machine.
  7. Argument from Continuity in the Nervous System: Discrete state machine cannot mimic the human nervous system since it is not continuous.

    • This was mentioned as less important in previous discussions on a digital computer. Also Turing argues that even if a discrete state machine cannot work as exactly the same way as the contiguous differential analyzer, it is capable of giving the right answer.
  8. The Argument from Informality of Behaviour: It is not possible to produce a set of rules purporting to describe what a man should do in every conceivable set of circumstances.

    • Turing says that he is skeptical about the existence of such a set of rules and if there is one, then a man would be no better than a machine. Additionally, if we could be sure of finding such laws, then given a discrete-state machine it should be possible to discover by sufficient observation to predict its future behaviours.
  9. The Argument from Extra-Sensory Perception: If we adopt the extra-sensory perception such as telepathy, clairvoyance, precognition and psycho-kinesis, then all our usual scientific ideas can be ignored.

    • Turing says that once one has accepted them, it does not seem a very big step to believe in ghosts and bogies. And he says putting the competitors into a ‘telepathy-proof room’ would solve the problem. (I think this is a kind of Turing-style humor…)



Learning Machines

Finally, Turing suggests the concept and the possibility of a learning machine which takes new knowledge over and over.

This part is a further specific refutation to the 6th contradictory view and can be seen as Turing’s view on the direction in which the thinking machine should follow.

Especially I think it will be more interesting if we compare the machine learning we know today with the learning methods presented in the paper.


Turing believes that a machine can also be injected into knowledge like the human mind.

And he says that it is also a matter of “programming”.

Then what should be programmed to make a machine able to think by itself and become learnable?


He proposes three main components like below.


  1. The initial state of the mind, say at birth.
  2. The education to which it has been subjected.
  3. Other experience, not to be described as education, to which it has been subjected.


The point is that we can assume the machine starts as a child, instead of simulating the adult mind.

This is quite natural since an actual human is born as a child first, then becomes an adult who can perform his/her duty/function after various educations and experiences.

This initial state can be seen as an initialized model before starting actual training in machine learning.

In addition, the following statement indicates that the performance of the model may vary depending on how it is initialized, and this is consistent with the current concept of machine learning, even the fact that it should be verified through repeated experimentations.

One must experiment with teaching one such machine and see how well it learns. One can then try another and see if it is better or worse.


And this is the most interesting part.

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 you have studied machine learning, then it would be easy to notice that the above process Turing suggests is very similar to one of its algorithms, more specifically the reinforcement learning.


Also, he suggests the method to make this teaching process more effective as follows.

One might try to make it as simple as possible consistently with the general principles. Alternatively one might have a complete system of logical inference ‘built in’.

Important amongst such imperatives will be ones which regulate the order in which the rules of the logical system concerned are to be applied.

To me, it seems the advantage of using a pre-trained model in other words, the transfer learning.

It shows us that giving rewards after constructing the general and universal logic system is more beneficial than training a machine from scratch.


And Turing describes the important feature of this learning machine like below.

An important feature of a learning machine is that its teacher will often be very largely ignorant of quite what is going on inside, although he may still be able to some extent to predict his pupil’s behaviour.

Isn’t this also very familiar?

It is very similar to the characteristic of most deep learning models, which are described as black boxes inside.

That is, we can predict and design a machine’s action to some extent but we cannot know what is going on in it specifically.


Additionally, he mentions the randomness of a machine’s results and most programs we inject can result in something that does not make sense to us.

This randomness eventually leads to the continuing process of finding the actions that can satisfy the teacher through experiments and searches, which is also very similar to the modern machine learning technique we use that finds the optimal point through repeated attempts.



This is the conclusion of this paper.

We may hope that machines will eventually compete with men in all purely intellectual fields.

One of the examples he suggests is chess and TuroChamp, the chess AI Turing designed, was actually developed and shown in 2012 to compete with a human chess player.

Also, the emergence of AlphaGo’s victory over many human Go players in 2016 shows that the arrival of Turing’s dream machine is not far off.


So this is the end of the review about his monumental publication, Computing Machinery and Intelligence.

Because of my lack of knowledge and interpretive capacity, I wonder if the contents have conveyed what he was trying to say properly.

Still, through this opportunity, I was able to think deeply about the thoughts of Alan Turing, the most respected scholar, his style, and the direction he pursued.

It is not only surprising that the modern technologies and concepts we encounter actually emerged in the paper from 70 years ago, but also very impressive that we have a lot of tasks to do to fulfill his goal at that time.

Of course, there is a case of artificial intelligence that has passed the Turing test, but the efforts of many researchers are still needed to discover and realize more advanced technologies.


We can only see a short distance ahead, but we can see plenty there that needs to be done.



Turing, A. M. (2009). Computing machinery and intelligence. In Parsing the turing test (pp. 23-65). Springer, Dordrecht. https://link.springer.com/chapter/10.1007/978-1-4020-6710-5_3.
Computing machinery and intelligence. (2017, Oct 20). https://blog.acolyer.org/2017/10/20/computing-machinery-and-intelligence/.
Church’s Thesis for Turing Machine. (2020, May 20). https://www.geeksforgeeks.org/churchs-thesis-for-turing-machine/.
What is Godel's Theorem?. (1999, Jan 25). https://www.scientificamerican.com/article/what-is-godels-theorem/.