C:
Please write me a sonnet on
the subject of the Forth Bridge [a bridge over the Firth of Forth, in Scotland].DARPA's supercomputer Bayley is the prime suspect in the murder of an AI researcher. According to DARPA's team, Bayley represents their success in the creation of Artificial Intelligence and they are not accountable for its actions. In this episode Charlie, Amita and the FBI try to crack this case to confirm if DARPA's claims hold to be true and Bayley has passed the Turing Test.
The Turing Test is the most known test to verify Artificial Intelligence. It was proposed by British mathematician Alan Turing (see Tangent) in an article published in 1950 in the journal "Mind" and titled "Computer machinery and intelligence".
Below, we will briefly explain some aspects of the Turing Test and the concept of Turing Machine. Alan Turing introduced Turing Machines in an earlier paper published in 1937 in the Proceedings of the London Mathematical Society and titled "On Computable Numbers, with an Application to the Entscheidungsproblem". Turing's work on computability and artificial intelligence has been so influential that many consider him the father of modern computer science.
Alan Turing created the Turing Test after considering the following question: Can machines think? Due to the controversial nature of the question he proposed an alternative question, namely: Are there machines that can do well in the Turing Test? The first version of Turing's test, or the "imitation game" as Turing introduced it in his paper, can be described as follows:
Suppose that three people take part of a game: A man (A), a women (B) and an interrogator (C), who can be of either sex. The interrogator (C) is in a different room than (A) and (B). (C)'s object of the game is to identify who of the two is the man and who is the women. In order to do so, (C) is allowed to address questions to (A) and (B). However (C) never hears the answers directly from (A) and (B) but through a teleprinter or intermediary. The objective of (A) is to trick (C) into a wrong identification, while the objective of (B) is to help the interrogator.
Turing proceeds to ask the following question:
"What will happen when a machine takes the part of (A) in this game?"
If the interrogator decides wrongly as often when the game is played with the computer as he does when the game is played between a man and a woman, it may be argued that the computer is intelligent. After this introduction Turing gives an example of a hypothetical conversation between the interrogator and player (A):
C:
Please write me a sonnet on
the subject of the Forth Bridge [a bridge over the Firth of Forth, in Scotland].
A: Count me out on this one. I never could write poetry.
C: Add 34957 to 70764.
A: (Pause about 30 seconds and then give the answer) 105621.
C: Do you play chess?
A: Yes.
C: I have a K at my K1, and no other pieces. You have only K at K6 and R at R1. It is your move. What do you play?
A: (After a pause of 15 seconds) R-R8 mate.
It might be hard to notice
at first glance but after a long delay the
witness (A) makes a mistake in the arithmetic question. It might be
argued that this is a sign of human behavior. However, if the
respondent were a machine there are some possible explanations. For
instance, a hardware error or a ploy inserted by the machine's
programmer to trick the interrogator.
Aware of the controversial nature of the problem, Turing lists some objections that could arise on the notion that machines could think. Below we will mention a few of them:
The Theological Objection: Thinking is a function of the soul and God reserved it for humans but not for animals or machines.
The Mathematical Objection: There exist mathematical statements that can be seen to be true by humans but cannot be mechanically proven. Hence, there does not exist a machine that represents the human mind.
Arguments from disabilities: A machine can mimic many human behaviors but there are numerous human features that cannot be mechanically replicated. Among them are: Be kind, friendly, beautiful, have a good sense of humor, etc.
For a more detailed discussion on the Turing Test we strongly recommend Chapter XVIII of Douglas R. Hofstadter' book "Gödel, Escher, Bach: an Eternal Golden Braid". In what follows we will explain the concept of Turing Machines. In the "imitation game" described above the machine playing the role of (A) is understood to be a Turing Machine. This type of machines is considered by Turing in all his studies on Computability and Artificial Intelligence.
This type of machines was defined and used for the fist time by Alan Turing in his remarkable work "On Computable Numbers, with an Application to the Entscheidungsproblem". In this paper, Turing resolved a question known as the Entscheidungsproblem or Decision Problem. The Decision Problem conjectured the existence of a mechanical process to decide whether a given mathematical statement is true or false. This problem is part of a three-fold question proposed by David Hilbert in 1928: Is mathematics complete, consistent and decidable? Czech mathematician Kurt Gödel gave a negative answer to the first two questions with his famous incompleteness theorems. By formalizing the concept of computability and algorithm through the concept of Turing Machine, Alan Turing proved in 1936 the "undecidability" of mathematics to give a negative answer to the third part as well (see Tangent).
Informally, a Turing Machine is a theoretical device
consisting of an infinite line of cells called a tape
and an active element called head.
The head moves along the tape and has an internal state
that changes through the computation. The number of possible states of
the head is finite and there is a subset of states known as final states,
where the computation ends or halts. Each cell on the tape contains a
symbol
from a finite alphabet,
which can be read and changed by the head. There is a special symbol, B,
which is the only one that can appear infinitely many times on the tape
throughout the computation. The Turing machine has a table of
orders that specifies the new state of the head, the
symbol
written on the cell and the direction of the head's movement (left, L,
or right, R)
depending on the current state of the head and the symbol read on the
tape's cell. As the reader might notice the definition of
Turing machine is obscure and is not suitable for implementation of
algorithms. Its use is purely theoretical, rather than computational
per se. Turing machines are abstract devices used to simulate
the logic of any computer algorithm.
To clarify the definition stated above we present an example.
Suppose that a Turing machine has the alphabet {0,1,B} and the states {0,1}. The end state is 1. The table of orders is
| Current state | Scanned symbol | Print symbol | New State | Move |
| 0 | 0 | 1 | 0 | R |
| 0 | 1 | 1 | 0 | R |
| 0 | B | B | 1 | R |
Assume that the initial state is 0 and that initially the head is pointing at asymbol different than B on the tape. The image below shows the partial steps in the computation when the initial configuration of the tape is .....BBB01BBB......
In general, for any initial 0-1 vector this machine changes all the zeros on the tape by ones. This simple operation needs a relatively large description in the language of Turing machines, which highlights the fact that these machines are not suitable for implementation. Clearly, this machine stops running given any initial configuration of the tape. In general, the problem of determining whether, given an initial input, a Turing machine will finish running or run forever is known as the halting problem. Turing proved in 1936 that it is impossible to find an algorithm to solve the halting problem. When translated to the language of number theory this result shows the "undecidability" of number theory and answers the Entscheidungsproblem.