Yesterday, Stanford Prof. emeritus Don Knuth gave one of the "lectures" in the series devoted by Stanford to their "Engineering Heroes." Jim Plummer, Dean of the School of Engineering, rattled off the names of the eight initial Engineering Heroes so quickly that I had to find them later here. They are William Durand, a pioneer in aerodynamics; Fred Terman, who is credited with fostering the emergence of Silicon Valley; Bill Hewlett and Dave Packard; Charles Litton, one of their associates and vacuum tube developer; Ray Dolby, whom we all associate with noise reduction in sound reproduction; Vint Cerf, one of the "fathers of the Internet"; and Don Knuth.
Like Cerf, Knuth was one of my professors at Stanford, and I am deeply indebted to his teaching. He is as close to a Renaissance man as you can get these days: a mathematician and computer scientist who pioneered the analysis of algorithm performance, but also invented many key algorithms for data manipulation; an accomplished player of multiple musical instruments, especially the organ; the developer of the TEX typesetting language (a derivative, LATEX, is still used today to typeset mathematical texts, including on Wikipedia and Blogger); the author of the famous series of textbooks called "The Art of Computer Programming," which he has promised finishing soon... since Vol. 3 appeared in 1973; and someone who, in the middle of all that, took time off his scientific pursuits to study religious texts.
Knuth used to devote the last lecture of his courses at Stanford to fielding questions from his students. True to form, he decided that his "Engineering Hero lecture" would not be a talk, but a Q&A session. He fielded questions from the packed auditorium on campus, as well as from the Internet audience who were following the event in real time. Dan Boneh, a cryptography expert who teaches at Stanford, was the moderator.
Below are my notes, providing a potentially biased summary of the session. I took the time to research links so that the reader can understand what mathematical or computational problems are mentioned in Knuth's answers. It should be noted that Knuth is often facetious, and will not bother giving a serious or complete answer to a question if he can get away by making a quip about it. He also tends to get off on a tangent frequently, and doesn't always return to the point. You can almost imagine the thoughts colliding in his head faster than he can express them -- nothing much has changed in this respect since I sat in his CS155 course, "Analysis of Algorithms," in 1973.
Q: If you wanted to give an interesting open problem of mathematics or computer science to a smart new student, what would it be?
A: One of the biggest open problems, of course, is P vs. NP. But really, this question is like asking a parent which of their children they love most. (Knuth searched for a specific problem in his own book, fumbled a bit, and gave up).
Q: In the 1790s, the French tried to introduce a decimal time system. How would a computer scientist design a time system?
A: Well, a decimal system could be very convenient, for example you could have birthdays more often.
Q: A lof of computer science students today don't know who you are. Do you think that's really bad?
A: I find it tragic when people don't know who Martin Gardner, who died about a year ago, was. He did a lot to illustrate mathematics in a really interesting way. For me, the important thing is not that they remember me, but that they remember the things I put in my books, and don't reinvent the same things over again.
Q: You developed TEX when computers were slow and user interfaces were not WYSIWYG. How would you do things differently today?
A: Actually, I wanted to design something that could capture texts in an archival format, something that would endure through technology changes. So I was never interested in changing it to track the evolution of technologies.
Q: I learned Pascal, then C, C++, and Java. After 25 years, I still think it is hard to write software, debug it, etc. Why, and do you think we'll finally some day overcome this?
A: I put a lot of ideas about this in my book "Literate Programming." I think the key is to write programs so that they can be easily understood by humans. But there is no silver bullet. Some techniques will make things better, but programming will still be hard.
Q: What is your opinion of quantum computing? If it ends up working, will it change the notion we have of algorithms?
A: Quite possibly. Quantum computers make some things we consider very hard today much easier. So if this works, I might be able to finish my books much faster.
Q: Your Web site has Frequently Asked Questions, but also Infrequently Asked Questions. Do you know why those questions are infrequently asked?
A: I am not an activist, but I think people should be talking more about some important issues like those. And my points must not have been made strongly enough, because I didn't get any hate mail.
[Note: I think that it may simply be that this page is hidden away and has not been mentioned enough. I just discovered it myself as a result of this question.]
Q: Can you talk about some mistakes you've made?
A: I once wrote a paper about the mistakes I made in TEX, and there were over 1000. One of them is that I based TEX on binary units internally, but decimal units externally (in what the user can see). The rounding error that results when someone specifies, for example, a space of 0.1 points, can cause some anomalies to happen.
Q: If you were starting as a Ph.D. student today, what area would you go into?
A: I'd probably be most attracted by computer graphics, because I like to use my left and my right brains at the same time.
Q: Do you think we will ever create real artificial intelligence?
A: I am not sure, and if it happens, we may not know it. But regardless of the result, aiming for that goal has been one of the most fruitful generators of ideas and of useful computer science problems.
Q: What are the biggest bottlenecks against improving the quality of life?
A: The eighth and latest volume of my collected papers ("Selected Papers on Fun and Games") is the "dessert issue" -- things I couldn't think of leaving out. I mention this because quality of life is about building a bridge to the other side of the river so we can cross it and go have fun on the other side. But I really don't enjoy the kind of ranking we tend to do, like "what is the most this, what's the best that?"
Q: What is your general approach about solving a tough problem?
A: One of the biggest problems I solved, with several other people, was the "giant component problem" in graph theory. When you randomly connect vertices in a set, the largest connected subgraphs stay small for a while, and then there's this sort of big bang explosion of the size of the largest component. We had to invent a way to look at the time steps in this process differently so we could see what was happening in slow motion, so to speak.
I tend to train my brain to understand the domain of the problem by taking baby steps during the first weeks.
Q: What do you think about open-access (freely downloadable) texts and journals vs. traditional commercial publications?
A: I like to do control quality myself on my work, but I'm also now thinking of doing e-books. I'm in favor of open-access journals because I don't like it when commercial publishers make money from the free work of the authors and reviewers.
Q: Do you prefer analyzing a problem or solving it?
A: If I can solve it, I certainly feel an adrenaline rush when I succeed. But I can sometimes find the journey more interesting than the destination.
Q: A long time ago, you had said that computer science did not have enough hard scientific results to really qualify as a science. Are we there yet?
A: Yes, we must have passed that point 25 years ago. What happened is someone told me that a science needed to have 500 theorems or more to really be a science. I replied "or 500 interesting algorithms." We've had that many for a while now.
Q: When you write your programs, what language do you use?"
I use CWEB. I write about 5 programs a week, mostly pretty small ones, and that's what I use.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment