Ken Liu: Broken Stars

The most important paper published by Alan Turing wasn’t “Computing Machinery and Intelligence,” but “On Computable Numbers, With an Application to Entscheidungsproblem,” published in 1936. In this paper, Turing creatively attacked Hilbert’s “decision problem” with an imaginary “Turing machine.”

At the 1928 International Congress of Mathematicians, David Hilbert asked three questions. First, was mathematics “complete” (meaning that every mathematical statement could be proved to be true or false)? Second, was mathematics “consistent” (meaning that no false statement could be derived from a proof each step of which was logically valid)? Third, was mathematics “decidable” (meaning that there existed a finite, mechanical procedure by which it was possible to prove or disprove any statement)?

Hilbert himself did not resolve these questions, but he hoped that the answers for all three questions would be “yes.” Together, the three answers would form a perfect foundation for mathematics. Within a few years, however, the young mathematician Gödel proved that a (non-trivial) formal system could not be both complete and consistent.

In the early summer of 1935, Turing, as he lay in the meadow at Grantchester after a long run, suddenly came up with the idea of using a universal machine that could simulate all possible computing procedures to decide if any mathematical statement could be proved. In the end, Turing successfully showed that there existed no general algorithm to decide whether this machine, given an arbitrary program to simulate and an input, would halt after a finite number of steps. In other words, the answer to Hilbert’s third question was “no.”

Hilbert’s hope was dashed, but it was hard to say whether that was a good or bad thing. In 1928, the mathematician G. H. Hardy had said, “If… we should have a mechanical set of rules for the solution of all mathematical problems,… our activities as mathematicians would come to an end.”

Years later, Turing mentioned the solution to the decision problem to Christopher. But this time, instead of offering a mathematical proof, he explained it with a parable.

Alan: Dear Christopher, I thought of an interesting story for today.

Christopher: An interesting story?

Alan: The story is called “Alec and the Machine Judge.” Do you remember Alec?

Christopher: Yes. You’ve told me. Alec is a smart but lonely young man.

Alan: Did I say “lonely”? All right, yes, that Alec. He built a very smart machine that could talk and named it Chris.

Christopher: A machine that could talk?

Alan: Not a machine, exactly. The machine was just the supporting equipment to help Chris vocalise. What allowed Chris to talk were instructions. These instructions were written on a very long paper tape, which was then executed by the machine. In some sense, you could say Chris was this tape. Do you understand?

Christopher: Yes, Alan.

Alan: Alec made Chris, taught him how to talk, and coached him until he was as voluble as a real person. Other than Chris, Alec also wrote some other sets of instructions for teaching machines to talk. He put the different instruction sets on different tapes, and named each tape: Robin, John, Ethel, Franz, and so on. These tapes became Alec’s friends. If he wanted to talk with one of them, he’d just put that tape into the machine. He was no longer lonely. Marvelous, right?

Christopher: Very good, Alan.

Alan: And so Alec spent his days writing instructions on tapes. The tapes ran so long that they piled all the way to the front door of his home. One day, a thief broke into Alec’s home, but couldn’t find anything valuable. He took all the paper tapes instead. Alec lost all his friends and became lonely again.

Christopher: Oh I’m sorry, Alan. That makes me sad.

Alan: Alec reported the theft to the police. But instead of catching the thief, the police came to Alec’s house and arrested him. Do you know why?

Christopher: Why?

Alan: The police said that it was due to the actions of Alec that the world was full of talking machines. These machines looked identical to humans, and no one could tell them apart. The only way was breaking open their heads to see if there was any tape inside. But we couldn’t just break open a human head whenever we pleased. That’s a difficult situation.

Christopher: Very difficult.

Alan: The police asked Alec whether there was any way to tell humans apart from machines without breaking open heads. Alec said that there was a way. Every talking machine was imperfect. All you had to do was to send someone to talk with the machine. If the conversation went on for long enough and the questions were sufficiently complex, the machine would eventually slip up. In other words, an experienced judge, trained with the necessary interrogation techniques, could work out which interviewees were machines. Do you understand?

Christopher: Yes, Alan.

Alan: But there was a problem. The police didn’t have the resources or the time to interview everyone. They asked Alec whether it was possible to design a clever machine judge that could automatically screen out the machines from the humans by asking questions, and to do so infallibly. That would save a lot of trouble for the police. But Alec responded right away that such a machine judge was impossible. Do you know why?

Christopher: Why?

Alan: Alec explained it this way. Suppose a machine judge already existed that could screen out talking machines from humans within a set number of questions. To make it simple, let’s say that the number of questions required was a hundred—actually, it wouldn’t matter if the number were ten thousand. For a machine, one hundred or ten thousand questions made no difference. Let’s also suppose that the machine judge’s first question was randomly chosen out of a bank of such questions, and the next question would be chosen based on the response to the first question, and so on. This way, every interviewee had to face a different set of one hundred questions, which also eliminated the possibility of cheating. Does that sound fair to you, Christopher?

Christopher: Yes, Alan.

Alan: Now suppose a machine judge A fell in love with a human C—don’t laugh. Perhaps this sounds ridiculous, but who can say that machines cannot fall in love with people? Suppose that that machine judge wanted to live with his lover and had to pretend to be a human. How do you think he would make it work?

Christopher: How?

Alan: Simple. Suppose I were the machine judge A, I would know exactly how to interrogate a machine. As a machine myself, I would thus know how to interrogate myself. Since I would know, ahead of time, what questions I would ask and what kind of answers would give me away, then I would just need to prepare a hundred lies. That’s a fair bit of work, but easily achievable by the machine judge A. Doesn’t that sound like a good plan?

Christopher: Very good, Alan.

Alan: But think again. What if this machine judge A were caught and interrogated by a different machine judge B? Do you think machine judge B would be able to determine whether machine judge A was a machine?