Happy 0x50th Birthday, Donald Knuth

Gödel’s Lost Letter and P=NP 2018-03-14

A revel and revelation in Sweden

Cropped from “Knuth at Brown” video source

Donald Knuth’s 80th=0x50th birthday was on January 10. In the array ${B}$ of his birthdays, numbering from zero so that ${B[0]}$ stands for his birth day in 1938, that was indeed ${B[80]}$ . However, as the 81st entry in the array it might have to be called his 81st birthday. Oh well.

Today we salute his 80th year—wait, it really is his 81st year—and wish him many more.

Our little riff on “off-by-one” issues is not an idle matter. Don’s epochal multi-volume monograph The Art of Computer Programming (TAOCP) set standards for presenting as well as designing algorithms and programs. He nodded to community agreement on the benefit of “numbering from zero” but began his chapter on lists and arrays by numbering from 1 before using either convention. The xkcd cartoon “163: Donald Knuth” projects onto him the opinion,

“Different tasks call for different conventions.”

In his textbook Concrete Mathematics with Ron Graham and Oren Patashnik, in a passage indexed as “Zero not considered harmful,” they say:

People are often tempted to write ${\sum_{k=2}^{n-1} k(k-1)(n-k)}$ instead of ${\sum_{k=0}^{n} k(k-1)(n-k)}$ because the terms for ${k = 0}$ , ${1}$ , and ${n}$ in this sum are zero. … But such temptations should be resisted; efficiency of computation is not the same as efficiency of understanding! …[S]ums can be manipulated much more easily when the bounds are simple. … Zero-valued terms cause no harm, and they often save a lot of trouble.

Emphasizing zero values rather than the index ${0}$ , they continued with what they termed “a radical departure from tradition”:

Kenneth Iverson introduced a wonderful idea in his programming language APL … to enclose a true-or-false statement in brackets, and to say that the result is ${1}$ if the statement is true, ${0}$ if the statement is false … This makes it easy to manipulate the index of summation, because we don’t have to fuss with boundary conditions.”

This was almost 25 years ago but Don’s advice is still a step ahead today.

The Fest in Sweden

I (Ken) used to think that only chess held marquee events up near the Arctic Circle: the 1972 match between Bobby Fischer and Boris Spassy in Reykjavík, Iceland; the 2014 Chess Olympiad in Tromsø, Norway. The January 8–10 workshop and celebration for Don’s 80th birthday was organized in Piteå, Sweden, which is just north of 65° latitude.

“Organized” is the operative word. As Don says in the opening seconds of a video with the science editor of Sweden’s premier newspaper Dagens Nyheter:

It took such a perfect match. I don’t believe that any other … anywhere else in the world would come anywhere near being right…

We have elided one of Don’s words, and we’ll keep you in suspense about it, but for a hint it’s the ${\overset{9}{\underset{5}{\scriptstyle 7}}}$ kind of suspension. Which is one of the more difficult things I’ve ever had to do in plain TeX, because WordPress does not recognize fancy add-ons to LaTeX (nor even the \TeX or \LaTeX macros).

TeX, of course, was Don’s free gift to the world. It sprang not only from his desire to make mathematical typesetting freely available—and to demonstrate how to code large-scale useful software—but also from the value of pliable visual beauty. It was duly featured at the workshop in a talk by by Yannis Haralambous titled “TeX as a Path.” Here are the other talks in the order they were given—most have slides on the talks page:

Robert Sedgewick: “Cardinality Estimation”
Michael Drmota: “Subgraph counting in series-parallel graphs and infinite dimensional systems of functional equations”
Tim Roughgarden: “Don, Stable Matchings, and Matroids”
Svante Janson: “Random permutations avoiding some patterns”

Sunset was observed during the lunch break—this was the Arctic Circle in early January, after all.

Wojtek Szpankowski: “Analytic Information Theory: From Shannon to Knuth and Back”
Richard Stanley: “Combinatorics and Smith normal form”
Ronald Graham: “Eulerian Adventures with Don”
Richard Karp: “The Rectilinear Group Steiner Problem”
Sunrise
Susan Holmes: “Don Knuth and the Reproducible Research movement”
Jeffrey Shallit: “Using Automata to Prove Theorems in Additive Number Theory”
Anders Björner: “To where Knuth paths can lead”
Sunset
Persi Diaconis: “Don Knuth and Backtracking”
Svante Linusson: “Using a modified Robinson-Schenstedt-Knuth correspondence on randomized sorting networks”
Michael Paterson: “An old buffers problem: taking a closer look”
László Lovász: “Graphings, hyperfiniteness and combinatorial optimization”
Robert Tarjan: “Zip Trees”
Gregory Tucker: “Tales of Computational Geomorphology”
Sunrise
Martin Ruckert: “Programming as an Art”
Erik Demaine: “Fun and Games meet Computer Science”

There followed the talk on TeX by Haralambous, a tribute by Don’s son John Knuth, and a brief introduction by Jan Overduin to the signature event of the day, which took place after the cutting and serving of the birthday cake.

The Revelation

The word apocalypse comes from Greek apo- “away” and kalupsis “covering”—that is, a revelation. As the original Greek name for the Book of Revelation it acquired its connotations of catastrophe and final destruction. What we now consider to be apocalyptic writing goes back at least to the fall and Babylonian exile of Israel and Judah. But the primary element of revealing hope sets Revelation apart—except that its germ is in the last chapter of the book of Daniel.

As Björner highlighted in his talk, in a January 1981 interview that was published a year later in the The Two-Year College Mathematics Journal, a caption opened by noting him as “an accomplished organist and composer” and went on to quote him:

“I want to write some music for organ with computer help. If I live long enough, I would like to write a rather long work that would be based on the book of Revelation. The musical themes would correspond to the symbolism in the book of Revelation.”

He got it going in early 2011. So January 10 saw the world premiere of his Fantasia Apocalyptica on the Orgel Acusticum, whose official page begins by saying, “This is an instrument for the 21st century.” It was built in 2012 by Gerald Woehl. A year ago, Don visited it in Piteå and wrote an incredibly detailed exegesis, including the organ’s software features and controls.

You can hear parts of it in an introductory video by the Canadian organist Jan Overduin, who performed it in Piteå and will do so again on November 4 at his home First United Church in Waterloo. This video is atop Don’s own page which includes his full score in manuscript and typeset forms.

Both Overduin and Don describe how the music closely follows both the message and the numerical contents of the Book of Revelation. Don described the process as “Constraint-based Composition” in a lecture of that title in May 2015 at Stanford. He draws analogy to constrained writing as practiced by the Oulipo group of mainly-French writers. A very loose example is how every post on this blog is constrained to follow some “GLL invariants.”

However, what I (Ken) think of as the highest example of constrained writing is translation. Insofar as they give scope for the translator’s own creativity, they are constrained by faithfulness to the source text. Creative choices come because meaning and imagery and emotion require different mixings in different languages and media. The Fantasia Apocalyptica is organized into one movement for each chapter of Revelation, and each movement follows the verses as Overduin expounds. It is thus a musical translation at perhaps a finer grain than many tone poems that have been based on literary works.

With “fine-grained” as well as “constraints” we have circled around to computer-science concepts again. If there is one over-arching point we see Don conveying, it is that such integration of informatics with arts and language and real-life appreciation should be natural.

Open Problems

We wish Don many more birthdays to come, no matter how they are numbered.