- My first exposure to Knuth's work was in 1980 when I was doing a survey on Factoring Polynomials over Finite Fields. I couldn't find the relevant papers in the library (I can hear people under 25 saying weren't they on line? or what's a library?), so I was told to look in Knuth Volume 2. And indeed, there was a wonderful exposition of what I needed to know, and the history behind it. Quite scholarly and, unfortunately, quite rare among other researchers.
- Browsing through Knuth's volume I got the impression that his attitude is I want to solve problem X and I'll use whatever math I need to solve it, even if I have to develop it myself. Never shy away from a problem because you don't know the math needed, or even because the math you need hasn't been developed yet.
- TeX: Reading the TeX manual you actually learn things of interest outside of TeX. Not only did I learn how to hyphenate in TeX, I also learned that in German when you hyphenate some words, you actually change their spelling. And, of course, TeX can handle this.
- TeX and LaTeX: Revolutionized how we write papers. Facilitated the notion of keeping papers on line for easy access.
- First Contact!: I got a postcard from Knuth pointing out an error in a paper I wrote. WOW! a postcard from Knuth.
- Second Contact!: Knuth asks me to get a review of Volume 4 in my book review column. I was surprised that he emailed me (he does not use email) and amazed that Volume 4 was coming out. The way he asked me was interesting: see this post
- I always thought Volume 4 was a myth, like the missing part of the Dead Sea scrolls. How long has the world been waiting for Volume 4? Knuth needed a term for what we know as `NP-completeness' for use in Volume 4. He held a contest, and NP-completeness won. (He ended up not using it in Volume 4.)
- Volume 4: Yes, it really is out, sort of. It's coming out as a series (or a sequence) of fascicles (small books) of (I am not making this up) exactly 128 pages. It's on generation of combinatorial objects. The second fascicle, on enumerating all strings of length n, (e.g., Gray codes) is fascinating. Includes history and the needed mathematics. History goes back to the mid 1850's. Quite scholarly and, unfortunately, quite rare among other researchers.
- What has Knuth's influence been on computer science? He was one of the first people to realize that an algorithm can be analysed in a mathematical and intelligent way without running it. This is one of the most important starting points for computer science theory. Perhaps even for computer science.
Thursday, January 10, 2008
Today is Knuth's 70th birthday!!
Today, January 10, is Donald Knuth's 70th birthday.
I have some thoughts on Knuth, but I am sure that my
readers have more. So, I'm asking you to leave comments on
Donald Knuth. Let's break the record for number-of-comments
on an entry. Knuth deserves it!
(What is the record? If I were as meticulous as Knuth I would know.)
Subscribe to:
Post Comments (Atom)
Well, Happy Birthday to him, and thanks :)
ReplyDeleteHappy Birthday to Don Knuth, and, wishing him long years that he completes Vol 7 of TAOCP.
ReplyDeleteHappy Birthday!
ReplyDeleteTrivia for people from Romania: Knuth wrote "The dangers of computer science theory" in Cişmigiu Park.
There is also the book Concrete Mathematics with Ron Graham and Oren Patashnik. Of all the books in my office, possibly excepting this one, I regard it as the book where I would find the most germs of new research ideas if I took the time to plumb it more than I have.
ReplyDeletePossible discussion topic: the role of long-term "labors of love" in the (computer) science community, and whether/how one can be both deep and keep a central perspective. Balancing against the drives to specialize and generate "publishable units".
I really like #2; I think that's a strong starting point to doing groundbreaking work.
ReplyDeleteAnd happy birthday!
Knuth is James Joyce of computer science. How many of you own a copy of TAOCP and really went through it? I claim the ratio of "yes" answers is the same as those whose own Ulysses and actually read it!
ReplyDeleteMy favorite piece that has to do with Knuth is Dave Gries's 1996 talk "Eliminating the chaff --again," in which he mocks Knuth's love of 'goto' statements. Too bad this hilarious--and I claim educational, even for you fortnow reader--piece is not available on-line.
HAPPY BIRTHDAY KNUTH!!!!!
ReplyDeleteKnuth, many many happy returns of the day and thanks for your unmatchable contribution to computer science.
ReplyDeletei share number three; while learning LaTeX i also learned that typesetters avoid making lines more than 70 characters wide, and about ligatures, long S, and i guess even the fact that typsetting was both much more artistic, and scientific, than i would have previously guessed.
ReplyDeleteIndeed, I can't find "Eliminating the Chaff" online either. This 1993 piece, "Software Visions" by John Robinson of Syracuse, has some discussion of the issue, but too brief. From what little else I know about Knuth's WeB system, I deduce that he advocates/d "goto" only within a managed framework.
ReplyDeleteI wonder if the (nesting-only-)structured vs. goto debate in the 1970s was influenced by the abstract idea of how well a tree can approximate a directed graph, in cases that matter for meaning and practice.
I'm dealing with a case of this issue myself. In response to the "command compliment" you can find by Google Polgar Regan very difficult endgame, I've been carrying out the widest-ranging ever endgame analysis---and after 9200+ 80-char lines of analysis in one "PGN" game file, and over 20 trillion positions sifted by chess programs, I still can't tell if White was winning at Move 50! (One possible research-worthy benefit) The PGN standard is pure nesting, and the chess database software gives you no more than the tree view. But the underlying moves form a digraph, which a winning strategy can treat as a DAG, and I often find myself repeating analyses of important goal positions that are reached along different transposing paths. A "WeB" framework here would save me a lot of work, not to mention PGN file size!
Is there an online copy of Knuth's essay "The dangers of computer science theory"?
ReplyDelete- Cris
I didn't find one, but I did find Bill G.'s review of the collection it's in, which conveys some of it.
ReplyDeleteHappy birthday to the great don!
ReplyDeleteJust as you were surprised about Don Knuth using email, I was very much surprised when I saw him attend a non-cs talk and ask questions at the end!!
The talk was by the creator of xkcd, and many illustrious people attended it.
I blogged about it in http://toprecorder.blogspot.com/2008/01/don-turns-70-today.html
TAOCP was the first book I checked out in college!
ReplyDelete"Science is what we understand well enough to explain to a computer. Art is everything else we do."
ReplyDeleteI find myself using this quote from Donald E. Knuth in many of my courses and introductory presentations to (prospective) CS students. It stems from the foreword Knuth wrote for the book "A=B" by Marko Petkovsek, Herbert Wilf and Doron Zeilberger, and sums up beautifully how important computer science has become under the influences of giants like Knuth.
A belated happy birthday to him, even though I don't think that this post will break the record for the number of comments. Sorry Bill.
"A=B" is a wonderful book. The Knuth quote has an ancestor from Knuth's 1974 article Computer Programming as an Art: "Science is knowledge which we understand so well that we can teach it to a computer; and if we don't fully understand something, it is an art to deal with it."
ReplyDeleteLike many quotes, and like Knuth himself, it got better! :)
Part of the motivation I give for formal rigor in proofs (in our undergrad theory course) is imagine that you are teaching the proof to a computer.
ReplyDeleteEn-passant, I may as well ask: how many jobs are there in automated verification nowadays?
HOWEVER:
At the IFIP'94 conference in Hamburg, I asked Robin Milner how long it would take to have a computer system capable of understanding the proofs in an intro theory course---enough at least to check them, ideally to solve things like "Prove that very string generated by this context-free grammar has an even number of 0s." His instant reply: "About 50 years", or "Not in 50 years."
Thus at least until 2044, my CSE396 course qualifies as art :-).
May as well tack on a relevant story from ancienter history: The Boyer-Moore people (I believe it was they) came up from Texas to Cornell in summer 1987 (or 1989? pretty sure 1987) while I was teaching Cornell's analogous course in the summer session. At the 4pm dept tea, I asked them if they could do one of my grammar proofs---indeed the one above about even 0s. "Suuure", they said, and right away formed the predicates for numbers being odd or even, and for counting symbols in a string. They got stuck, however, on teaching the system that 1 + an odd number = an even number, and vice-versa. 4:30pm. 5pm. 5:30pm. They did not talk much with Juris or Dexter or John H. or Tim T... At 6pm they had a dinner with several deans. All I know is they were late for that dinner...I don't know if they ever proved it! Of course, that was 20 years ago...
En-passant, I may as well ask: how many jobs are there in automated verification nowadays?
ReplyDeleteGood question! I'd love to have an estimate myself. I suspect that they are not yet a large number, but that they may be more than most people expect. I believe that computer-aided verification groups exist in most big hardware companies, and there are very active ones at Microsoft Research and NASA. See for instance the material here.
The advent of mature model-checking tools has made algorithmic model-based verification much more accessible to the average computer scientist/engineer. So much so that we can now teach first-year students to use model checking tools by sweeping essentially all of the theory behind them under the carpet. See, for example, the very recent experience report:
Roelof Hamberg and Frits Vaandrager.
Using Model Checkers in an
Introductory Course on Operating Systems. Technical Report ICIS-R07031,
ICIS, Radboud University Nijmegen, December 2007.
Last November, I have used the Uppaal model checker in a one-week intensive course on operating systems for engineering students, and the results were very encouraging.
As far as theorem proving is concerned, the technology is also getting better all the time. Great strides have been made since a theorem prover showed Robbins Conjecture, which had stumped people like Alfred Tarski. Check out the work that Georges Gonthier has done by providing the first fully-machine-checked proof of the four colours theorem. Gonthier is now working on formalizing the 250-page proof of the Feit-Thompson "odd order" theorem from group theory. And let's not forget Hales' Flyspeck project.
But overall I agree with you: much remains to be done, and it'll take time.
Thanks for the great stories! I'll readily add them to my story-telling arsenal for courses and introductory talks :-)
I found Don Knuth by another path. By 1979, I had completed three years of classical mathematics, and was switching universities to major in something that could be called math for computer science, more due to family reasons than actual vocation---then limited to a vague feeling since late high school that I was sort of a heterodox logician at heart. That year, browsing through a bookstore that still exists in Madrid (I think I could pinpoint exactly even the shelf) I found a just-published translation of a novel which was actually a research monograph on math and on research itself. It was the Spanish version of this: http://www-cs-faculty.stanford.edu/~knuth/sn.html
ReplyDeleteLater on I had the English version, had the Conway book, lent each, lost track of them, bought volumes 1 to 3 fo TAOCP, read fragments of them, lent them, recovered them (I just checked and, amazingly, they are indeed there on the shelf) and so on. But the first time I heard of Don Knuth was, well, maybe unusual for a computer scientist. Also unusual could be a rare preference that I have: if I am not writing with coauthors or under some other constraints, I tend to prefer slightly TeX over LaTeX...
Happy birthday, creator of so many marvelous things and notions: let me mention my own favorite, even beyond the amazing Knuth-Bendix completion; something that is being used (also!) many times per second permanently around the planet, nearly every time anyone is compiling a program: LR parsing, from "On the Translation of Languages from Left to Rigth", Information and Control 8(6):607--639 (1965).
>>>> JLBalcázar.
With regard to "How many jobs are there in automated verification?" the answer is "plenty."
ReplyDeleteSee my esteemed colleague Jon Jacky's new book Model-based Software Testing and Analysis with C#.
Jon is in Beijing this week, lecturing on this subject. So there are at least a few hundred million people interested. :)
What's that you say? The book is not about automated verification in its strictly rigorous sense?
Like the Rabbi says in a famous Yiddish joke "You know, you're absolutely right!"
Knuth is truly a giant in the field.
ReplyDeleteI think that his great contribution was not "to realize that an algorithm can be analysed in a mathematical and intelligent way without running it"--this was done already by von Neuman, in the very first CS papers.
Knuth's immense contribution was to make algorithms the centerpiece of CS--and of superb scholarly study--but, within this erudite framework, value, practice and thoroughly enjoy the practice of programming, as done by the best of "hackers". He brings together the two cultures of CS.
Another (sad) trivia is that Knuth was recently diagnosed with cancer. (He says so in one of the videos at http://www.peoplesarchive.com/, which seems to be down at the moment.)
ReplyDeleteBelated Happy Birthday wishes Knuth...
ReplyDelete