Numb3rs 517: First Law

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.

Alan Mathison Turing was a British mathematician, logician and computer scientist born in London in 1912. A defender of Artificial Intelligence, Turing played an important role in the development of computers in Britain. Together with his friend David Champernowne he invented "round-the-house" chess: after you move, run around the house, if you get back before your opponent's move you are entitled to a new move.

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.

The Turing Test

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.

Activity 1:
    Analyze the conversation above by giving possible explanations to the answers if the respondent were a machine. What questions would you ask if you were playing the role of (C) in the "imitation game"? Why would you ask these questions? How could a machine trick you with its answers?

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.

Activity 2
    Think of further objections you might have to the notion of artificial intelligence and figure out possible counter-arguments to your own objections.

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. 

Turing machines    

In 1936, Alonzo Church solved independently the Decision Problem by formalizing the concept of effective calculability thorough the notion of λ-calculus. It was later proved that Turing and Church's results were equivalent in what it is now known as the Church-Turing Thesis.

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.

Activity 3
    a) Describe a Turing machine that converts all the 0's on a 0-1 vector into 1's and all the 1's into 0.
    b) Describe a Turing machine for which the computation on a particular initial input runs forever.