Slashdot Mirror
Donald Knuth Turns 80, Seeks Problem-Solvers For TAOCP (stanford.edu)
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."
Why are all stories showing zero comments? Perhaps someone could learn the art of programming slashcode?
Didn't he just get arrested for buying an iPhone X?!
For the title of "Last Great Work of Computer Science Written By a Single Human Without Intentional AI Assistance".
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.
One of my favorite XKCD strips is Knuth-related: https://xkcd.com/163/
Violence is the last refuge of the incompetent. Polar Scope Align for iOS
Why do people persist in calling it the "Book of Revelations" or "Revelations"?
There is one revelation. The name of the book is "The Revelation of John", or just "Revelation".
For solving some hard problems (e.g. combinatorial problems), i recommend
1. ECLiPSe.
2. Prolog with CLP(FD) support.
3. Java with frameworks Choco and JaCoP (Scala too).
Can Knuth to test these above solvers?
... he should just hire some people to do so.
'nuff said.
I used to make jokes about which Volume 4 would publish first: Knuth's, or Star Wars (i.e., episode 1). Of course, even with all of the LucasFilm soap opera, it looks like episode 9 will beat it.
Comment removed based on user account deletion
Some rando? omfg.
I'd suggest googling it.
... that when an error was found in an earlier volume of Knuth's Art of Computer Programming that God relented and chose to change the underlying laws of the reality instead?
Yep. This Donald Cuck guy is some rando that nearly 99% or more of the world has never heard of.
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.
That's because Knuth is known for his encyclopedic, foundational works in computer science and rather less for HIV transmission.
Years ago I did a survey of solvers. Only one instance of one ever passed all of my test. The rest happily spit out invalid solutions. The most sophisticated open source solver cryptosatsolver was by far the absolute worst providing wrong answers right and left. Not too long after my testing discovered blog posts by the programmers basically outlining one of the problems with an embarrassingly simple circular dependency graph turned into a sat problem spitting out the wrong answer. Don't trust SAT solvers with anything important.
I'd suggest re-reading the thread. Or perhaps reading it for the first time.
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.
Sick burn.
You wouldn't be able to show what a cut you are on the internet if it wasn't for his work.
Heard the preview. 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.
When all you have is a hammer, every problem starts to look like a thumb.
Just how many Knuth stories does Slashdot need?
As many as there are.
When all you have is a hammer, every problem starts to look like a thumb.
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
A lot of people would pay for this kind of privilege. Why should someone who would only do it for money get the privilege?
I used Don's insertion sort from TAOCP, Sorting and Searching, to fix a knotty programming problem I had years ago. I've always been a fan of TAOCP, what a treasure trove of info!
Circle the wagons and fire inward. Entropy increases without bounds.
or perhaps Alan Morgan's Law: "Any sufficiently advanced troll is indistinguishable from a genuine kook."