The Chisel-Construct Cycle · AI Series · 03

Turing Imagined a Machine to Prove Something Could Not Be Done

Han Qin · About 28 minutes · Published

1. The Main Problem

There is a feature of calculation by rule: the person who can do the sums need not understand them.

Give someone an addition problem. They can write it out in columns and get it right without knowing what the numbers stand for. The rules are on the page; the person simply carries them out.

By the end of the nineteenth century, mathematicians were wondering about something larger. Could all mathematical problems be handled this way? Take any formula of first-order logic. Is there a fixed procedure you can follow for a finite number of steps to tell whether it is true under every interpretation?

The idea was not to have a clever person think it through. It was to let someone who did not understand it do the work by following the rules.

The word for such a set of rules was a procedure. Whether there was one was what a 1928 textbook singled out as the main problem of mathematical logic.

There was no such procedure. That was proved in 1936. To make the conclusion stick, the man who proved it first had to say what a procedure could be. To say what it could be, he invented a machine.

That machine came to be taken as a model for the computer.

In 1928 a Berlin publisher printed a textbook, Principles of Mathematical Logic, by David Hilbert and Wilhelm Ackermann. Hilbert was a mathematics professor at Göttingen, one of the most influential mathematicians of the day. Ackermann was his student.

The book posed a problem. Given a logical expression, they wanted a procedure that could tell in a finite number of operations whether the expression held under every interpretation, or whether at least one interpretation made it true.

On the same page they offered a judgment: the decision problem must be called the main problem of mathematical logic.

That is not a recommendation. It is a designation. The word is must.

They did not call the problem interesting or say it deserved study. They called it the main one. When a field puts its center somewhere, that place becomes a measure of the work that follows. Whoever does it has done what the field set out to do. If it is proved that it cannot be done, the field has to change shape. In 1928 the textbook did not provide for the second outcome. A textbook gives students things to learn, not things to doubt. To put a problem in a textbook is to declare it a proper problem. The assumption with proper problems is that there is an answer.

The demand had an earlier form. In Paris in August 1900, the tenth on Hilbert's list of problems called for a procedure to tell, in a finite number of operations, whether any given equation of a certain kind had an integer solution. It was narrower than the one in 1928; it dealt with a particular class of arithmetic equations. But the words were the same: procedure, a finite number of operations, decide. Over twenty-eight years the scope grew without changing the shape of the demand. In the general remarks of the same address, Hilbert said a well-posed mathematical question ought to yield a definite solution or a proof that a solution was impossible. The last clause was a way out at the time. Thirty-six years later it became the way in.

In Zurich in 1917 he named decidability, including decidability in finitely many operations, as something to study. In 1922 Heinrich Behmann put the term decision problem in the title of a paper. He said deciding truth and falsity should be reduced to a mechanical calculation according to given instructions. That already says what is wanted: a set of instructions one can follow without thinking. In the winter term of 1922–1923 Hilbert and Paul Bernays taught a course on the logical foundations of mathematics at Göttingen.

From 1900 to 1928 the demand was set out more and more clearly. One thing about it was never made clear.

What a procedure was.

What sort of action counted as an operation in “a finite number of operations”? How far did “mechanical” extend in a mechanical calculation carried out according to given instructions? Nobody had defined these things, because in 1928 they did not seem to need defining. A mathematician could tell an algorithm when he saw one. If you can recognize it, why define it?

To prove something cannot be done, this step cannot be skipped. First you have to draw a circle around all the possibilities without leaving any out. Otherwise you cannot say the thing does not exist, only that you have not found it. Not finding it is not a proof. Only after you have drawn all the forms it might take can you say it is not among them. That is the shape of Turing's paper: make a cage as large as you can, then show that something lies outside it. The larger the cage, the more certain the thing is outside. Section 9 explains why nothing relevant can slip through. One by one Turing closes the gaps someone might point to, reaching each time for something that belongs to the person doing the sums.

For twenty-eight full years, people had been asking for a procedure without defining what one would look like. The demand stood. The thing demanded had no shape. The construction was reaching outside itself for something it still did not know how to name. What happened next could only happen because somebody went back and made the thing that had no name.

2. Two Meeting Rooms

Königsberg, September 1930. Two things happened that week that are often told as one.

One of them was later said to have changed an entire field. Nobody in the room answered in the moment. It took over a year, until the paper was printed, for the thing to come into view. An event rarely has a shape at the moment it happens. The shape gets printed later.

The first event was the Second Conference on the Epistemology of the Exact Sciences, from September 5 to 7, organized by a society for empirical philosophy. There were several irreconcilable views of what the foundations of mathematics should be. On the fifth, each camp had an hour. John von Neumann spoke for Hilbert's. The sixth brought another set of talks. A twenty-four-year-old from Vienna, Kurt Gödel, had twenty minutes to speak about work he had just finished.

On Sunday the seventh there was a discussion of the foundations of mathematics, chaired by Hans Hahn. Von Neumann and Gödel both spoke. Near the end Gödel announced a result he had not yet formally published.

The second event was Hilbert's address, “Logic and the Knowledge of Nature,” on September 8. It was not part of the first conference. It belonged to the meeting of the Society of German Natural Scientists and Physicians that followed in the same city. A recording of a broadcast version, about four minutes long, survives. At its end are the words: “We must know. We shall know.”

He was addressing mathematics. He would not admit that some things were unknowable in principle. There was another view in circulation: some things will never be understood, and that is the end of it. It was the end of it that he opposed. Six years later something grew out of his own field that proved a particular route was closed. The proof was not shaped like that declaration of unknowability. It did not say people could not understand; it said the thing in question did not exist. The two statements are often mixed together. In this series they occupy quite different places. One concerns the limits of people; the other the shape of the world.

The two events happened a day apart. Later accounts put them in a single scene. The words are barely out when someone in the next room announces the result that cancels them.

The records of that week do not show the two men meeting. Hilbert is not on the list of participants or speakers for the discussion on the seventh. There is not a line to tell us whether Gödel was in the audience the following day. Two rooms, each with its own meeting. There is no record that either heard the other.

The later scene makes a whole event fit a sentence. On the page that week looks like this instead: several dozen people divided between two meetings, each speaking to his own room. Late on Sunday afternoon, when one meeting was about to end, somebody said something and nobody took it up.

Gödel's 1931 paper in a monthly mathematics journal addressed something related but different. In the kind of formal system he studied, if it could express arithmetic and met the relevant consistency conditions, there were statements it could neither prove nor refute. A system is just such a set of rules written down and fixed.

It did not answer the textbook's question. The decision problem called for a procedure that worked on any first-order formula. The paper of 1931 dealt with statements within a certain kind of system. The decision problem stayed open until 1936.

3. Three Papers in 1936

In 1936 three papers arrived, by three people taking different routes. They ran into the same question: how do you make calculation by rule precise? One used a calculus of functions and substitution; one a tape and a table of actions; one a row of boxes and a person following instructions. Similar ideas can start independently. It still takes work to prove whether they amount to the same thing. After the proof, the routes can look as though they had been one road all along.

In March, in the first issue of a new journal of symbolic logic, Alonzo Church of Princeton published a two-page note with Entscheidungsproblem in the title. In April he published a nineteen-page paper in an American mathematics journal, “An Unsolvable Problem of Elementary Number Theory.”

On May 28, the London Mathematical Society received a paper from Alan Turing, a twenty-three-year-old fellow of King's College, Cambridge. The title was “On Computable Numbers, with an Application to the Entscheidungsproblem.” It was read on November 12. It took up thirty-six pages in print.

On October 7 the journal of symbolic logic received the third paper. Its author was the American mathematician Emil Post; its title was “Finite Combinatory Processes—Formulation 1.” Three pages made it the shortest of the three. It appeared in a journal only recently founded, with the author of the March and April papers among its editors. The same name appears three times that year: as an author, as the person to catch up with, and as an editor receiving a paper. The following year it appears again, in a review and as a supervisor. He also gave the machine its name.

Turing says at the outset that Church's recent work had already given the negative result. In an appendix he shows that what he calls computable and what Church calls definable are equivalent.

The appendix shows that the paper changed after submission. Somebody else had reached the result before him. He now had to prove that his route and the other one led to the same place. The proof was not part of the first plan. It was forced on him by the order in which things happened.

In 1937 he had something else to say about it. At the start of a paper comparing the two formulations, he said his own might be more convincing. The two were mathematically equivalent but not equivalent in force. The difference was not the conclusion but the shape of the reason for it.

When Post's three pages appeared, an editorial footnote invited the reader to compare Turing's forthcoming paper and expressly said that though Post's came later by date, it had been written entirely independently.

Here, then, is what happened in 1936. Church and Turing each proved there was no solution to the decision problem. Post independently proposed another model of computation and expected it to be equivalent to what Gödel and Church called recursion. His three pages were not a third proof of the same result.

That the two formal definitions were equivalent was later taken as important evidence. For Turing in 1936 it was first a piece of work: he had to prove that his method and Church's computed the same kind of things before he could say where the roads met.

In 1937 Turing published a three-page correction and credited Bernays with pointing out an error in the original. Within a year someone had found a mistake in what would so often be called a founding paper. The mistake was put right. The machine and the conclusion were still there.

4. The Person Doing the Sums

Section 9 begins with an admission. Turing has not yet shown that his formal use of computable takes in everything that ordinarily goes by that name.

He gives three kinds of reasons: a direct appeal to intuition, a proof of equivalence between definitions, and a large range of examples.

What such reasoning examines is a person doing sums with paper and marks.

In the English of 1936 a computer was a person. It was a trade, a title you could put on a résumé. People sat at desks, went step by step according to fixed rules, and worked out tables. Astronomical tables, navigation tables, actuarial tables were made that way. Such people were everywhere. Most were hired for repetitive work, a row of them in one room, each responsible for a portion. It would be decades before the word passed to the machine. When it did, the people who had held the name got another, or none. When a machine takes the name of a trade, it often means the work is no longer counted as work. In this section, Turing's pronoun for the person who calculates is he.

One of his sentences says that the person's behavior at any moment is determined by the symbols he is observing. In the same account Turing adds the person's state of mind at that instant as another determining factor.

The model has two things in it from the start: visible symbols and an invisible state. What the section keeps doing is trying to make the second thing visible too. If it cannot, it replaces it. That is the device of the third argument in Section 9, and the device of the paper as a whole.

Then he brings things under control one by one. Each move is alike in one respect. It begins with what a person can do, not with what is mathematically convenient.

Paper usually has two dimensions. He rewrites it as a tape divided into squares. Not because people actually use tape, but because two dimensions are not essential to calculation. A way around the two-dimensional arrangement can always be found.

There has to be a finite variety of symbols. The reason he gives comes from experience rather than mathematics. If you take a long string of characters as one compound symbol, the person eventually cannot recognize it at a glance. His example is two very long strings of nines. You cannot tell just by looking whether they are the same.

This is a reason from experience, not a formal one. To fix one of the basic concepts of a field that prizes rigor above all, the evidence he brings in is that a person's eye is not up to the job. At this spot the boundary of the model is measured against a person's powers: not physics, not logic, simply whether somebody can see the difference at a glance. Later it was often treated as a property of the machine itself.

There is an upper bound to how many squares can be observed at once. He marks it by a letter. To see more, the person has to look again, in succession.

The number of states of mind that need to be considered must also be finite. He argues that if there were infinitely many, some would lie arbitrarily close together and be confused. Some of the complexity can be shifted out into additional symbols on the tape.

There is an act in that sentence: shift it out. If there is too much to hold in one's head, put it on paper. Once on the paper, it no longer has to be held in mind. The less is left in the mind, the less has to be assumed; the less assumed, the firmer the argument. The section keeps emptying things out onto the paper until there is nothing left inside.

Where the eye lands next is also limited. There is a fixed distance. A newly observed square cannot be too far from the ones just looked at. Turing considers a counterexample: a distant square with a number on it might seem recognizable at a glance. His answer is that once the number gets long, you still have to check the characters one by one.

Putting those assumptions together, he constructs a machine to reproduce the person's calculation. Each state of mind the person needs to consider corresponds to an internal configuration. The machine scans the relevant number of squares and changes its position of observation within a bounded distance.

What it can reproduce is the stretch of symbolic calculation analyzed here. It reproduces a particular job, the one done by a person following rules to do sums. That job is specific and dull. People had been paid to do it.

That same autumn, someone else described another form of it in three pages. Post's space for symbols is a row of boxes stretching without end in both directions. A box is blank or marked. The one doing the work he calls a problem solver or worker. At a given box the worker obeys a fixed, unalterable set of instructions. The basic acts are to see whether the box is marked, erase a mark, make one, move one box right, or move one box left.

An Atlantic Ocean lay between the papers. Their vocabulary differed. They started with the same object: a person, some paper, a set of rules not open to change.

Each man set out to think what calculation was. The first thing each pictured was a person working. Not a clock, a loom, or a row of circuits. The model was to be about calculation, and at the time nothing in the world looked more like calculation than a person doing sums by rule.

5. The Note on the Paper

Section 9 contains a third treatment. In this argument Turing finds a substitute on paper for the state of mind. In the first argument there had been something that other people could neither see nor check. And the whole point of the paper is to settle something.

He imagines that the computer can stop, leave, forget the whole thing, then return and go on with the aid of a written instruction he left behind. The note, together with the marks already on the tape, makes a more definite physical counterpart to the state of mind.

This is how he deals with it. He does not say the state of mind does not exist, or does not matter, or undertake to find out what it is. He finds something that lets the argument go on without it. Where there had been something nobody else could check, there is now a piece of paper. It can be passed around, copied, checked, and taken up by somebody carrying on the work. Once someone else can carry on with a thing, it no longer needs the person who was there at the start. In 1936 that is a step in an argument. Over the next hundred years it is the situation many people find themselves in. Here it is still a convenience in an argument, a means of doing without an assumption nobody can check.

He even has the person sit down for a single step each time, then write a new instruction for picking up the work. The complete state of the calculation at any given point is now recorded in the note and the marks on the tape.

The person can be replaced. Somebody else sits down, reads the note, takes one step, writes a new note, and goes away. The result is unaffected by who takes the step, because the paper says what to do. The person doing the work has become replaceable. In the first argument he still brought his state of mind. In the third, he and his state have been moved onto the page. Once they are there, it no longer matters who is in the seat.

The device has been used ever since. When you meet something you cannot reach but cannot go around, find a substitute within reach and let the argument continue. The test of the substitute is whether the argument goes through. As for what the thing it stands in for was really like, that question need no longer be answered.

What he did was make a model of a particular kind of work with paper and pencil. What people later said was that the model was a model of the mind. There is a long way between those statements. The thirty-six pages of 1936 do not take a step down it.

Here is something the series will meet again. A substitute put into an argument tends to stay there. The argument goes through and the substitute becomes the thing itself. What it replaced has neither been disproved nor acknowledged. It is simply mentioned less and less.

6. A Machine That Can Stand in for All the Machines

The title of Section 6 is “The Universal Computing Machine.”

At the start Turing writes that it is possible to design a single machine. Give it the standard description of another machine, he says, and it computes the same sequence as that machine. Section 7 gives its full table of actions.

What it does is take in the description of another machine as data. The description and the thing described end up on the same tape. The specification of one machine becomes a set of signs for another to process. In 1936 this was a convenience in a proof. It became a premise of an industry.

The machine stands in a peculiar relation to the others. It is not the strongest of the many machines. It is the one that can stand in for any of them. Everything that can be done within this class, it can do. Here, for the first time, the construction closes within its class. There is nothing inside it that it cannot reach.

Until then the construction kept growing outward. Gain an inch and there was an inch less outside, but there was always more. This machine is different. It takes up its whole class at once. It need not grow out farther. To make it do something else, change the signs that go in, not the machine. The Jacquard loom could already take different cards, and the wooden piano could take different premises. But what each could change lay inside rules of its own. This machine separates the machine from what it is to do. After that separation the word machine changes too: from something built for a task to something waiting to be given one. The person giving it the task is still outside. What task to give it and who decides are not taken over by this machine or discussed in this paper. Every time another piece of work has moved into a machine since, those two things have stayed where they were.

And in the very same paper, Section 8 gives a negative result. There is no general procedure that, given any machine description, always tells whether that machine belongs to a certain class he defines. Section 11 transfers this undecidability to the system of notation used in the 1928 textbook. It reaches this conclusion: what had been designated eight years earlier as the main problem of mathematical logic has no solution.

Both things are in the same paper. The construction closes within its class, and at the same time it is proved to have an outside.

Both things come from the same set of ideas. Because any machine can be written as a string of signs and fed into this one, that string can be used in the proof. Because this machine can imitate any machine in its class, you can ask a question it cannot answer. Closure and having an outside are not two separate results here. They are two sides of one.

What lies outside is not there temporarily. Better technology will not make it disappear; building something bigger and faster will not get you in. It was proved to be outside.

People drew the boundaries in the two earlier essays. Somebody looked at a machine and said this was as far as it went. This time the limit does not come from somebody's judgment. It follows from the machine's own rules. Nobody can move it by changing their mind. Whenever someone says a machine cannot do something, one can ask whether they mean this kind of cannot or another. This is the first time in the series that nobody just points to something and says it is the remainder. The remainder follows from the rules of the construction itself.

Take the later, familiar halting problem as an illustration. Suppose a procedure could make the decision. Use it to build a machine that does the opposite of whatever the procedure predicts it will do. The procedure then has no consistent answer for that machine, although it was meant to answer for every machine. So the assumption fails. An argument of this kind is called a diagonal argument. In Section 8 itself, Turing asks whether a machine keeps producing output of the specified kind, and whether one can tell if it will ever print a specified symbol.

The machine is what gets the paper to this point.

To be precise about the thing that cannot be done, you first have to say what it means to do something at all. In this paper what can be done takes the shape of a machine. What later serves as a model of computation is here one part of a negative result.

The machine is used as evidence. To show that there is no procedure that can do something, first say what a procedure can be. Then you can catch all possible procedures in a net and point to what none of them can do. The machine is the net. What its maker wanted to catch was not a machine but a procedure. Once woven, the net itself was what remained.

7. The Names Came Later

In those thirty-six pages the word intelligence never appears.

Mind does, almost always in the recurring phrase about the person's state of mind in Section 9. That is not the claim that a machine has a mind. It is a variable describing the person doing the calculation, and the note in the third argument soon takes its place. When the paper is quoted later it is often read the other way around: a variable for a person becomes a promise about a machine.

Think appears too, in ordinary phrases such as “I think” or “it may be thought.” The paper does not ask whether machines can think.

For the next eighty years the paper was often treated as the starting point of that question. What it answered was a different question: does the procedure exist? From 1900 to 1936, that was asked for thirty-six years. The answer was no. Giving that answer required first defining the whole business of calculation. Once that was done, the negative answer took only a few pages. The definition remained.

Another name is absent: Turing machine. Turing's terms were computing machine, automatic machine, choice machine, and universal computing machine.

The name came from Church's March 1937 review of the paper. The person who named it was the colleague who reached the same conclusion two months earlier; he did it the year after the paper appeared, in the act of reviewing it. In the same review Church draws a direct comparison. Turing's account of computability, he says, makes its identity with effectiveness in the ordinary sense immediately evident. That was the man who had got the result first, a founding editor of the journal and Turing's supervisor for the next two years.

The other names came later still. The logician Stephen Kleene began calling it Church's thesis in a 1952 book on metamathematics. The name joining Church to Turing comes from another of Kleene's books, in 1967. None of the three men in 1936 used these names. It took thirty-one years for the two names to be joined. By then one of the men was gone. Someone else gives the name, while the person is not there. This is the third time it has happened in the series.

Post wrote a warning about names on the last of his three pages.

He called the identification Church made, between effective calculability and a formal class, a working hypothesis that had to go on being tested. He objected to hiding the identification under the word definition. In his words, that “blinds us to the need of its continual verification.”

It was 1936, and someone was already pointing out, as the work was being done, that to call it a definition was to say it no longer needed checking.

What he wanted to protect was not a point of technical precision. A definition is a convention. A convention need not answer to the world. A hypothesis is a claim, and a claim has to stay open to being overturned. The name under which a proposition travels decides whether anybody still has to look at it. He wanted to prevent a name from closing the matter for everyone.

The names it took on later were indeed definition and thesis, each having its turn. Neither name had appeared when Post wrote those lines.

8. Which One Did Gödel Choose?

Turing arrived at Princeton at the end of September 1936 and spent the next two years there as a graduate student under Church. He took his doctorate in 1938. That April von Neumann asked him to stay as his assistant. He declined and went back to Cambridge.

Gödel was not at Princeton during those two years. No letter, record of a meeting, or joint paper between them survives. The two names often appear side by side in later accounts, because they fit so easily there.

Before Turing, Gödel had not been satisfied with Church's approach. Church wrote in November 1935 that Gödel found the proposal to define effective calculability by definability thoroughly unsatisfactory. At the time Gödel preferred to begin by setting out axioms for effective calculability.

Speaking at a mathematics conference for Princeton's bicentenary in 1946, Gödel said that the great thing about this work was that for the first time it gave an absolute definition, one independent of the choice of notation. He stressed the absoluteness of the concept. Change the formal system and the concept does not change with it. His words were for the first time. In his view, the attempts before 1936, including his own 1934 lectures at Princeton, had not got that far. Each prior definition depended on a system of notation; change the notation and you would have to begin again.

In 1963 he added a note to his 1931 paper. Owing especially to Turing's work, he said, it was now possible to give a precise and unquestionably adequate definition of a formal system in general. He added that in a formal system in the proper sense, the inferences can in principle all be made by a mechanical device.

The note was written in 1963 and attached to a paper from 1931. Thirty-two years later, he supplied something that had been missing at the time: what a formal system is. He supplied it by way of a model made in 1936 for something else.

In 1964 he wrote a postscript to his 1934 lectures, saying that Turing's work gave an analysis of the concept of a mechanical procedure. In the same postscript he left another question open. Might there be finite procedures that are not mechanical?

The person who put his stamp on the idea said in the same document that he had not extended it into an account of all human mental processes. What he accepted was one particular thing: the idea of a mechanical procedure had been made clear. Was there something else beyond mechanical procedures? He wrote down the question and did not answer it.

In conversations late in life he said it more strongly. Before Turing, people had not seen the clear concept of a mechanical procedure for what it was. Turing had brought in the right view. To define it by what a Turing machine can do was, he went on, the right and only way to do it.

Here the remainder is left open by the very person who put his stamp on the model.

He accepted the model in strong terms, calling it unquestionably adequate. Right there he set the larger question down on a line of its own. He did not extend his claim to it.

In a notebook in 1947, the philosopher Ludwig Wittgenstein wrote a sentence about Turing's machines. These machines are the people who calculate.

The next sentence turns to how Turing's idea can be expressed in the form of a game. Then Wittgenstein writes a variant of a diagonal argument of his own and discusses how rules at certain points become meaningless instructions. A sentence often quoted about people and machines was written by somebody working on a diagonal problem.

The readers who can be named in the first three years took this shape. Newman knew about it before submission and had discussed it. Church reviewed it. Bernays read closely enough to find an error. In February 1937 Turing also had an offprint sent to Wittgenstein.

That is the list: a teacher, a competitor, someone who spotted an error, and an offprint sent out.

In the proceedings of the Royal Society in 1948, Newman published “General Principles of the Design of All-Purpose Computing Machines,” discussing Turing's idea of a universal machine. By then, making a general-purpose electronic computer was an engineering problem. The man who wrote that paper was the one who had told Turing about the problem twelve years earlier. At the time he was teaching a problem in logic. Twelve years later he was writing about engineering. The subject had not changed. Its use had. Twelve years before, it was used to prove something could not be done; twelve years later, to explain how a machine should be designed. It was proved that something did not exist, and the tool made to prove it survived and was built in metal. This will happen again in the series. The shape changes. The point does not.

There is no complete list of the people who listened on those days in September 1930. Nobody can now list the people Gödel was speaking to that Sunday afternoon, who heard him and who did not. Yet the later scene stands on the strength of that missing list.

A twenty-three-year-old finished a paper in the spring of 1936 to prove that something could not be done. From a person sitting at a desk doing sums, he stripped away everything but a machine. The machine was later built, called by various names, and used to ask a question he does not ask once in the paper.

He asked it himself fourteen years later. By then he had an actual machine in hand, and the person he had stripped it from, the person at a desk who did sums according to rules, was no longer called a computer.

The machines are still being built. Each generation says again where the boundary lies.