The Secrets of the Turing Machine

The second lecture of “What Is Science” was delivered by Yao Qizhi on the life of Turing. Before the class, as a teaching assistant, my dealings with his female secretary already left me with a very bad impression; I hadn’t expected the lecture itself to be disappointing as well. After the lecture I had already written some thoughts, which I’ll paste below first:

Frankly speaking, today Teacher Yao’s lecture was disappointing. The introduction to Turing was too watery, and it hardly introduced what Turing’s enormous contribution actually was. It only said that he designed the “Turing machine,” that the Turing machine is a universal computer, that is, the modern computer. But what on earth the Turing machine actually is was not introduced either. Even in terms of the introduction to Turing’s life, it was far inferior to the vivid, flesh-and-blood feeling one gets when Mr. Yang Zhenning introduces his own life. I personally express my dissatisfaction.

For this level of popular-science introduction, everyone might as well go look at Baidu Baike. The Turing entry on Baidu Baike is written fairly richly. The entry on Chinese Wikipedia is rather thin; the English entry is of course much richer. But in any case, the lectures in this course should not be limited to the level of Baidu Baike.

No matter how the lecture itself was, the discussion section is the more important part of this course. If the presenting student is willing, he can make up for the lecture’s deficiencies. I also recommend that the other students take a look at the reading materials I selected; that book at least makes clear what on earth the Turing machine actually is. Only by understanding what the Turing machine actually is can we possibly understand where Turing’s genius lies, and also feel the relationship between the development of science and intellectual history, and the developments of mathematics, logic, philosophy, engineering technology, and so on.

The aim of this course is to let the students think about and experience “what science is.” And for this, it is by no means enough to list some scientists’ achievements and contributions, or to talk about a few trivialities from scientists’ lives. I may know that some scientist is extraordinarily outstanding, that he has made extraordinary contributions, but if I know nothing at all about how he actually achieved those accomplishments, or what kind of accomplishments he actually made, then I still know nothing at all about what science is.

I believe the lectures after this will come closer to the spirit of the course: they are not meant to list scientific achievements and scientists’ contributions, nor are they meant to popularize scientific knowledge. Rather, through vivid cases of scientific activity shown from different angles, they are meant to give students a firsthand experience of the development of science and of scientists’ creativity, so that they may carry out their own thinking. Of course, that is also the purpose of the discussion section. In the end, we cannot have everyone say, “Oh, Turing was amazing, his contribution was huge,” and then end it there. We must always remember the course’s main thread: “understanding science.” We should not only know that Turing was amazing, but also grasp why Turing, as a “scientist,” was amazing; we should not only know that Turing made huge contributions, and that all computers today are Turing machines, but also think about where Turing’s contribution, as a scientific activity, actually made a breakthrough, and what significance its influence has in the history of science and the history of culture. We might even as well reflect: was Turing a scientist? (Or would philosopher or logician be more appropriate?) Was the conception of the Turing machine a scientific activity? (Or was it an exercise in logical speculation, or an engineering invention?) Why is it that we revere Turing as a scientist, why is it that we regard the Turing machine as a scientific breakthrough—what exactly in his work contains those things? In any case, through Turing’s case, we must reflect on what “science” actually is. We must find a point of entry from the cases provided by the lecture, and carry out our own activity of “reflection.” Rather than, like listening to a storyteller, just oohing and aahing and then letting it be over and done with.

After the discussion section, let me add a few more things.

Because only one person had arrived at the beginning of one of my discussion sections, we temporarily merged into Teaching Assistant Jing’s class. After listening to one student’s report from their class, we found that several more people gradually arrived, so we went back to our own classroom to discuss. The main presenter in Jing’s class was obviously a student from the School of Information Science and Technology; at the time he was wearing the same Google T-shirt as I was, but his report did not satisfy me. He made up for Yao Qizhi’s complete lack of introduction to Turing’s concrete work, but he introduced it too professionally, so that students who had not prepared in advance probably could not understand it, while students who had already gone to the trouble of reading the materials I selected did not need to listen any further. That student kept talking for twenty minutes and still would not stop. Indeed, this topic is hard to explain clearly in a very short time, but that precisely means that choosing such a topic was inappropriate.

Yao Qizhi’s lecture and that student’s presentation represent two extremes: one is excessively superficial, remaining at the level of an external encyclopedic introduction and not involving scientific content at all; the other is excessively showy in its professionalism, without considering the setting of a discussion.

So, with Turing as the topic, how might one go about giving a report limited to ten minutes? Actually, it is not difficult. The key is to grasp clearly what exactly you want to talk about. Although that student presenter seemed to be striving very hard to show himself, in fact he was not showing himself as a distinctive participant; he was merely showing his own knowledge—nothing but indoctrinated, by-the-book material (see my previous post). He tried to explain how the Turing machine works, how the Turing machine solves the relevant problems of Hilbert and Gödel, but what he explained was not much different from the procedures in textbooks or popular-science materials. What he was trying so hard to “show” was merely his “complete” grasp (see my previous post) of this textbook knowledge. That is why he could not control the time, because he did not try to prune and select, did not strive to make the report bear his own imprint. If the presenter can throw off his attachment to dogmatic knowledge, and pay more attention to his own thoughts and experiences, thereby selecting the focal points he cares about for the report, then the report can be both relaxed and interesting.

If I were to give the talk myself, I would not talk so much about operating mechanisms and program examples, much less about things like incompleteness theorems and the halting problem. I would first sketch, in the simplest way, Turing’s place in intellectual history—after Hilbert and Gödel, using the Turing machine method in the process of solving the decision problem, so that the modern universal electronic computer became a by-product of this mathematical activity. Then I would only need to emphasize the “secret” of the Turing machine, or rather, its “trick.” Of course, the main report would still have to be based on the premise that students had at least browsed the designated reading materials, and only then could it be properly understood.

Where is the trick of the Turing machine? Why is the Turing machine a “universal computer”? Why did the Turing machine give rise to the modern electronic computer? In fact, none of the various encyclopedic or professional introductions spells out these points clearly. In one sentence, I would say: “encoding.” The idea of “encoding” had already been gradually established in the work from Boole to Gödel, and Turing creatively developed this method. The Turing machine’s trick lies in this: with him, not only the data being computed are abstract, formalized, and digitized, but “computation” itself is abstracted, formalized, and digitized. That is to say, “computation” being encoded is the trick. In earlier calculators, the hardware as the computing tool and the input and output data were entirely different existences: the former were concrete things, hardware, while the latter were abstract numbers. But in the Turing machine, the boundary between hardware and data is broken down. Through encoding the computational process, different methods of computation no longer correspond to differences in some concrete mechanical structure, but to differences in program encoding. And the “program” as a computing tool is at the same time abstract code, and these codes can in turn become the data to be computed—when von Neumann added the “memory” mode to the second electronic computer, the power of the Turing machine was truly realized: we perform a computation by inputting a program, and the result output by the computation can at the same time be executed as a new program for a new computation. We can use programs to read programs and write programs; in other words, we can input a “computer” into a “computer” and obtain a new “computer.” This is something unimaginable for earlier calculators in which hardware and data were separate. Thus the Turing machine not only became a “universal” calculator (it does not need to change its mechanical structure, but only to replace one set of data with another, and can then carry out different computational tasks), it also became a calculator capable of continuous extension and expansion, because we can use data to compute data, use a “computer” to write a “computer,” and thus our computers today can have such complex and diverse systems and applications.

Like many revolutionary insights, Turing’s contribution did not require excessively lofty learning or skill. During the break of the last lecture I heard Teacher Rao Yi tell some student that Einstein’s revolutionary theory was also expressed without any particularly profound mathematics, and that even the crucial insight itself was formulated at about the level of “elementary school mathematics.” There are many students in China who are very good at studying; they make the four major forces extraordinarily solid, and their mastery of mathematical technique always astonishes Westerners, but these alone cannot produce truly creative insight. So where does creative insight come from? Although creativity itself cannot be foreseen, the soil that nourishes creativity can still be explored. Taking Turing as a case, we can ask where his creative insight came from—apart from coincidence, were there any other chances worth talking about? Were there any interesting things to excavate in terms of the preparation provided by intellectual history and factors of personal temperament, and so on? Perhaps there is no certain “scientific method,” but there are always some typical scientific styles that can be described.

September 20, 2010