Donald E. Knuth Q&A Session 2 Transcript

See also the event landing page and the Q&A Session 1 Transcript.

00:00:01 organ music playing

00:00:10 Zlatuška: Ok, ladies and gentlemen, dear colleagues, I would like to welcome you at the second session of Questions and Answers with professor Donald Knuth. Today, again, there is a possibility to put questions over your phones or whatever connection this works (???). And today's topics are not limited to just computer science, but also to music.

We invited Don for 25th anniversary of Faculty of Informatics. Not only as the first honorary doctor of informatics of this university and this faculty, but also as personality who transcends boundaries, and especially we felt that it would be interesting to have him here also as a musician.

I believe he's got at home not only his work office devoted to The Art of Computer Programming and Informatics, but also to music. He built his own organ in his house at Stanford, so this other Donald Knuth, I believe, will be for many people as interesting as Donald Knuth, the author of The Art of Computer Programming. If you look at that from other perspective, I feel that the idea of programming as an art—Don quoted that yesterday—is something which resonates with this second personality, but I hope that there will be also questions concerning this part.

Now. I thought Donald travelled with this, but he travelled so light, but it would be impossible so... The floor is yours with the questions. Any questions from the floor?

00:02:46 Knuth: Right, so, hello, everybody. I want to thank again for the wonderful hospitality this week, and before I forget, I also want to mention that there's another lecture today by Dana Scott. I think 4:30 in the afternoon. So, you know, if I give a bad lecture, you at least get one good one today. Zlatuška's laughter

The other thing I wanted... Before we start with new questions, I had a couple things to say. First of all, I don't know if you've ever given a lecture, but the night after it you wake up in the middle of night saying "Oh, I should have said that!" and so I thought of at least two things that I wish I had said yesterday.

So in the first place, I was trying to explain why the question about P versus NP is not as simple as people usually think when they talk about whether there exists an algorithm that runs in polynomial time, and they think it's the same as saying that we could know an algorithm that runs in polynomial time. But there's a big jump between that, and then someone asked me later on about the artificial intelligence. So it occurred to me during the middle of the night that one way to think about it is this:

I want to give an example where maybe there exists an algorithm to decide the 3-SAT problem in polynomial time. But we won't know what the algorithm is. So imagine that we have a problem of size n, and we build, let's say, (n ^ 1,000,000)-state, some kind of a neural network that has n ^ 1,000,000 neurons. So this is a polynomial number of things. Just add a few more [zeroes to the exponent]. So now we trained this neural network on lots and lots of SAT problems. You know, we've got great advances now in machine learning theory. Now I feed it a new SAT problem, and how do I know that it's not gonna solve all of them? In fact, in order to prove that, we couldn't possibly train this neural network. In order to show that P is unequal NP, we would have to show that there's no way to train this neural network to do it.

And that's a situation that we're faced with. Right now, when we do train neural networks, we've got something that solves the problem, but we have no idea what the network is doing inside. And that might be a way to think about the difference between an algorithm existing and an algorithm that we know what it is. Ok. Do you have a comment on that?

00:06:38 Zlatuška: If I may.

00:06:39 Knuth: Yeah.

00:06:42 Zlatuška: Could you extend this problem to the problem of human mind? The human mind and limits of human mind?

00:06:49 Knuth: Okay.

00:06:50 Zlatuška: Because that laughter obviously... That's obviously similar problem.

00:06:55 Knuth: Yeah.

00:06:56 Zlatuška: So what's your idea about limits, the capacity of human mind? You know, the ideas like mysterianism, and the existence of problems which are inaccessible to human mind?

00:07:13 Knuth: In that case, we actually have rigorous proofs, because there are incompressibility theorems. So we know that there are things that cannot be made small, and so the human mind can't possibly understand something that has more states in it then there are, well, let's say, protons in the universe or something like this.

00:07:39 Zlatuška: So, something between man and the God.

00:07:41 Knuth: Yeah. But in one of my papers, I have a number that I called... I don't know, I forget... I shall call it Super K, which is also the name of a breakfast cereal in America, but anyway, I needed a special font in order to do it. Like I wanted to print it only in color, but if you look with a magnifying glass at the paper where I talk about Super K...

Anyway, this was a number that was, I forget, it was something like 10 ^^^^ 3, which is defined in terms of the [Knuth] arrow notation. Anyway, I was once giving a talk at Livermore Lab where they were trying to impress me by how big their equipment is, so I said: "Well, here, let me show you some big numbers that are bigger than you ever thought of before. When you try to think—what is this number Super K—this simply means writing on blackboard that you take ten... let's see... quadruple arrow I don't even remember the thing... Anyway, 10 ^^ 10 is equal to 10 ^ 10 ^ 10 ^ ... and then if you want to go to triple arrow, then you simply do this that many times. Pretty soon, it gets mind-boggling.

But still, this number is finite, and almost all numbers are bigger than this. laughter You get a little idea that even though computer scientists stick to studying finite numbers, we aren't limiting ourselves too much. There's still a lot of interesting stuff down in... I don't necessarily insist on immortality, I would settle for living this long. laughter

00:10:11 Zlatuška: And if I may misuse the moderator's role, I would like to ask about music a bit. Within Fantasia Apocalyptica, you have lots of quotations from... or sort of inspirations from other authors. And what seems to me really fantastic is the scope. You go from Gregorian chants to authors whose music is sort of dramatic, like Olivier Messiaen. And incidentally to see quotations from Olivier Messiaen and Bruce Springsteen at the same time, well, both of them are favorites of mine, but what seems to me interesting, just to combine those absolutely different styles which are usually considered incompatible. How did you solve this compatibility problem?

00:11:16 Knuth: So come on Friday, but what's your opinion of rap music? Zlatuška laughs Because there's a quotation from Eminem as well. laughter And of course Dvořák. There are a few notes that are actually original with me as well. I wanted to mention that now before I forget because it ties in with Brno. When I came 24 years ago, my first visit to this part of the world, as my plane was approaching the airport in Prague, I woke up that morning with a melody in my head. And I wrote it down. Probably in the airline magazine or something, but anyway, I wrote it down, and I kept that piece of paper, and I saved it. I sort of thought of it as a Prague theme. Because really, I woke up and here was this melody and I wanted to write it down before I forgot it.

So fast forward twenty more years, and I'm writing Fantasia Apocalyptica, and I came to a point of the piece where I'm trying to represent Chapter 21... I guess I gotta go back. The point of Apocalyptica refers to Apocalypse, the last book of the Bible. I'm trying something new in this piece, which I don't think had been done before. To make a fairly literal translation of an original Greek text and convert it into musical equivalent. So I find more than hundred fifty motifs for things that are repeatedly used in the Greek text. The same sequence of motifs occurs in my piece...

00:13:55 Zlatuška: You consider yourself Wagnerian?

00:14:02 Knuth: Yes, Wagner had motifs, but he never told anybody what they were. So the differences is...

00:14:13 Zlatuška: He wasn't university teacher, so...

00:14:18 Knuth: For example, the motif for war is staccato. The motif for angels is an arpeggio. keyboard playing The motif for God is a three-note melody. keyboard playing If you're referring to the first person of the Trinity, you emphasize the first note. keyboard playing If you're emphasizing the second person of the Trinity. keyboard playing And guess what the third person of the Trinity. keyboard playing And the motif for the devil, in the book of Revelation, there's also a [sic] Anti-Trinity. And so this is keyboard playing the devil. And there's the first person keyboard playing and the second. The Book of Revelation has about ten thousand words in Greek, almost exactly, and I didn't just go word by word because I want it to be good music.

I use this as the constraints to say what kind of good music is suggested by this pattern of motifs. And when I get to Chapter 21, the story talks about the New Jerusalem. Here's a Golden City coming out of the sky, and that's where I got to use my Prague theme. I'm not sure which... I'll just play it instead of trying to find the absolute best combination of voices. So it goes like this: keyboard playing So, da-da-da da-da-da da-da-da da. That's what I wrote down in the airplane. Then it goes on a few more bars, it uses some of the chord progressions of Dvořák's New World Symphony. And New World Symphony is like New Jerusalem. So this is a little bit of music here, that...

00:16:58 Zlatuška: So this is actually what we loose for not having international airport in Brno. Because if Don landed in Brno, that could have been Brno theme.

00:17:12 Knuth: So if I had never been invited here in the first place, who knows what would have happened. One other footnote to yesterday and that is: There was a question where I referred to Stuart Russell. Now I can give you the definite reference because I recommended that you watch this video. I think it's five minutes long, and it's easy to find. So Stuart Russell... writing on blackboard And there's been a lot of follow-up on it, but this came out not quite two years ago, and it's called Slaughterbots. It's sort of a mind-changing video that I recommend everybody to look at. It's very important, I think, that we should ban autonomous weapons, and there are thousands of computer scientists who have signed declarations and are actively trying to make sure that the dangers are minimized.

So that was end of footnotes to yesterday, now I'm ready for new question.

00:18:38 Zlatuška: So I guess... Have you ever burned out?

00:18:54 Knuth: There was a period about 1990, where I was feeling kind of low and I actually I got a little worried about it, because one of my uncle's had gone through a period where he was, I don't know, not getting along with anybody else in the family and so. So when he got old, and I said: "Oh-oh! Maybe I'm inheriting some mental problem." Anyway, so I went to see a psychiatrist, and he said: "Have you ever heard of a Type A personality?" He was a great doctor, he showed me his textbooks. Instead of telling me, sort of preaching to me, he said: "Here, look. Here's a book I was giving you. If you look in this chapter, you'll see something that describes you to a T (???)."

I learned from that how to reduce the stress, and so it was 1990. So how old am I? 50... 52 years old. And I realized why physical education was a required subject in college. I had never done much exercise, so I started swimming in 1990, and very quickly I was happy again.

But there was a time when... Well, I work sort of 24/7, in some sense, but it's fun. Mostly. I have to psych myself up in the morning, and once I get into something, then it's hard to stop again, so that's why I have to turn off like somebody mentioned yesterday. ... Well, how do I describe my daily schedule?

I have a very peculiar scheduling algorithm. You wake up in the morning, and you have to decide what you're gonna do next. The algorithm that I finally decided to work the best is that I always do what I hate the most. Of all the things that I have no good excuse for not doing, which one would I rather not do. And that's what I choose. So all the time I'm working on something I don't wanna do, in a sense.

On the other hand, at the end of the week, I've got stuff out the door. And I'd have to do those unpleasant things anyway, so as long as there's no good reason to procrastinate anymore, that's what I choose to do. Somehow that turns out to be a better scheduling algorithm than the other way, where, "what is the most fun all the time?"

I noticed that my mood, when I start feeling bad, is really if several weeks have gone by, and I've never had a time to do anything creative. There's something, there's some urge that says: "Prove a theorem or something!" So if there's too much busywork, I can stand that for a little while, but after three weeks I have to try to do something new. I can't explain why that is. But that seems to be true.

00:23:07 Zlatuška: I would just add to that Stuart Russell, for anybody interested: There is a new book, which is Human Compatible by him and that was published yesterday.

00:23:18 Knuth: Oh, yesterday! smiling ... Human...

00:23:22 Zlatuška: ... compatible. Staying... artificial intelligence and the problem of control. And that looks pretty much as this topic.

00:23:39 Knuth: Very good.

00:23:40 Zlatuška: Tabs or spaces?

00:23:43 Knuth: Tabs or spaces? smiling You're going back to that question again? Knuth laughs

00:23:45 Zlatuška: Oh! Okay, it was... ???

00:23:51 Knuth: No, I have a question: Why does [sic] people ask about tabs or spaces? To me, when I make somebody else's code in order to read it, [and] it comes in with tabs, it confuses TeX. The Tab prints as a letter gamma, so I have to go through it, get rid of all the Tabs, and change to space, and then I can print the file.

00:24:18 Zlatuška: That's a proper answer, after which nobody would ever use Tabs.

00:24:22 Knuth: laughing Ok.

00:24:26 Zlatuška: Ok. Biggest challenge of becoming a good programmer?

00:24:29 Knuth: Biggest challenge of becoming a good programmer? Well, being born a geek. I know, some people think that it's just a matter of motivation and trying harder and keep educating, read and write right books and so on. Well, that might be true, but my experience is differently.

My experience is that I know many many intelligent people who are, no matter how motivated they are, I don't think they'll ever be a good programmer, and conversely, I know that I'm never gonna be good as a programmer of a quantum computer. There's something about the way my brain works that gives me a great intuition for the classical computer, but not for quantum computing. And it's not a matter of good or bad or trying or harder or not being motivated. It's a quirk that I happen to [have] been born with one of these peculiarity [sic].

00:25:45 Zlatuška: What's your idea in this context about sort of mandatory courses of programming within elementary school? If it is true that not everybody can be a programmer.

00:25:58 Knuth: No, no! You left out the word "good". laughter

00:26:02 Zlatuška: Ah, ok. laughter

00:26:04 Knuth: I think people can become a programmer [sic], but dogs can walk on their hind legs.

00:26:10 Zlatuška: So you feel that there's not enough of bad code.

00:26:15 Knuth: What I'm saying is: If you somehow realize that you've been born a geek, then you owe it to the world to use that talent because the world needs this talent. That's the way I look at it.

00:26:39 Zlatuška: Vim or Emacs... That was also yesterday. I am not quite sure...

00:26:42 Knuth: Vim or Emacs. Yeah, yeah, ok. I just did admit to using Emacs, but I learned how to use vi enough to know how to quit. laughter That was the hardest first lesson. I mean, I had to go Control-Q or something, I don't know.

00:27:03 Zlatuška: Do you think that we are living in a computer simulation?

00:27:06 Knuth: Do I? smiling

00:27:10 Zlatuška: Is your god a programmer?

00:27:12 Knuth: It's hard to tell. laughter So whether I think so or not doesn't matter. The whole question about how far artificial intelligence could go: It certainly could go to the point where it has decided that we should have this gathering today.

00:27:40 Zlatuška: There's one consequence of living in computer simulation because that means that the world would be only processes which are computable.

00:27:50 Knuth: And finite, yeah. So, for example, the game of life can simulate any such thing. You have any universal scheme, then it would represent the lecture I'm giving now. As one very special case, it would represent Stuart Russell's book, etc. It would represent all discordant ways to write the Fantasia Apocalyptica.

00:28:27 Zlatuška: What was the worst code you have ever seen?

00:28:30 Knuth: What was the worst code I have ever seen? Hey, I love this! smiling

00:28:33 Zlatuška: All you down to ??? level.

00:28:36 Knuth: No, no. I had this student in the 70s who was not born a geek laughter, but he came to Stanford from, I think, West Point. Anyway, he was trained as a soldier, and he would follow orders. He was not a Ph.D. student; he was master student. But he did a master's project which was to automate the system that we had in the computer science department for sharing technical reports with other universities. So we had to make subscriptions to others, and then if they send us their reports, we send them our reports gratis. We had this large database, sort of... data processing problem. So we needed somebody to do that, and I gave that to him as a master project. He wrote a system that was going to handle the technical parts. I saw the thing, I was busy at the time, and it looked like the right number of pages and so on. And it had a sample where he had taken a couple of... a small database with a few reports, and it gave the right report, so I gave him A on it, and he got his degree. Well, that was in June.

Then in July, the secretary called me: "So Don, we're having a little problem using this system." So I went, and that was one of my first trips to the Stanford AI Lab, where they had special computers there. I started looking at the code that he had written. I got to page three or page four, and it was an example of shellsort, a sorting routine, but it was implemented... It was the first time I had seen a program where I could change one character in the program and make it run hundred times faster. laughter And the thing was, the variable should have stepped by H instead of by one. So he wrote shellsort so that it was just a plain old insertion sort. And clearly, he didn't understand that. So I made a copy of that page: "Hey, I gotta show this to my students next ???!" Then I turned to the next page, and he did a binary search on that.

So every page I turned to, I saw a new kind of programming error that I had never seen before. laughter And finally I looked at the whole way he had organized the thing. It's really hard to explain, but the text editor that we used in that day—this was way before Emacs—it would start out with an index page, so text editor would always prepare automatically a table of contents at the beginning. He had assumed that text editor would always put all of the whole database into alphabetical order in just the way that you could read it, knowing that there would be line breaks or anything like this. So it was impossible to fix the program. You couldn't possibly write a program that was assuming that you were gonna use the text editor's database for table of contents to do the data processing. So that wins my vote.

00:32:54 Zlatuška: Well, given the fact that programming is actually about giving orders, and maybe he studied military academy. That means some privates should never be given the ability to issue orders.

Do you have any experience with psychedelic drugs, like Richard Feynman? Altered state of consciousness. LSD, psilocybin.

00:33:30 Knuth: No, I'm glad that I didn't, nor did my kids. As far as I know. Near-death experiences? No.

00:33:43 Zlatuška: Any problems you gave up on trying to solve?

00:33:47 Knuth: Any problems you gave up on trying to solve, yes. Many times. In fact, I certainly thought that I had proved that P was unequal NP rather earlier. And after I had solved it, then I wrote it up, and finally, everything disappeared, just about as I was writing the last line of the paper. I realized that it was hopeless.

I can remember the first time I actually solved a problem that I had given up on, which was a kind of a breakthrough. As a student, I had tried various things, and I sort of had a "give it five days and, if you haven't got any ideas, then let it go." But once, I let it go, and the next morning, I woke up, and I said: "Wait, what if I tried this." When you do work on a problem and fail, there's one trick you can try, and that is: Imagine somebody sent you email or letter or knocked on your door, and said "So ??? I just solved that problem." And then use: "Oh, I bet I know how he did it." Somehow, if you think the problem can be solved, sometimes it helps you solve it.

But the one that was most dramatic for me, I guess, years ago, when I started, about one third of computer science was a study of programming languages, and now my collected papers collected in eight volumes, and one of those volumes is all the papers that I wrote about programming languages. There's a journal called SIGACT News that has book reviews, and they have a page in there saying: "Here are books that we've received. Would you like to review them?" And this collection of my papers on programming languages was on that list for a couple years. Nobody wanted to review it. So nobody cares about this although this the hottest thing in computer science when I started.

I worked on a problem that was called parentheses languages. So I think everybody still knows what a context-free grammar is. A way of defining a language in terms of productions. But some context-free grammars have the property like nested parentheses. So if you look at the language, half of the characters are like left delimiters, and half of the characters are like right delimiters. And every string in the language has nested left and right delimiters, properly nested. So the question is: "Somebody gives you a grammar. Is the language that it generates a parenthesis language?"

The grammar won't show any matching between these, but can you somehow look at the grammar and figure out yes or no? Is it really gonna be possible to do this? That was an open problem, and I worked several weeks on it and finally gave up. But then, I think a week later, the key came to me how to solve it. And so, at that point, I was quite delighted to have the solution. I was able to use the insights I got from that when I was doing other work later on, but as far as I know, nobody has ever read that paper.

00:38:12 Zlatuška: Do you solve many programming problems or create music when you sleep?

00:38:17 Knuth: Do I... solve many programming problems, create music when I sleep? So, no. laughter

With respect to the Fantasia, it was kind of interesting that after I started working on it, I had the feeling that the music had already been written, and I just had to listen for it. I don't know, out of body experience... it's like I was channeling in a way, that it was there. It did feel that there was a muse helping somehow.

Now, with respect to programming problems, it goes the other way. If I'm trying to figure out how to solve a programming problem, I can't go to sleep. So I need somehow to either solve it or forget it. But when working on a difficult problem, I usually fill up sheets and sheets of scrap paper, and so I can't keep it all in my head, but I have to write down a whole bunch of stuff in order to get it into my brain. But when it comes to the point, when I can actually think about that problem when I'm swimming, then I know I'm about ready to solve. My brain has absorbed enough so that I've learned how to go from baby steps to giant steps in this territory, the problem domain. So there is this mysterious thing that takes place once I'm ready to do it.

So I always say to my grad students... They're working on the thesis, and I realized early on that was a good idea that they should keep. Every week when we would meet, they would write down in detail what they had been thinking about that week and what was on, what do we know, what don't we know. Then after the problem is solved, you can look at that, and I can use that to prove to them that they solved a hard problem. Because once you solve the hard problem, you think it was obvious, I didn't do anything. But once you see how many hurdles you actually got through... This was good.

00:41:42 Zlatuška: Also yesterday you mentioned that you are Platonist with respect to mathematics.

00:41:48 Knuth: Yes.

00:41:49 Zlatuška: Are you Platonist with respect to music? Music is up there and...

00:41:57 Knuth: The music of the spheres. There's a question. Why is it that some music I can hear ten times and next time I hear, it's just as if I never heard it at all.

00:42:46 Zlatuška: This happens to some students with mathematics. laughter

00:42:28 Knuth: With mathematics as well, yeah.

But, for example, in the old days, when you have CD, I mean long-play records, they would always have to add to the piece you wanted, they had to add something else to fill it out. So I have something by Brahms, and then the publisher added a piece by somebody named Bax. B-A-X. I've heard the piece by Bax as many times as I've heard the piece by Brahms because it's hard for me to get up and turn off the record player. However, I'll never recognize the piece by Bax the next time I hear it. So there's something different about Brahms's music and Bax's music, and I haven't been able to reverse-engineer that at all.

My piece [Fantasia] has parts of it that involve more less random elements. And the question was, well, if you just have random music, does the human brain somehow learn to do it? Well, it didn't work with Bax's music, but there are parts of it where I based on Morse code. I had to make a decision how to spell some Greek words. It turns out that in Ancient Greek, they had a notation for absolute pitch, so you could spell a Greek word just by playing those notes. Let's see if I can find... There's a place in Chapter 2 where the name Jezebel comes out. So Jezebel in Greek is iota, epsilon, zeta, and so on. I think it comes in here... Yeah. music playing That's Jezebel. It's kind of ???. Now Jezebel was a prophetess, and the motif for prophet is contrary motion. And so after I play Jezebel, then I play it contrary motion. But anyway, that's random. Still, our brain gets it in, we find ourselves humming. Jezebel, even though there was no reason why we should be able to remember that melody.

So I'm not sure to what extent you can take random elements, and they actually become warm and somehow have a personality. On the other hand, if you have no randomness whatsoever—musicians found long ago—that if you go straight one two three four, one two three four, exactly right, it loses life. You have to go a little bit before the beat, a little bit after the beat in order for music to come to life. And I tried the same experiment with font design. So instead of drawing a letter precisely, I would wiggle some of the points a little bit, and then the alphabet seemed to have a personality.

00:46:26 Zlatuška: Software patents. Software patents, can you elaborate your stance regarding software patents. Patenting software. The second from bottom.

00:46:39 Knuth: Second from bottom? Stances regarding software patterns.

00:46:46 Zlatuška: Patents. Intellectual property.

00:46:49 Knuth: Patents! Ok, aha. Software patterns is another thing, okay software patents, right.

I think people deserve protection for their ideas, but not if just the ideas are trivial. So a great number of software patents were something that we would expect any student to do on an exam, but a lawyer—a patent lawyer not being a geek—wouldn't know how to distinguish those. And so there was a time when people went and tried pro bono make a patent on every trivial idea. So that people wouldn't be able to make us pay them every time they use this trivial idea.

When I wrote TeX, I didn't need to get permission for any of the ideas that I use, the trivial ideas that I used in TeX. But after intellectual property rights got more and more complicated, it might very well have been impossible to write TeX twenty years later.

So when it comes to a substantial piece of software, like the undoing mechanism in Photoshop or something like this, I think this really deserves patent protection for a limited amount of time, but not in perpetuity. That's my general feeling about patents in a nutshell.

00:48:48 Zlatuška: What's your favorite music band?

00:49:10 Knuth: My favorite music... band? laughter I remember The Beatles. But lot of the music after that sounds like noise to me.

00:49:27 Zlatuška: Some of the exercises in The Art of Computer Programming are known to be open research problems. Has anyone ever contacted you that they have solved one of them while reading the book?

00:49:40 Knuth: Yes, I think I mentioned that yesterday, but it's not that uncommon.

00:49:48 Zlatuška: And you don't pay actually...

00:49:50 Knuth: No, no, I only pay...

00:49:52 Zlatuška: It became closed problem, so it was an error...

00:50:02 Knuth: It's stated there that if you find a better answer, you don't get money, you get glory instead, and so instead I mention your name. But if you correct an error, I silently correct it as if I had known it.

00:50:22 Zlatuška: What would you like to redo?

00:50:25 Knuth: What would I like to redo if I could? I would base TeX on decimal instead of binary at the lowest level. TeX is based—at the lowest level—on a scaled point, of which there are 2¹⁶ scale point to weigh a point. So internally, everything is kept in binary but is communicated to the user in decimal. So the user doesn't get to see... This leads to strange results. You know, you say one third, and then you multiply it by three, and you get 0.999 instead of one. So that would have been better to do that.

00:51:30 Zlatuška: Do you still use TeX often?

00:51:34 Knuth: giggles Well, let's see... I haven't used it since last Friday because I've been in other town.

Here's a... Oh, I see. You're not raising your hand, you're raising the camera. Ok. But other people out here who...

00:51:47 Zlatuška: Anybody from the audience?

00:51:51 someone: Can you play something?

00:51:53 Zlatuška: Can you play something?

00:51:54 someone: Like a longer piece.

00:51:56 Zlatuška: Longer...

00:51:58 someone: Anything you like.

00:51:59 Knuth: Well, I only have this music here. So, choose a random chapter.

00:52:05 someone: Uh... Seven? laughter

00:52:07 Knuth: Seven. Ok, so seven is the chapter where the saints come marching in. And...

00:52:17 Zlatuška: 3:16?

00:52:18 Knuth: What?

00:52:19 Zlatuška: 3:16?

00:52:32 Knuth: So there are different motifs here. I'm trying to see which are the easiest to explain. Well, ??? mentioned that [it] has lots of different styles, and since this is about the Apocalypse, one of the styles had to be calypso. So in Chapter 7, we get calypso: music playing Now, that's trying to imitate an organ. Let's try to just do a piano. I don't know how to do this here. Voice... Voice "church [organ]"... Let's change other voices... How do we go down?

00:53:30 Szaniszlo: What kind of voice?

00:53:34 Knuth: Just take piano, for example. Grand piano, here we go. music playing Now this last thing is music playing Harry Belafonte, so "run Venezuela". music playing and Knuth singing "She ran with the tailor." laughter That's what I'm singing to myself when I was writing this piece. However, this is, of course, taking place as the saints come marching in. music playing So at this point there's a grand shout, comes along, and chord plays at the is called music playing. That's God. music playing Next is: music playing This is the motif for the lamb, one of the principal characters, and it's supposed to sound like baa baa. music playing So the scene we have here is that the saints go onto this hill, and then there are 24 elders, and the elders form a chromatic scale of 24 notes. music playing Besides the elders and other characters are Seraphim, and there are four creatures, and the theme for the four creatures is music playing. And you can do this: music playing.

Is that enough? applause

00:56:14 Zlatuška: By the way, is it difficult to actually play something for organ just on piano? If I understand...

00:56:23 Knuth: Yes, but it's also very difficult... It's also very difficult to play this on the organ. Jan [??? Rotrekl, the performer of the Fantasia Apocalyptica], the organist, has had to work very hard in order to do it. When I wrote this piece, I didn't hold back. I knew it was the only piece I was ever going to write, and so I didn't bother to simplify it. I wrote what I thought I wanted to hear, and so he has to play what I wrote.

00:56:54 Zlatuška: With (???) Don, when I asked him [Don] whether we can perform this, he mentioned that the organist who did the world premiere was ill and unable to play that, but there is a proof that it is playable. laughter

00:57:11 Knuth: laughs Yes. I can play it, but not at speed. Well, the organist who did work on it actually fell in love with—I'm glad to say—and he wrote me a couple weeks ago saying that you he's feeling withdrawal symptoms, he wants to play it again.

00:57:45 Zlatuška: Anybody else?

00:57:47 someone: I have a question. I have read about your WEB and CWEB projects. Do you think that the problem in computer science that you were trying to solve with this projects is already solved by maybe new programming languages or different approaches towards documentation? Or do you think that the projects are still relevant today? And maybe a follow-up: If you had ability to write CWEB or WEB again today, would you do anything differently than you did before?

00:58:14 Knuth: To me, it's one of the things I love the most about my life, is that I can write programs in CWEB. However, in order to do that, I'm also living with the fact that the implementation that I have had never been tuned up to a great programming environment. So, for example, I start a CWEB program, and I always type a few things. Like I always type a line that says: @... at-sign asterisk index period, and I put that at the bottom. It's a little bit of a nuisance, but in fact everything in life has some small nuisances, and so as long as something is working for 97% of the time, I'm not gonna spend much time figuring out the 3%, but a mature program, they start fixing up the 3%.

So I use CWEB knowing that it was a quick and dirty implementation, but it still does almost everything that I want, exactly as I want. And I have an Emacs interface to CWEB. My wife will tell you I come out of my office several times a day saying: "It's so fun programming in CWEB!"

And the reason is that as I'm doing it, it seems to me that I'm combining the formal and the informal aspects of the program the way they ought to be. In order to understand any complicated technical subject, one of the main tricks of it, of a person who writes about computer science, mathematics, is to say everything twice: once formally and once informally. Maybe three times, but from different perspectives, but you don't only give a formula, but you say what the variables in the formula mean. You write a program, you not only declare something to be ??? and a variable. You say what has an invariant relation: This is the number of nonzero elements in the array or something, but you combine formal and informal.

And that's the way I CWEB works. It breaks down a program into a small number of pieces that fit together in a small number of ways. But each module of the program is a combination of informal—which you write in natural language—and formal—which you write in whatever formal language you're using. In CWEB, it's C, but there are many different flavors of web.

So I really think there's nothing else anywhere near as good as an approach, but I know that there are many ways to refine it, and I'm not interested in actually pursuing the refinements because it's good enough for me. On the other hand, most of the world writes... you look on the solid programs on GitHub. You'll find that they're probably not using CWEB, but there's a certain style that's become... I don't know, I don't like C++ program because... it's so ambiguous. Each C++ compiler does different things with these programs, and so when people... If somebody sends me a program in C++, I don't know what subset of the language they're using. There's all kind of things going on automatically, and the programmer knows what she's doing, but their reader doesn't know which subset is there, so I don't care for that.

But let's suppose we look at a typical module that we get, that's written in C, and it's a style of programming that people have learned to read and maintain, and so it works. I can say: "Oh yeah, let me rewrite your program in CWEB, and you'll see that it actually not only is better, it's more reliable, and you'll realize that certain features were missing because of the discipline of literate programming." However, I don't believe I'll ever convert the world with this. It'd be like saying Esperanto is a much better language than English, so therefore let's abolish English. English works well enough so that some ideal language isn't going to displace it.

01:03:49 Zlatuška: There's question by Tim: Paul Erdős spoke of book in which God kept the most elegant mathematical proofs in the same sense of divinity that are key??? I would extend this also to the most elegant programs, but...

01:04:14 Knuth: I read a very strange paper recently where they asked people to compare algorithms to music. One group of subjects, they were supposed to compare algorithms to music, and another group of subjects was supposed to compare the algorithms to art. Where was this paper? It was one of the papers I read in the last three weeks. Anyway, these people presented keep sort, binary search, ... they took five algorithms that they thought were classic, and then they showed the subjects several pieces of music, and the subjects were supposed to say: "Okay, now match this algorithm to this piece of music." They found—maybe a hundred subjects—that there was a fairly good correlation, it wasn't random permutation of this matching between algorithms and music. But then they did another group, and they showed them five paintings, and they were supposed to again associate this with the painting, and that didn't work at all. But maybe they didn't choose the right paintings. I don't think all kinds of art are equivalent. Certainly, there's a quantitativeness to music that's similar to computer science.

01:06:07 Zlatuška: Suppose we create a technology to faithfully copy and simulate working human brain. Would you want to continue living as such a simulation? That's apparently the Kurzweil's idea.

01:06:26 Knuth: So there's a line in... That's a Gershwin's song Ain't Necessarily So. And it says something like Methuselah lived nine hundred years. Methuselah lived nine hundred years, but who calls that livin' if no goal won't give in to a man who was nine hundred years. So there's more to living than thinking.

01:07:09 Zlatuška: Your favorite fractal?

01:07:10 Knuth: My favorite fractal. Well, it has to be the dragon curve because that was the first one I knew about. The dragon curve—you can look it up—but basically, you take a long sheet of paper. Like thin sheet of paper, like we used to have adding machine tape or something. And you fold it in half, you crease it, you fold it again, and you fold it again, so each time it gets half as big as before. And you've got creases in the paper. Then you open it up, some of the creases go down, and some of them go up. It makes a pattern. An interesting pattern that also turns out to be equivalent to the Legendre symbol of minus one over anything (???). Anyway it's a pattern. You open up the paper, and you make all the bends go ninety degrees. So it'll go like this drawing on blackboard, and then go like this... something, left-right, left-right. You can round off the corners if you want, but this is the idea of dragon curve.

It turns out it never intersects itself, and if you take four of them, and start them out... I probably didn't drop correct dragon curve, but if I take four of them, it will cover the entire plane, with four of them. I had a lot of fun proving that theorem in the 80s. And I was really proud when that theorem was picked up in Russia in Quant magazine, which late sixties, of course, there was the iron curtain then, and they illustrated my theorem with four colors in this magazine written for high school students in Russia. It says, you know, I knew enough Russian to translate it, it said: This is a difficult theorem, it was proved by Donald Knuth.

Now we see Czech version of... my books.

01:10:00 Zlatuška: I think the topmost question was already tackled.

01:10:06 Knuth: Are there any other questions from the...

01:10:09 Zlatuška: From the floor?

01:10:13 someone: What kind of organ do you have at home? Is it a pipe organ? Mechanically controlled or a digital or electronic...

01:10:17 Knuth: Yes, it has 850 pipes or so, and the website explains it all. If you go to my home page and look under pipe organ. It was built by a firm called Abbott and Sieker—they're both dead now—but they used to make about four organs a year. And it has 17 ranks of pipes, and I have a major exercise in Fascicle 5—which is coming out next month to say—how many different sounds can you make on this organ that have exactly five pipes going, or exactly six pipes going, or so on. I found it to be quite a fascinating exercise. So if you want to know more about the organ, online has the specs, but also then you've got to buy the book, [to] look at this exercise about that organ that I have.

01:11:28 someone: So I assume that you also prefer pipe organ, mechanically controlled, instead of say, digital organs.

01:11:37 Knuth: I am sorry, I don't understand the question.

01:11:39 Zlatuška: You prefer classical organ to digital?

01:11:43 Knuth: Oh, I see. Yes, absolutely. I heard a pretty good digital organ in England in July, but it's quite rare. They make good digital recordings of organs, most of the organs that I've ever had a chance to play. Even though it's in a great building, and you had the reverberation and everything, it just doesn't match.

I come from a part of the United States where it was illegal to some—it's called America's Dairy State, America's Dairyland—and so it was illegal to sell margarine instead of butter in our state. If you wanted to get margarine, you had to go to Illinois laughter to buy it, it was a little cheaper. But I look at butter versus margarine, that sort of has the difference between pipe organ and electronic organ. But also in the early days, before we had good resolution in fonts, there was good printing–butter–and there was the kind that we could get in our lab in the early days–margarine.

01:13:21 Zlatuška: You originally wanted not to have your organ built by some American company, but you imported from some Nordic country. Do you regret that did not work? Or...

01:13:38 Knuth: I heard some really beautiful organs in Denmark, and I inquired about having a Danish organ, and this was in the 70s, there was only one Danish organ in America at that time, it was one in Boston. So I had talked to the builder, and then I found out that there was no way... I had a limited budget, and according to Danish law, the only way I could buy this organ was to agree that the price was indeterminate until after it was built because by Danish law whatever the Union workers wanted to get for it, had to be the amount that was done. So they couldn't get me a fixed price for it, and I might have gone broke, so I was unable to do that.

01:14:46 Zlatuška: So your love for organ was not that big that you would get broke because of it? laughs

01:14:53 Knuth: The organ that I finally bought cost $35,000. People were paying that for a house in those days. Now you get a house for $35,000, it's impossible.

01:15:12 Zlatuška: What will happen with your organ when the lease of your house expires?

01:15:19 Knuth: Who knows. But it has only existed in this room. People could unscrew it and reassemble it somewhere.

01:15:33 Knuth: Somebody else? Ah, over there.

01:15:36 someone: You mentioned once that in Super Bowl game the crowds, they ave flags with... showing 3:16 on it. I've always been puzzled what does that have to do with football game.

01:15:57 Knuth: There are people who flaunt their religion. And the most famous verse in the Bible by its number is John 3:16, which is said to be the gospel in a nutshell. It says the God loved the world in such a way that He gave His only child, and so on. So that's a very famous verse of the Bible. People think that by putting that number up that will give publicity, to make people look up this verse and they will suddenly realize that this should be their religion. At football games, it just happened that the cameras, the camera crews survey the crowd, and so this was a way to get advertising for whatever slogans you wanted to do. And a certain group of people started doing it.

Then there were jokes based on. I mean, there was in baseball game... what was his name... a guy from the Boston Red Sox, but anyway his batting average was 0.316, and his nick, his first name was John. So people hold up a chart saying "John! 0.316!" And this was to be a satire on this phenomenon. But it was something that sort of grew like... we have bumper stickers, slogans that people put on their cars and things like that.

But the fact is that this number, the verse got popular by its number, and I used that later when I wrote this book called 3:16 because I wanted to use a cross section of the Bible in order to understand the complexity of it and have some way of sampling. So I used this in order to get a good cross section of not the Bible itself so much, but all the secondary literature about the Bible. So there have been 100,000s of books written about the Bible, but I could go into a theological library, and most of those books have an index in the back, and they'll say which verses do I refer to. So I go through, and I find out, oh yeah, I only have to read a dozen pages of this book, and I can see what it says about Genesis 3:16 and what it says about Revelation 3:16.

By the way, Revelation 3:16 is one of the verses that's here [in Fantasia Apocalyptica], so I might as well go to Chapter 3. flipping pages The verse Revelation 3:16 says something like "because you are lukewarm, neither cold nor hot, I will spit you out of my mouth." The message is that God prefers atheist to people who don't care at all. So when I do verse 3:16, I had a little fun in the music. I used time signature 3/16, which is three sixteenth notes to a measure. And then it says: "I will spit you out of my mouth," so on the organ, we have here in the church on Friday, has a pipe called the spitzflute, so we use a spitzflute for this spitting out of the mouth. So it goes anyway music playing and then spitz! music chord Listen for that on Friday.

01:20:28 Zlatuška: I guess that we basically finished the time allocated for this. There will be the question: "How are you today?" but that will be postponed for next time. Maybe if Don wakes up in the night, maybe he starts with another sermon in the Church, but... Now, that was just a joke.

So thank you very much, I believe that... applause Thank you very much for coming, for having these sessions with us. An invitation to everybody for Friday, 7 p.m. in the Church of Jesuits, where the piece Fantasia Apocalypsa [sic] will be performed.