Donald Knuth Turns 80, Seeks Problem-Solvers For TAOCP (stanford.edu) 71
An anonymous reader writes:
When 24-year-old Donald Knuth began writing The Art of Computer Programming, he had no idea that he'd still be working on it 56 years later. This month he also celebrated his 80th birthday in Sweden with the world premier of Knuth's Fantasia Apocalyptica, a multimedia work for pipe organ and video based on the bible's Book of Revelations, which Knuth describes as "50 years in the making."
But Knuth also points to the recent publication of "one of the most important sections of The Art of Computer Programming" in preliminary paperback form: Volume 4, Fascicle 6: Satisfiability. ("Given a Boolean function, can its variables be set to at least one pattern of 0s and 1 that will make the function true?")
Here's an excerpt from its back cover: Revolutionary methods for solving such problems emerged at the beginning of the twenty-first century, and they've led to game-changing applications in industry. These so-called "SAT solvers" can now routinely find solutions to practical problems that involve millions of variables and were thought until very recently to be hopelessly difficult.
"in several noteworthy cases, nobody has yet pointed out any errors..." Knuth writes on his site, adding "I fear that the most probable hypothesis is that nobody has been sufficiently motivated to check these things out carefully as yet." He's uncomfortable printing a hardcover edition that hasn't been fully vetted, and "I would like to enter here a plea for some readers to tell me explicitly, 'Dear Don, I have read exercise N and its answer very carefully, and I believe that it is 100% correct,'" where N is one of the exercises listed on his web site.
Elsewhere he writes that two "pre-fascicles" -- 5a and 5B -- are also available for alpha-testing. "I've put them online primarily so that experts in the field can check the contents before I inflict them on a wider audience. But if you want to help debug them, please go right ahead."
But Knuth also points to the recent publication of "one of the most important sections of The Art of Computer Programming" in preliminary paperback form: Volume 4, Fascicle 6: Satisfiability. ("Given a Boolean function, can its variables be set to at least one pattern of 0s and 1 that will make the function true?")
Here's an excerpt from its back cover: Revolutionary methods for solving such problems emerged at the beginning of the twenty-first century, and they've led to game-changing applications in industry. These so-called "SAT solvers" can now routinely find solutions to practical problems that involve millions of variables and were thought until very recently to be hopelessly difficult.
"in several noteworthy cases, nobody has yet pointed out any errors..." Knuth writes on his site, adding "I fear that the most probable hypothesis is that nobody has been sufficiently motivated to check these things out carefully as yet." He's uncomfortable printing a hardcover edition that hasn't been fully vetted, and "I would like to enter here a plea for some readers to tell me explicitly, 'Dear Don, I have read exercise N and its answer very carefully, and I believe that it is 100% correct,'" where N is one of the exercises listed on his web site.
Elsewhere he writes that two "pre-fascicles" -- 5a and 5B -- are also available for alpha-testing. "I've put them online primarily so that experts in the field can check the contents before I inflict them on a wider audience. But if you want to help debug them, please go right ahead."
Re: (Score:2)
Re: (Score:1)
Re: (Score:1)
Rather than explaining who he is, I'll point you to a comment from a previous story on Donald Knuth.
https://developers.slashdot.org/comments.pl?sid=35651&cid=3849091 [slashdot.org]
Knuth, what? (Score:5, Funny)
Didn't he just get arrested for buying an iPhone X?!
Re: (Score:2)
Re: (Score:2)
Gentlemen, we have a candidate (Score:1)
For the title of "Last Great Work of Computer Science Written By a Single Human Without Intentional AI Assistance".
Re: Gentlemen, we have a candidate (Score:5, Funny)
Have you ever read any of TAOCP? Years ago I kept hearing how great it supposedly is, so I read all of the volumes that were available at that time. I have to say, I was very underwhelmed. It wasn't a bad work, but I don't think it was deserving of the praise that's heaped on it so often. I've since found that Wikipedia articles are often more comprehensive, more comprehensible, have better examples, and are more practical.
This is akin to someone saying "I don't know why everyone says Shakespeare is so great. His writing is just a bunch of famous quotations strung together."
Re: (Score:1)
Perfect response. And you made me laugh, too.
Re: (Score:2)
I feel the same way about "The Art of Electronics" on the hardware side. Useless book, except as a symbol, or if you enjoy reading two old men wool-gathering about obsolete technologies.
Re: Gentlemen, we have a candidate (Score:1)
Re: (Score:3)
Because it's theory, and far too few programmers bother with that. They're more interested in tying frameworks together with programming glue. And yes, it's a difficult book to read; it requires thinking and practice and is the opposite of "Learn a Popular Language in 21 days".
Re: (Score:3, Insightful)
It's not just that it's theory, it's theory presented in a pretty unapproachable way. People read TAOCP for the same reason that they join Mensa: so that they can look down on people that didn't. If you actually want to learn the theory, then you can pick up pretty much any undergraduate computer science textbook and see a far more approachable presentation.
Remember, this is the same Knuth whose TeX system started with a Turing machine and thought 'that's a really approachable programming model. Scopi
Re: (Score:2)
This is true in a way. I think the book was much more approachable back in the late 70s, early 80s, because there was so much more code written in assembler. Thus the MIX language. If it had been written a decade later I suspect there might have been a higher level language used. Although at a higher level, it's easy to fall into a trap of ignoring the low level details - ie, only worrying about how many compare operations there are and not counting the overhead of the loop itself.
Will he cover Rust's algorithmic discoveries? (Score:5, Funny)
Will he be covering the numerous algorithmic and data structure discoveries made by the Rust programming language's creators? For example they have discovered new algorithms for tracking ownership of resources. Knuth's work couldn't be considered anywhere near comprehensive as long as it is missing coverage of what the Rust programming language has given us.
Re: (Score:2)
I'm tempted to mod this +1 funny.
Re: (Score:3)
It's supposed to be a joke, but it's not really funny. Merely referencing things isn't actually funny, no matter how current.
Knuth's work couldn't be considered anywhere near comprehensive as long as it is missing coverage of what the Rust programming language has given us.
I take it you don't like Rust very much. But no, Knuth's work is about algorithms and as far as I can tell doesn't cover any aspect of type theory. And no, his book isn't comprehensive to the world of programming: it's a book on algorithm
Poe's Law (Score:2)
or perhaps Alan Morgan's Law: "Any sufficiently advanced troll is indistinguishable from a genuine kook."
Re: (Score:2)
Do you really not understand that type systems have associated algorithms?
Type inference?
Type checking?
The obligatory XKCD (Score:5, Funny)
One of my favorite XKCD strips is Knuth-related: https://xkcd.com/163/ [xkcd.com]
Re: The obligatory XKCD (Score:3)
The previous one, the classic 162, that has been in footer pantheon of 5 best panels for ages, is the best romantic work ever with a touch of STEM.
Re: (Score:2)
I have loved XKCD 162 ever since he published it. It is a marvelous fusion of romance and physics.
Re: (Score:2)
If he wants someone to look over his work... (Score:2)
... he should just hire some people to do so.
Re: (Score:2)
You're not taking reality into account, most people of intelligence have lives and just asking people to do it for free means there was already intellectual interest it would have been done long ago. The reality is if the problem is hard or non trivial then it's genuinely work.
Happy Birthday! (Score:4, Informative)
'nuff said.
Which Volume 4 first? (Score:2)
Re: (Score:2)
Just how many Knuth stories does Slashdot need?
As many as there are.
Re: (Score:2)
He seems to like complex devices (Score:4, Interesting)
I would love to see a short story written by him about the connections between pipe organs and computers. Until the invention of the steam locomotive, organs were the most complex devices ever made. Many of the terms of CPU/ALU parts came from the pipe organ such as register, buffer and accumulator. There is a reference in one of his books that he was going to use the royalties from TAOCP to buy an organ.
Re: (Score:2)
The Organ of Don and Jill Knuth
https://www.cs.stanford.edu/~k... [stanford.edu]
Wow, without Jill listed there, that would be interpreted very differently!
Re: (Score:2)
But seriously, Knuth also likes to solve puzzles. I met him at a gathering of puzzlers from the SF Bay Area and didn't even recognize him until someone introduced me to "Don" and it finally clicked. There was some serious brain power in that room....
Re: (Score:2)
I believe that Neal Stephenson's novel Cryptonomicon has a computer made in part out of a pipe organ. Or perhaps that's what you were referring to?
Bach it isn't (Score:3)
Heard the preview. [youtube.com] I've heard worse, but that isn't saying much. Competently written, more than competently performed. Inspired? No. Cohesive? No. As tidily organized and precise in detail as any technical text he has published. Worth sitting through? Don't entirely know yet because the composition is not released, but at this point it seems safe to say, that would be more out of respect for the person who wrote it than the enjoyment of a masterpiece. On other fronts, I will be more than happy to attempt to wade through as much of the new AOCP as I can possibly manage, when available. I hope it does become available, at least, more so than the 6th volume of Ice and Fire.
best wishes, Don! (Score:2)