Brown CS News

Computational Ideas, World Culture, And Maximum Insights Per Hour: Donald Knuth Delivers The 2016 Paris C. Kanellakis Memorial Lecture


    Among many other things, the visit was timely: a post about Donald Knuth’s multi-volume opus, The Art of Computer Programming, was trending on Slashdot just last week.

    Earlier this month, on Thursday, December 1, 2016, and Friday, December 2, Brown University’s Department of Computer Science (Brown CS) hosted Knuth, Professor Emeritus at Stanford University. Widely regarded as an artistic genius and perhaps the most gifted programmer of all time, he delivered the 16th Paris C. Kanellakis Memorial Lecture and a John von Neumann Lecture.

    “This is the most mind-boggling thing,” Knuth said at the start of the first lecture, proceeding immediately to boggle the minds of a record-size audience with insights that varied from the specific to the far-reaching and from the offhand to the profound. Below, we sketch just the outline of his visit in text, photographs, and video.

    Organ Music

    The mornings of both days were occupied by visits to two prominent local pipe organs, one at Brown’s Sayles Hall and the other at the Cathedral of Saints Peter and Paul. Knuth played a selection of Bach, seasonal favorites, and part of his own Fantasia Apocalyptica, which he described with enthusiasm and a vocabulary more reminiscent of an undergraduate than an octogenarian: “So far, I’m psyched about it!”

    Explaining the mechanics of a pipe organ to his listeners, he made the computer science analogy of columns and rows, saying that there are n notes and m tonalities to choose from, and thus the total number of sounds that the organist can possibly make is at most 2 to the power m-plus-n. However, the number of pipes is m times n; therefore, if a computer were able to turn each individual pipe on or off independently, the organ would be able to produce many, many more sounds: 2 to the power m-times-n!

    For example, at Sayles Hall both m and n are less than 70, so fewer than 2 to the power of 140 sounds are possible. But that organ has 3355 pipes, so it’s capable of 2 to the power of 3355 different sounds. Thus, Knuth mused, for every sound the organist can play, the instrument is actually able to make more than 64,000,000,...,000 (imagine 957 other zeroes in the expression) others. “Most of the sounds this instrument can make haven’t been heard yet,” he said. “We don’t know if the unheard ones are beautiful or not. Are we missing something important?”

    Hamiltonian Paths And Satisfiability

    Both lectures were spectacularly well-attended, setting Brown CS records. Introduced at one point by Professor Sorin Istrail as one of “two real-life superheroes, von Neumann and Donald Knuth”, and wearing the same brightly-colored shirt from when he spoke at the opening of the CIT in 1988, Knuth seemed to relish speaking to what he described as a “pretty geeky” audience.

    The first lecture, which Knuth framed as a “history of clever ideas that arose around the world”, traced the evolution of a problem that dates back to antiquity: finding a path that encounters all points of a network without retracing its steps. Knuth’s sense of aesthetics, curiosity, and his love of minutiae and the absurd were on full display (“look at the ingenious wordplay….nonsense things like this are easy to learn”) as he took his audience from Hellenic icosahedrons to a knight’s tour of the chessboard to the sandals of Lord Rama, mentioning with offhanded modesty feats such as teaching himself enough Sanskrit to find errors in Wikipedia entries devoted to obscure treatises half a millennium old.

    In the second lecture, Knuth returned the audience to his multi-decade project, The Art of Computer Programming. (“It makes a wonderful Christmas present,” he said to considerable laughter.) His subject was the concept of satisfiability, in which a formula is declared satisfiable if one can find and prove a model that makes the formula true. Again, the approach was in part historical, tracking inflection points such as the “unseen breakthrough” of lazy data structures in 1982, but Knuth also made an argument for the importance of what he described as a “million-dollar” problem. (The number refers to the value of the award given by the Clay Mathematical Institute for solutions to their Millennium Prize Problems, some of the most famous unsolved questions in mathematics.) “I didn’t anticipate,” he said, “that I was going to have 300 pages on it, but eventually I realized that satisfiability is a basic technique that deserves to be much better known, part of every programmer’s toolkit.”

    The occasional digressions were equally interesting. Knuth explained that creating a graph of character interactions in Anna Karenina increased his appreciation of Tolstoy, and that he obtained “maximum insights per hour” through a technique of taking a random walk through the Bible as well as through student papers that he needed to grade. “Some people thought I graded at random,” he joked. “That wasn’t exactly true.”

    Knuth And Wegner

    At the end of the first lecture, Sorin offered a champagne toast to celebrate a remarkable collaboration between Knuth and Brown CS Professor Emeritus Peter Wegner. Almost fifty years ago, Knuth explained, a “hot topic in those days” was the hope to “define the precise meaning of programs in a formal way, noting that all of the existing proposals for programming language definition at the time were too uncomplicated and unintuitive to be fruitful”.

    During a visit to Wegner’s home in 1967, Peter suggested that information could be conveyed down a parse tree as well as upward from the bottom. This seemed preposterous at the time, Knuth explained, sharing the memory of how he was so agitated by the idea that he suddenly realized he was yelling instead of speaking in a normal tone. But the suggestion lingered in his mind because he understood that Peter was absolutely right. This suggestion soon led to the invention of attributed grammars. “Much of the technology of modern compilers,” write Shasha and Lazere in Out of Their Minds: the Lives and Discoveries of 15 Great Computer Scientists, “dates from these insights.”

    Questions Answered

    After each lecture, when students asked a variety of difficult, far-reaching, and even unanswerable questions, Knuth shone. The witticisms were present again as he answered a query as to whether a supreme deity plays dice with the universe (“God could perfectly well play dice, if that leads to a good algorithm”), but weight and seriousness returned as he urged attendees to lengthen their attention spans. “Computer science shouldn’t automatically lead directly to Wall Street,” he said; computer scientists should “advance civilization” instead.

    Not even the most broad and fundamental challenges were out of bounds. When asked about what’s widely considered the most important question in computer science theory, Knuth took the unpopular position that P=NP, giving just enough detail in his response to preserve and even augment, rather than destroy, the mystery of one of the most famous problems of our discipline.

    Some of Knuth’s most powerful moments were when his remarks took on the fullest possible global and cultural scope: “The notions that we now think of as computational ideas are part of world culture going way back.” Each time, whether the topic was look-ahead solvers, random sampling of the Bible, or the “thrill” of feeling like he was talking to a fellow scholar from the 13th century, segments of the talks devoted to theory and comprehensive detail were illuminated by the personal example of Knuth’s intellectual restlessness and eagerness, his unabashed love of experimentation. Even as he lamented that he was unable to persuade any of his PhD students to interest themselves in the history of computer science, he urged his audience to do so, and thereby pursue the life of ideas: “We need to see what other people have thought and how they approached problems, a combination of breadth and depth….good computer science, like good mathematics, has a long half-life.”


    For a full gallery of photos from Professor Knuth’s visit, click here.


    Click any link below to watch a video from the two-day event: