Donald Knuth: Algorithms, Complexity, and The Art of Computer Programming | Lex Fridman Podcast #62

Lex Fridman 0:00 The following is a conversation with Donald Knuth, one of the greatest and most impactful computer scientists and mathematicians ever. He's the recipient of the 1974 Turing Award, considered the Nobel Prize of computing. He's the author of the multi-volume work, the magnum opus, The Art of Computer Programming. He made several key contributions to the rigorous analysis of computational complexity of algorithms, including the popularization of asymptotic notation that we all affectionately know as the Big O notation. He also created the TeX typesetting system, which most computer scientists, physicists, mathematicians, and scientists and engineers in general use to write technical papers and make them look beautiful. I can imagine no better guest to end 2019 with than Don, one of the kindest, most brilliant people in our field. This podcast was recorded many months ago. It's one I avoided because, perhaps counterintuitively, the conversation meant so much to me. If you can believe it, I knew even less about recording back then, so the camera angle is a bit off. I hope that's okay with you. The office space was a bit cramped for filming, but it was a magical space where Don does most of his work. It meant a lot to me that he would welcome me into his home. It was quite a journey to get there. As many people know, he doesn't check email, so I had to get creative. The effort was worth it. I've been doing this podcast on the side for just over a year. Sometimes I had to sacrifice a bit of sleep, but always happy to do it, and to be part of an amazing community of curious minds. Thank you for your kind words of support and for the interesting discussions, and I look forward to many more of those in 2020. This is the Artificial Intelligence Podcast. If you enjoy it, subscribe on YouTube, give us five stars on Apple Podcast, follow on Spotify, support on Patreon, or simply connect with me on Twitter @lexfridman, spelled F-R-I-D-M-A-N. I recently started doing ads at the end of the introduction. I'll do one or two minutes after introducing the episode, and never any ads in the middle that break the flow of the conversation. I hope that works for you and doesn't hurt the listening experience. I provide timestamps for the start of the conversation that you can skip to, but it helps if you listen to the ad and support this podcast by trying out the product or service being advertised. This show is presented by Cash App, the number one finance app in the App Store. I personally use Cash App to send money to friends, but you can also use it to buy, sell, and deposit Bitcoin in just seconds. Cash App also has a new investing feature. You can buy fractions of a stock, say $1 worth, no matter what the stock price is. Brokerage services are provided by Cash App Investing, a subsidiary of Square and member SIPC. I'm excited to be working with Cash App to support one of my favorite organizations called FIRST, best known for their FIRST Robotics and Lego competitions. They educate and inspire hundreds of thousands of students in over 110 countries, and have a perfect rating on Charity Navigator, which means the donated money is used to maximum effectiveness. When you get Cash App from the App Store or Google Play and use code LEXPODCAST, you'll get $10 and Cash App will also donate $10 to FIRST, which again is an organization that I've personally seen inspire girls and boys to dream of engineering a better world. And now, here's my conversation with Donald Knuth.

Lex Fridman 3:45 In 1957 at Case Tech, you were once allowed to spend several evenings with a IBM 650 computer, as you've talked about in the past, and you fell in love with computing then.

Donald Knuth 4:00 Yeah.

Lex Fridman 4:00 Can you take me back to that moment with the IBM 650? What, what was it that grabbed you about that computer?

Donald Knuth 4:09 So the IBM 650 was this, this machine that, uh... Well, it didn't fill a room, but it, it was, it was big and noisy. But when I first saw it, it was through a window and there were just a lot of lights flashing on it. And, uh, I was a freshman. I had a job, uh, with the statistics group, and I was supposed to punch cards and s- a- a- for data and then sort them on another machine. But th- they got this new computer came in and I... and, um, it had, uh, interesting l- you know, lights, okay. So well...

Lex Fridman 4:50 (laughs)

Donald Knuth 4:50 ... but I had, I had a key to the building, so I can, you know, I, I could get in and look at it and got a manual for it. And, and, uh, my first experience was based on the fact that I could punch cards basically, which was a big thing for the... But the, but the IBM 650 heck was, uh, you know, big in size, but, but, uh, i- i- i- incredibly small in power-

Lex Fridman 5:10 In resources.

Donald Knuth 5:11 ... uh, in memory.

Lex Fridman 5:12 Yeah.

Donald Knuth 5:12 It, it had, it had 2,000 words of memory, and, and a word of memory was ten decimal digits plus a sign. And it, it would do, uh... To add two numbers together, you could probably expect that would take, oh, say three milliseconds. So th-

Lex Fridman 5:30 Still pretty fast. It's... The memory is the constraint, the memory is the problem.

Donald Knuth 5:34 That was why it was... it took th- three milliseconds, because it took five milliseconds for the drum to go around, and (laughs) you had to wait, I don't know, five cycle times. If, if you have an instruction, uh, in one position on the drum, then it would be ready to read the data for the instruction and, and, uh, uh, y- you know, go th- th- three notches. The, the drum is 50 cycles around, and you go three cycles, e- e- and you can get the data, and then you can go another three cycles and get, and get to your next instruction.... if the instruction is there. Otherwise, you, otherwise, you spin until you get to the, to the right place. And it, and we had no, uh, random access memory whatsoever until my senior year. In my senior year, we got 50 words of random access memory-

Lex Fridman 6:17 Ooh.

Donald Knuth 6:17 ... which were, which were priceless, and we would w- and we would move stuff up to the, up, up to the, uh, random access memory in, in 60-word chunks and then we would start again so s- subroutine wouldn't go up there and ...

Lex Fridman 6:31 Could you have predicted the future 60 years later of computing-

Donald Knuth 6:36 No.

Lex Fridman 6:36 ... from then?

Donald Knuth 6:37 No. Y- you know, in fact, the hardest question I was ever asked was, uh, "What could I have predicted?"

Lex Fridman 6:44 Mm-hmm.

Donald Knuth 6:44 In other words, the interviewer asked me, she, she said, you know, uh, y- you know, "What about computing has surprised you?" You know, and immediately-

Lex Fridman 6:52 (laughs)

Donald Knuth 6:52 ... I ran, I rattled off a couple of dozen things, and then she said, "Okay, so what didn't surprise you?" And I, I was, I tried for five minutes to, to think of something that I, that I would have predicted and I, and I, and I couldn't. All right. But I, let me say that this machine, I didn't know, well, well, it, there wasn't, there wasn't much else in the world at that time. The 650 was the first machine that was, that there were more than 1,000 of ever.

Lex Fridman 7:19 Mm-hmm.

Donald Knuth 7:19 And before that, there were, you know, there was, uh, each machine there might be a half a dozen examples, maybe, maybe-

Lex Fridman 7:25 It's the first mass market-

Donald Knuth 7:27 ... maybe a couple of dozen.

Lex Fridman 7:27 ... mass produced.

Donald Knuth 7:28 It was the first one that, yeah, th- done in quantity. And, uh, and IBM, uh, didn't sell them, they, they rented them, but, but they, they rented them to universities at, at great, uh, uh, you know, had, had a great deal.

Lex Fridman 7:44 Mm-hmm.

Donald Knuth 7:44 And, and so that's why, uh, uh, a lot of students learned about computers at that time.

Lex Fridman 7:51 So you-

Donald Knuth 7:52 Mm-hmm.

Lex Fridman 7:52 ... refer to people, including yourself, who, uh, gravitate toward a kind of computational thinking as geeks. I've he- at least I've heard you use that terminology.

Donald Knuth 8:03 It, it, it's true that I think there's something that happened to me as I was growing up that made my brain, uh, uh-

Lex Fridman 8:10 (laughs)

Donald Knuth 8:10 ... structured in a certain way that, that resonates with, with computers.

Lex Fridman 8:14 So there's this space of people, it's 2% of the population, you empirically estimate.

Donald Knuth 8:19 That, that's a per- per- that's been-

Lex Fridman 8:22 Proven? (laughs)

Donald Knuth 8:22 ... fairly constant over most of my career. However, uh, it might be different now because kids have different experiences when they're young.

Lex Fridman 8:30 So-

Donald Knuth 8:31 I'm just saying. (clears throat)

Lex Fridman 8:31 ... what does the world look like to a geek? What is, what is this aspect-

Donald Knuth 8:38 (clears throat)

Lex Fridman 8:38 ... of thinking that is, uh, unique to, uh-

Donald Knuth 8:42 That makes, they, yeah.

Lex Fridman 8:43 ... that makes a geek?

Donald Knuth 8:45 Th- this is hugely important question. In, in the '50s, IBM noticed that, that, uh, there were geeks and non-geeks and so they tried to hire geeks (laughs) and they, and they put out ads with papers saying, you know, "If you play chess, come to Madison Avenue-"

Lex Fridman 9:04 (laughs)

Donald Knuth 9:04 "... and for an interview," or something like this.

Lex Fridman 9:05 Right.

Donald Knuth 9:06 You know, they were, they were trying for some things. So what did, what, what is it that I find easy (laughs) and other people tend to find harder? And, and I think there's two main things. One is this, uh, (laughs) with, is, uh, ability to, to jump, jump levels of, of, uh, abstraction. Uh, so you see something in the large, uh, and you see something in the small and, and, uh, y- and you pass between those, uh, uh, unconsciously. So you, you, you know that in order to solve a, some big problem, what you need to do is add one to a, uh, in, to a certain register and it, and that gets you to, to another step. And it, and, and, be, and below the... Yeah. I mean, I don't go down to the electron level, but I knew what those milliseconds were, what the drum was like on the 650. I knew how I was gonna factor a number or, or find a root-

Lex Fridman 10:01 Mm-hmm.

Donald Knuth 10:01 ... of an equation or something-

Lex Fridman 10:02 The algorithm.

Donald Knuth 10:02 ... be- because of what was doing. And, and as I'm debugging, I'm going through y- you know, did I make a key punch error? Did I, (laughs) did I, uh, write the wrong instruction? Do I have the wron- wrong thing in the register? And each level, it, e- e- each level it, uh, is different and, uh, so this idea of being able to see something at, at all, at, at lots of levels, uh, and fluently go between them seems to me to be s- more pronounced, much more pronounced in the, i- in the people that resonate with computers like, like I... So in my books, I also don't stick just to the high level but, but-

Lex Fridman 10:42 Yeah.

Donald Knuth 10:43 ... I, but I, I, I mix, uh, low level stuff with high level and this, uh, uh, means that some people think, uh, you know, that, uh, that, uh, I should write better books. Uh, and that's probably true but, but other people say, "Well, but that's, if, if you think like, like that, then that's the way to train yourself, right? To keep mixing the levels and, and learn more and more how to jump between." So that, that's the one thing. The other, the, the other thing is that it's more of a talent, uh, th- uh, it, uh, to be able to deal with, um, uh, non-uniformity where, where, wh- where there's case one, case two, case three, uh, instead of, in- instead of having one or two rules that govern everything. Uh, so, so it, s- so it, it doesn't bother me if I need, uh, uh, like an algorithm ha- has 10 steps to it, you know, each step-

Lex Fridman 11:39 Mm-hmm.

Donald Knuth 11:39 ... is does, does something else, that doesn't bother me. But a lot of, a lot of pure mathematics is based on one or two rules which, which are universal and, and, uh-

Lex Fridman 11:48 Mm-hmm.

Donald Knuth 11:48 ... and so this means that people like me sometimes work with, uh, systems that are more complicated than necessary because it doesn't bother us-

Lex Fridman 11:56 Mm-hmm.

Donald Knuth 11:56 ... as th- that we don't, that we didn't figure out the simple rule.

Lex Fridman 12:00 And you mentioned-

Donald Knuth 12:02 (clears throat)

Lex Fridman 12:02 ... that while Jacobi, Boole, Abel, and all the mathematicians in the 19th century may have had symptoms of geek-... the first 100% legit geek was Turing, Alan Turing?

Donald Knuth 12:15 I, I think he had mo- yeah, a lot more of the ... (laughs) of, of, of this, uh, quality than anybo- uh, uh, just from reading the, the, the kind of stuff he did and ...

Lex Fridman 12:27 So how does, uh, Turing

Lex Fridman 12:30 ... What influence has Turing had on you? What-

Donald Knuth 12:33 Well, okay, so-

Lex Fridman 12:33 ... in your way of thinking?

Donald Knuth 12:34 ... I didn't know that aspect of him until after I graduated some years. Uh, it, as an undergraduate, we had a, a, a, a class that talked about computability theory and Turing machines, and, and it was all ... It, it sounded like a very specific kind of purely theoretical-

Lex Fridman 12:53 Mm-hmm.

Donald Knuth 12:53 ... uh, a- approach to stuff. So when ... How old was I when I li- when I learned that he, that he had a, a, you know, a design machine (laughs) , and that he wrote the ... You, you know, he wro- he wrote a wonderful manual for, for Manchester Machines, and, uh, and he invented all c- uh, you know, s- sub-routines and, and (laughs) , and he was a real hacker, that-

Lex Fridman 13:21 Mm-hmm.

Donald Knuth 13:21 ... that he got, had his hands dirty. The, uh, I, I thought for many years that he had only done p- purely formal work. A- as I started reading his own publications, I could s- I could, you know, I could feel this kinship, um-

Lex Fridman 13:36 Hmm.

Donald Knuth 13:37 ... and, and, of course he had a lot of peculiarities, uh, like he wrote numbers backwards because c- ... I mean, l- left to right instead of right to left, because that's the, that's ... It was easier for computers to process them that way.

Lex Fridman 13:52 What do you mean left to right?

Donald Knuth 13:54 He would write pi (laughs) as, you know, 9514.3.

Lex Fridman 14:01 Oh, wow.

Donald Knuth 14:01 I mean, okay?

Lex Fridman 14:02 Okay. (laughs)

Donald Knuth 14:04 Uh, uh-

Lex Fridman 14:05 Right. Uh, got it.

Donald Knuth 14:07 ... or, or 41.3 or so (laughs) on the blackboard. I mean, when he, he ... (laughs) Like, uh, he, he had trained himself to, uh, uh, to do that because the computers he was working with, uh, uh, worked that way inside.

Lex Fridman 14:21 Trained himself to think like a computer?

Donald Knuth 14:22 Yeah.

Lex Fridman 14:22 Well, there you go. That's-

Donald Knuth 14:23 Mm-hmm.

Lex Fridman 14:23 ... that's geek thinking.

Donald Knuth 14:24 Yeah.

Lex Fridman 14:26 You've practiced some of the most elegant formalism in computer science, and yet you're the creator of a concept like literate programming, which seems to move closer to natural language type of description of programming.

Donald Knuth 14:43 Abs- ... Yeah, absolutely the-

Lex Fridman 14:44 So how do you see those two as conflicting, as the-

Donald Knuth 14:47 Well-

Lex Fridman 14:47 ... formalism of theory, and the idea of literate programming?

Donald Knuth 14:51 So there, there we are in a non-uniform system where I don't-

Lex Fridman 14:54 (laughs)

Donald Knuth 14:54 ... where I don't think one, one size fits all, and I don't, uh, and I don't think a- all truth lies in one, in one kind of expertise. And so s- somehow ... In, in a way you'd say my li- my life is a convex combination of English and mathematics. Uh-

Lex Fridman 15:13 And you're okay with that?

Donald Knuth 15:14 And not only that, I th-

Lex Fridman 15:16 Thrive in it.

Donald Knuth 15:16 I wish ... You know, I want my kids to be that way.

Lex Fridman 15:18 (laughs)

Donald Knuth 15:19 I want them, et cetera, you know?

Lex Fridman 15:20 Yeah.

Donald Knuth 15:20 Not ... Use left brain, right brain at the same time, uh, y- you get a lot more done. That's, that was part of the (laughs) , s- part of the bargain.

Lex Fridman 15:28 And I've heard that you didn't really read for pleasure until into your 30s, and-

Donald Knuth 15:36 Yeah, that-

Lex Fridman 15:36 ... you know, literature.

Donald Knuth 15:37 That's true. You know more about me than I do, but I, I'll-

Lex Fridman 15:39 That's true.

Donald Knuth 15:39 ... try to be consistent with what you read.

Lex Fridman 15:41 Yeah, no, just believe me. I, uh ...

Donald Knuth 15:43 (laughs)

Lex Fridman 15:44 Just go with whatever story I tell you.

Donald Knuth 15:45 (laughs)

Lex Fridman 15:45 It'll be easier that way. The conversation will be easier (laughs) .

Donald Knuth 15:47 Right, yeah, no, that's true. Yep, yep.

Lex Fridman 15:50 So I've heard mention of Philip Roth's American Pastoral, which I, I love as a book. Uh, m- I don't know if ... It was, it was mentioned as something, I think, that was meaningful to you as well. W- uh, i- in either case, what literary books had a lasting impact on you? What literature, what poetry?

Donald Knuth 16:07 Yeah, okay. Good, good question. So I, so I, I, I met Roth, uh, uh-

Lex Fridman 16:12 Oh, really?

Donald Knuth 16:13 ... well, we both got doctorates from Harvard on the same day, so (laughs) -

Lex Fridman 16:17 Okay.

Donald Knuth 16:17 ... so, so we were ... Yeah, we had lunch together and stuff like that, and ... But he knew that, uh, uh, you know, computer books would never sell. Well, well, um-

Lex Fridman 16:26 (laughs)

Donald Knuth 16:27 All right, so you say you, you, uh, you, uh, y- you were a teenager when you left Russia, so-

Lex Fridman 16:33 Mm-hmm.

Donald Knuth 16:35 ... uh, I have to say that Tolstoy was one of the big influences on me. Uh, I, uh, especially like Anna Karenina.

Lex Fridman 16:41 Mm-hmm.

Donald Knuth 16:42 Uh, not because of th- of p- particular of the plot of the story where ... But because, uh, uh, the ch- there's this character who, uh, uh, you know ... The, the philosophical discussions, the-

Lex Fridman 16:56 Mm-hmm.

Donald Knuth 16:57 ... uh, it, it's all ... It's a, it ... A whole way of life is worked out there, it's ... among the characters. And so it ... And so it ... That I thought was, uh, was especially beautiful. On the other hand, Dostoevsky, I, I didn't like at all.

Lex Fridman 17:12 (laughs)

Donald Knuth 17:13 Because I f- I felt that he, his genius was mostly because he kept forgetting what he w- what he had started out to do, and he was just sloppy. I, I, I, I didn't think that, that h- that, that he polished his stuff at all. Uh, and, and I, I tend to admire-

Lex Fridman 17:28 Mm-hmm.

Donald Knuth 17:28 ... somebody who, uh, who dots the Is and crosses the Ts. Um-

Lex Fridman 17:32 So the, the music of the prose is what you admire more than-

Donald Knuth 17:36 Yeah. The ... I certainly do admire the music of the language, which I couldn't appreciate in the Russian original, but, but I can in Victor Hugo, you know, because it's close. French is mu- is closer. But, but Tolstoy, I like. It's the same reason I like Herman Wouk as a, as a novelist. I th- I think, uh, uh, h- he, like, his book Marjorie Morning Star has a similar character in Hugo who developed his own personal philosophy, and expo- and, and it go- goes in, in ...

Lex Fridman 18:08 Was consistent?

Donald Knuth 18:10 Uh, yeah, right.

Lex Fridman 18:10 Yeah.

Donald Knuth 18:11 And it's worth, you know, worth pondering. Uh-... so, uh-

Lex Fridman 18:16 So you don't like Nietzsche and, uh-

Donald Knuth 18:18 Like what?

Lex Fridman 18:18 You don't like Friedrich Nietzsche or-

Donald Knuth 18:20 Nietzsche, yeah. No, no, yeah. Th- this has ne- I, I, I keep seeing quotations from Nietzsche and they never tempt me to read any further.

Lex Fridman 18:29 (laughs) Well, he's full of contradictions, so you will certainly not appreciate him.

Donald Knuth 18:34 Yeah. But Schiller, you know, I'm trying to get, get across what I appreciate in literature.

Lex Fridman 18:39 Mm-hmm.

Donald Knuth 18:40 Uh, and part of it is the, is, is, as you say, the music of the language, uh, the way it flows. Uh, take, uh, Raymond Chandler versus Dashiell Hammett. Dashiell Hammett's sentences, uh, are, are awful, and Raymond Chandler's are, are, are beautiful. They just flow. So I, I don't, uh, I don't read literature because it's, uh, uh, supposed to be good for me or because somebody said it's great, but, but, uh, I, I, I find things that I like. I mean, uh, you mentioned you were dressed like James Bond, so I-

Lex Fridman 19:19 Mm-hmm.

Donald Knuth 19:19 ... you know I love Ian Fleming. I think he's got a, he had a really great gift for if he has a golf game or a game of bridge or something and this comes into a story, it'll, it'll be the most exciting golf game or, or, you know, the absolute best possible hand of bridge that, that exists and, and, uh, and he, he exploits it and tells it beautifully, so.

Lex Fridman 19:45 So in connecting some things here, looking at literate programming and being able to convey, uh, encode algorithms to a computer in a way that mimics how humans speak, uh, how... What, what do you think about natural language in general and the messiness of our human world, about trying to express-

Donald Knuth 20:13 Yeah.

Lex Fridman 20:13 ... difficult things?

Donald Knuth 20:15 So the idea of literate programming is to, is really to try to, uh, understand something better by seeing it from at least two perspectives, the formal and the informal. If we're trying to understand a complicated thing, if we can look at it in different ways. And so this, this is, in fact, the key to technical writing. Um-

Lex Fridman 20:38 Mm-hmm.

Donald Knuth 20:38 ... a, a good technical writer, trying not to be obvious about it, but says everything twice, uh, (laughs) formally and informally, or, or maybe three times. But you try to give, uh, the, uh, the reader, um, a way to put the concept into his own brain or her own brain.

Lex Fridman 20:57 Is that better for the writer or the reader or both?

Donald Knuth 21:01 Well, the writer just tries to understand the reader. That's the goal of a writer, is to, is, is to have a good mental image of the reader and to, to say what the reader expects next and to, to impress the reader with what has impressed the writer, (laughs) why something is interesting. So, so when you have a computer program, we try to, uh, instead of looking at it as something that we're just trying to give an instruction to the computer, what we really want to be is giving, giving insight to the person who's, who's, uh, uh, gonna be maintaining this program or, or to the programmer himself when he's debugging it, as to why this stuff is being done. And so all the techniques of exposition that, that a teacher uses or a book writer uses make you a better programmer if your, if your program is gonna be, uh, not just a one-shot deal.

Lex Fridman 22:01 So how difficult is that? Do you see hope for the combination of informal and formal for the programming task?

Donald Knuth 22:12 Yeah. I, I'm the wrong person to ask, I guess-

Lex Fridman 22:16 Uh-huh.

Donald Knuth 22:16 ... because I'm a geek. But, but I think for a geek, it's easy. No... (laughs) Well, I don't know. Some, not... Some people have difficulty writing, and that might be because there's something in their brain structure that makes it hard for them to write, or, uh, or it might be something just that they haven't had enough practice. I'm not the right one to, to, uh, to judge, but I don't think you can teach any person any particular skill. I, I do think that, that writing is, is half of my life, and so I, I put it together in literate programming. Even when I'm writing a one-shot program, I, I write it, uh, uh, in a literate way, uh, because I, I get it right faster that way.

Lex Fridman 23:04 Now, does it get compiled automatically or-

Donald Knuth 23:07 Right.

Lex Fridman 23:08 So I guess on the technical side, my question was, how difficult is, is it to design a system where much of the programming is done informally?

Donald Knuth 23:19 Informally?

Lex Fridman 23:20 Yeah, informally.

Donald Knuth 23:22 I think, uh, whatever works to make it understandable is good. Uh, but then you have to also understand, uh, how informal it is. You have to know the limitations. You have to-

Lex Fridman 23:35 Right.

Donald Knuth 23:35 ... you, you...

Lex Fridman 23:35 Yeah.

Donald Knuth 23:36 So, so by putting the formal and informal together, this, this is where, this is where it gets locked into your, into your brain. You can, you, you can say informally, uh, "Well, I'm working on a problem right now, so I..."

Lex Fridman 23:52 Let's go there. Do... Yeah. Can you give me an example of, um-

Donald Knuth 23:57 Yeah.

Lex Fridman 23:57 ... of connecting the informal and the formal?

Donald Knuth 24:00 Well, (laughs) it's a little too complicated an example. There, there, there's a puzzle that's self-referential. It's called a Japanese arrow puzzle. And, uh, and, and you're given a, a bunch of boxes. Each one points north, east, south, or west. And at the end, you're supposed to fill in each box with the number of...... distinct numbers that it points to.

Lex Fridman 24:24 Mm-hmm.

Donald Knuth 24:25 So, if I put a three in a box, that means that, and, and it's pointing to five other boxes, that means that there's going to be three different numbers in those five boxes.

Lex Fridman 24:33 Mm-hmm.

Donald Knuth 24:34 And, uh, and those boxes are pointing, uh, one might be pointing to me, one of them might be pointing the other dir- the other way. But anyway, I, it, yeah, I, I'm supposed to find this set of numbers that obeys this, this complicated con- condition that each number counts how many distinct numbers, uh, it, it points to. Well, um, and, uh, so a guy sent me his solution to this problem, where he, uh, where he, um, uh, uh, presents formal statements that, that, that say either this is true or this is true or this is true.

Lex Fridman 25:08 Mm-hmm.

Donald Knuth 25:08 And, and, and so I try to render that formal statement informally, and I try to say, "I contain a three and, and, uh, uh, the guys I'm pointing to, uh, contain the numbers one, two, and six."

Lex Fridman 25:24 Mm-hmm.

Donald Knuth 25:25 So, by putting it informally and also I converted into a, into a dialogue statement, um, uh, that helps me understand the logical statement that he's written down as a string of numbers in terms of s- some abstract variables that he had.

Lex Fridman 25:41 That's really interesting.

Lex Fridman 25:42 So, maybe an extension of that, there has been a resurgence in computer science and machine learning and, uh, neural networks.

Donald Knuth 25:52 Yeah.

Lex Fridman 25:52 So, using data to construct algorithms, so it's another way to construct algorithms, really.

Donald Knuth 25:59 Yes, exactly.

Lex Fridman 25:59 If you can think of it that way.

Donald Knuth 26:01 Yeah, yeah.

Lex Fridman 26:02 Uh, uh, so as opposed to natural language to construct algorithms, you use data to construct algorithms. So, what, uh, what's your view of this branch of computer science, uh, where data is almost more important than the, uh, mechanism of the algorithm?

Donald Knuth 26:18 It seems to be, um, suited to a certain kind of non-geek, uh (laughs) -

Lex Fridman 26:24 (laughs) Sure, sure.

Donald Knuth 26:24 ... and which, which is probably why it's, it's, uh, uh, it's taken off. The... It has its own community-

Lex Fridman 26:30 Got you.

Donald Knuth 26:31 ... that, that really, that really resonates with that. But, um, it's hard to, you know, to trust something like that because nobody, e- e- even the people who, who work with it, that they have no idea what has, what has been learned.

Lex Fridman 26:47 That's a really interesting thought that it's, uh, it makes algorithms more accessible to a different community, a different type of brain.

Donald Knuth 26:58 Yep.

Lex Fridman 26:59 And that's really interesting because, uh, just like literal programming, perhaps could make programming more accessible to a certain kind of brain.

Donald Knuth 27:10 There are people who think it's just a matter of education, uh, and any- anybody can learn to be a great programmer, anybody can learn to be a great, uh, uh, uh, skier, um-

Lex Fridman 27:21 (laughs)

Donald Knuth 27:22 ... uh, you know. I, I, I wish that were true, but I, but I know that there's a lot of things that I've tried to do and I, and, uh, like, I was well-motivated and I kept trying to build myself up and I never got past a certain level. Uh, I, I can't view, for example, I can't view, uh, uh, three dimensional objects in my, in my head. I have to, I have to make a model and look at it and study it from all points of view, and then I start to get some idea of... But other people are good at four dimensions. I mean... (laughs)

Lex Fridman 27:54 Physicists. (laughs)

Donald Knuth 27:55 Yeah.

Lex Fridman 27:58 So,

Lex Fridman 27:59 let's go to, uh, The Art of Computer Programming. In 1962, you set the table of contents for this, uh, magnum opus, right?

Donald Knuth 28:13 Yep.

Lex Fridman 28:13 It was supposed to be a single book with 12 chapters. Now, today, what is it? F- f- fifty, uh, seven years later-

Donald Knuth 28:22 (laughs)

Lex Fridman 28:22 ... you're in the middle of volume four of seven, uh-

Donald Knuth 28:26 In the middle of volume 4B is-

Lex Fridman 28:28 4B.

Donald Knuth 28:29 ... more precisely.

Lex Fridman 28:30 Can I ask you for an impossible task? Which is try to summarize the book so far, maybe by giving a, a little examples. So, from the sorting and the search and the combinatorial algorithms, if you were to give a summary, a quick elevator summary.

Donald Knuth 28:50 (laughs) Elevator, that's great.

Lex Fridman 28:51 (laughs)

Donald Knuth 28:52 Yeah, right.

Lex Fridman 28:52 Well, depending how many floors there are in the building, of course.

Donald Knuth 28:54 Yeah. The first volume called Fundamental Algorithms talks about s- something that you can't... the stuff you can't do without. Uh, you have to, you have to know s- some basic concepts of, of what is a program, what is an algorithm. And, uh, and, and it also talks about a low-level machine so you can have some, some kind of an idea wh- what's going on. And it has basic concepts of input/output and, uh, sub-routines.

Lex Fridman 29:26 Induction.

Donald Knuth 29:28 Induction, right. It's a mathematical preliminary. So, so the thing that makes my book different from, uh, a lot of others is that I'll, that I try to not only present the algorithm, but I try to analyze them, and which means to... Quantitatively, I say not only does it work but it works this fast.

Lex Fridman 29:46 Mm-hmm.

Donald Knuth 29:47 Okay. And so I need math for that. And then there's, uh, the standard way to structure data inside and represent-

Lex Fridman 29:53 Mm-hmm.

Donald Knuth 29:54 ... information in the computer. So, that's all volume one. Uh, vol- volume two talks, it's called Semi-Numerical Algorithms, and here we're, here we're, we're, we're writing programs but we're also de- dealing with numbers. The algorithms deal with, with any kinds of objects, but, but specific... When those objects are numbers, well then, then we have certain...... special paradigms that, that apply to things that have, involve numbers. And so there's, there's, there's, there's arithmetic on numbers and, and there's matrices full of numbers, there's random numbers, and there's power series full of numbers. There's different, um, algebraic concepts that have numbers in structured ways.

Lex Fridman 30:37 And arithmetic in the way a computer would think about arithmetic, so floating point-

Donald Knuth 30:41 Floating point arithmetic, high precision arithmetic. Not only addition, subtraction, multiplication, but also comparison of numbers. So then ch- then volume three talks about-

Lex Fridman 30:53 I like that one, sort and search.

Donald Knuth 30:55 Sorting and searching. Yeah.

Lex Fridman 30:56 I love sorting.

Donald Knuth 30:57 Right. So s- so here, you, you, you know, we're not dealing necessarily with numbers because you s- you sort letters and other objects, and searching we're doing all the time with Google nowadays, but I mean, then you, we have to find stuff. Uh, so, uh, again, algorithms that, that underlie, uh, all kind of applications, uh, you know, n- none of these volumes is about a particular application, but the applications are examples of, uh, of why people want to know about sorting, why people want to know about random number. So then volume four goes into combinatorial, uh, algorithm. This is where we have, uh, zillions of things to deal with and we... and, uh, here we keep finding, uh, cases where one good idea can s- can make something go more than a million times faster.

Lex Fridman 31:45 Mm-hmm.

Donald Knuth 31:46 And, and, uh, and we're dealing with problems that are probably never gonna be solved efficiently, but that doesn't mean we give up on 'em, uh, and, and, and we have this chance to have good ideas and, and go much, much faster on 'em. So, so that's combinatorial algorithms, and those are the ones that are... yeah, I mean, you say f- sorting is most fun for you. Well, it's, it-

Lex Fridman 32:09 Well, like, it's a s-

Donald Knuth 32:10 It's true-

Lex Fridman 32:10 ... satisfiability too.

Donald Knuth 32:11 ... it's fun, but combinatorial algorithms are the ones that I always, that I always, uh, enjoyed the most because that's when my skillet programming had the most payoff.

Lex Fridman 32:22 Ah.

Donald Knuth 32:23 You know, that was, uh, the, the different... the difference between an obvious algorithm that you think of first thing and a, and a, you know, and a, and a, and a good... an, an, an interesting subtle al- algorithm that not so obvious but, but, uh, runs circles around the other one, that's, uh, that, that's where computer science really comes, uh, work comes in. And, and a lot of these, uh, combinatorial methods, uh, were found first in applications to artificial intelligence or cryptography, and, um, in my case, uh, I, I just liked them and it was associated more, more with puzzles.

Lex Fridman 33:01 Uh, do you like the most of the domain of graphs and graph theory?

Donald Knuth 33:05 Graphs are great because they're, they're, they're, they're terrific models of so many things in the real world-

Lex Fridman 33:10 Right.

Donald Knuth 33:10 ... and, and, and, and you, you throw numbers on a graph and you got a network and so there you... the- there you have m- m- many more things. So... but combinatorial, in general, is an- any, uh, arrangement of objects that, that, uh, that has some kind of a higher structure, n- non-, non-random structure. And it's okay. I- is it possible to c- uh, to put something together satisfying all these conditions? Like I, I mentioned arrows a minute ago. You know, is there a way to, to, to put these numbers on a bunch of boxes that, that are pointing to each other? Is that gonna be possible at all? And-

Lex Fridman 33:48 That's volume four.

Donald Knuth 33:50 That's volume four. Uh-

Lex Fridman 33:52 What does the future hold?

Donald Knuth 33:53 ... they say volume 4A was part one and, and, uh, what happened was in 1962 when I started writing down a table of contents, it wasn't gonna be a book about computer programming in general, it was gonna be a book about how to write compilers.

Lex Fridman 34:10 Mm-hmm.

Donald Knuth 34:10 And I was asked to write a, a, a, a book, uh, explaining how to, how to write a compiler and, uh, at that time, the- there were, uh, only a few dozen people in the world who had written compilers (laughs) and I happened to be one of them so... and, and I also had some experience writing for, like, n- n- the c- the campus newspaper and things like that, so, so I said, "Okay, great. Uh, I'm the only person I know who, who has written a compiler but hasn't invented any new techniques for writing compilers." And, and all the other people I knew had, uh, super ideas but I couldn't see that they would r- be able to write a, a book that wouldn't... that would describe anybody else's ideas but their own. So I could be the, I could be the journalist and I could explain what all these cool ideas about compiler writing were. And, uh, and, and then I, I started putting down, "Well, yeah, let me... you need to have a chapter about data structures, you need to ha- have some introductory material." You... I wanted to talk about searching 'cause a compiler writer has to, has to, uh, l- l- look up, uh, uh, the, the variables in a symbol table and find out, uh, ge- you know, which, which, uh, uh, wh- when, wh- when you, when you write the name of a variable in one place it's supposed to (laughs) be the same as the one you put somewhere else. So-

Lex Fridman 35:33 Right.

Donald Knuth 35:33 ... so you need all these basic techniques and I, and I, uh, you know, ki- kind of know some arithmetic and stuff. So I, so I threw in these chapters and I threw in a chapter on combinatorics because, uh, th- that was what I really enjoyed pr- programming the most but there weren't many algorithms in... known about combinatorial methods in 1962. Uh, so that was a kind of a short chapter, but it was s- sort of thrown in just for fun. And chapter 12 was gonna be actual compilers, applying all the stuff in chapters 1 to 11, uh, to make compilers. Well, okay, so that was my table of contents from 1962, and during the '70s, the whole field of combinatorics we- went through a huge explosion.... people talk about com- combinatorial explosion, and they usually mean by that-

Lex Fridman 36:21 (laughs)

Donald Knuth 36:22 ... that, uh, the number of cases goes up, you know, n, n+1 and all of a sudden you, your problem has, has gotten more than 10 times harder. But, e- e- e- there was a, an explosion of ideas about combinatorics in the '70s, to, to the point that it, like take 1975, I, I betcha more than half of all the journals of computer science w- were about combinatorial methods.

Donald Knuth 36:49 And s-

Lex Fridman 36:49 What kind of problems were occupying people's minds? What ki- kind of problems in combinatorics? Was it s- sat-

Donald Knuth 36:56 Graph theory.

Lex Fridman 36:56 ... satisfiability? Graph theory?

Donald Knuth 36:57 Y- y- y- yeah. Graph theory was, was quite dominant. I mean... But, uh, uh, all of the MP hard problems, uh, that you have like, ha- you know, Hamiltonian path, or-

Lex Fridman 37:08 Travel salesman.

Donald Knuth 37:09 G- g- going beyond, yeah, yeah, going beyond graphs you had, you had operation research, uh, whenever there was a small class of problems that had efficient solutions, and they were usually associated with matroid theory, a special mathematical construction. But once we went, uh, to things that involved three things at a time instead of, instead of two, all of a sudden things got harder, so we had satisfiability problems where if, if, if you have, if you have clauses, e- every clause has two logical elements in it then we can satisfy it in linear time. We can test for satisfiability in linear time, but if you allow yourself three variables in the clause, uh, then, uh, uh, nobody knows how to do it. So, these articles were about trying to find better a- better ways to, uh, to solve cryptography problems and graph theory problems, whereas we have lots of data but we didn't know how to find the best subsets of the data like with sorting it, uh, w- we could get the answer, i- it didn't take long.

Lex Fridman 38:13 So how did it continue to change from the '70s to today?

Donald Knuth 38:16 Yeah, so now there are maybe half a dozen conferences whose topic is combinatorics, different kind, but fortunately I don't have to rewrite my book every month, you know, like I had to in, in the '70s. But still there's huge amount of work being done on it and people getting better ideas on these problems that don't seem to have really efficient solutions, but we still get, do a lot more with them. And so this book that I'm finishing now is, I've got a br- a whole bunch of brand new methods that, uh, as far as I know there's no other, there's no other book that covers (laughs) , that covers this particular approach, and, and, uh, so I'm trying to do my best of, uh, exploring the tip of the iceberg, uh, and, and I, I try out lots of things and, and keep, keep rewriting, uh, finding, as I find better, better method.

Lex Fridman 39:16 So what's your writing process like? What's your thinking and writing process like every day?

Donald Knuth 39:23 So, um-

Lex Fridman 39:24 What's your routine even?

Donald Knuth 39:25 My... yeah, I guess it's actually a the best question because I spend seven days a week-

Lex Fridman 39:32 (laughs)

Donald Knuth 39:33 ... (laughs) doing it. Uh-

Lex Fridman 39:34 You're the most prepared to answer it. Yeah.

Donald Knuth 39:36 Uh, yeah. But, um, okay, so, uh, uh, the chair I'm sitting in is where I do... (laughs)

Lex Fridman 39:45 It's where the magic happens? (laughs)

Donald Knuth 39:46 Well, uh, re- reading and writing, my chair is usually sitting over there where I have other books or some reference books but, but, uh, I found this chair, uh, which was designed by a Swedish guy anyway, it turns out this is the only chair I can really sit in for hours and hours and not know that I'm in a chair. But then I have this standup desk right next, next to us, and, and so after I write something with pencil and eraser, I get up and I type it, and revise, and rewrite, uh, uh...

Lex Fridman 40:20 But...

Donald Knuth 40:20 Uh, I'm standing up.

Lex Fridman 40:21 The kernel of the idea is first put on paper.

Donald Knuth 40:24 Yep.

Lex Fridman 40:25 That's where...

Donald Knuth 40:25 Right. A- and I'll write maybe five programs a week, uh, o- of course literate programming. And, uh, th- these are, before I describe something in my book I always program it to see how it's working and I, and I try it a lot. So for example, I learned, uh, at the end of January, I learned of a breakthrough by four Japanese people who had extended one of the, one of my methods in a, in a new direction, and so I, I spent the next five days writing a program to implement what they did and then I, you know, but they had only generalized part of what I had done, so then I had to see if I could generalize more parts of it, and then I, then I had to take their approach and I had to, I had to try it out on a couple of dozen of the other problems I had already worked out with my, with my old methods, and so that took another couple of weeks, and then I, you know, then I started to see the light, and I, and, uh, and- and I started writing the, th- the final draft, and, uh, and then I would, uh, type it up, involve some new mathematical questions, and so I wrote to my friends and s- who might be good at solving those pr- problems and, and, uh, they solved some of them, and so I put that in as exercises and... And so a month later, I had absorbed one new idea that I've, that I learned and, uh, you know, I'm glad I heard about it in time, otherwise my, I would have put my book out before I'd heard about the idea. On the other hand this book was supposed to come in at 300 pages and I'm up to 350 now. That added 10 pages to the book, but if I learn about another one, uh, my, my publisher is going

Donald Knuth 42:10 to shoot me.

Lex Fridman 42:10 (laughs) Well, so in the process, in that one month process, are some days harder than others?

Donald Knuth 42:19 Are some days harder than others? Well, th- yeah. My work is fun but I also work hard and every big-... job has parts that are a lot more fun than others. And so, uh, uh, many days I'll say, "Why do I have to have such high standards? What, what, uh, why, why couldn't I just be sloppy and not try this out and, and, you know, just, just report the answer?" But I, but I know that, um, uh, that people are counting on me to do this. And so they're, "Oh, okay. So, okay, Don, I'll grit my teeth and do it." And, and, and then the joy comes out when I see that actually, uh, you know, I'm getting good results. And, and, and I get ... a- and I, even more when I see that somebody has actually read and understood what I wrote, and, uh, told me how to make it even better. I did want to mention, uh, something about the, um, about the method. So I got this tablet here, where ...

Lex Fridman 43:16 Wow.

Donald Knuth 43:17 ... where, where I do the first, y- y- you know, the first writing, uh, of, of concepts. Okay? So, so, um-

Lex Fridman 43:25 And what language is that then? (laughs)

Donald Knuth 43:27 It, it's like ... right. So here you can take a look at it. But, you know, here, r- and I'm saying, "Explain how to draw such skewed pixel diagrams." Okay. (laughs) . So I got this paper-

Lex Fridman 43:37 Mm-hmm.

Donald Knuth 43:38 ... about 40 years ago, when I was, uh, visiting my sister in Canada. And th- they make tablets of paper with this, with this nice large size and just the right stuff.

Lex Fridman 43:47 And a very small space between lines.

Donald Knuth 43:49 Small spaces, yeah, yeah. Take a look.

Lex Fridman 43:51 Do you mind if I maybe, uh, also just show it? (laughs) .

Donald Knuth 43:54 Yeah. Sure.

Lex Fridman 43:56 Yeah. Wow.

Donald Knuth 43:59 S- you know, I've got these manuscripts going back to the '60s.

Lex Fridman 44:01 Get you out of ... yeah, yeah.

Donald Knuth 44:02 (laughs) . And, and, and th- those are when I'm getting my ideas on paper, okay? But I'm a good typist. In fact, I went to typing school when I was at, uh, when I was in high school.

Lex Fridman 44:14 Okay.

Donald Knuth 44:14 And so I can type faster than I think. So then when I do the, the editing and, you know, stand up and type, then I, then I revise this, and, and it comes out a lot different than what, you know, for, for style and rhythm and things like that come, come out at the, at the typing stage.

Lex Fridman 44:31 And you type in tech?

Donald Knuth 44:32 And I type in tech, yeah.

Lex Fridman 44:34 And can you s- can you think in tech?

Donald Knuth 44:37 No.

Lex Fridman 44:38 So-

Donald Knuth 44:38 To a certain extent I have, I have only a small number of, of idioms that I use. Like I, you know, beginning a theorem, I do something for e- ... displayed equation I do something, and, and so on. But I, but I, I have to see it. And-

Lex Fridman 44:53 In the way that it's on paper here?

Donald Knuth 44:55 ... it's ... yeah, right. And-

Lex Fridman 44:55 So for example, Turing wrote, what, The Other Direction.

Donald Knuth 44:59 Mm-hmm.

Lex Fridman 44:59 You don't write, uh, macros ...

Donald Knuth 45:02 Uh-

Lex Fridman 45:02 You don't think in macros?

Donald Knuth 45:04 Not particularly. But when I need a macro, I'll, uh, uh, I'll go ahead and-

Lex Fridman 45:08 Use it.

Donald Knuth 45:08 ... and do it. But, but the, but the thing is that I also write to fit. I mean, I'll, I'll change something if I can, if I can save a line.

Lex Fridman 45:17 Mm-hmm.

Donald Knuth 45:17 I'll ... you know, it's like haiku. I'll figure out a way to rewrite the sentence so that, uh, it'll look better on the page.

Lex Fridman 45:24 Mm-hmm.

Donald Knuth 45:25 And, uh, I shouldn't be wasting my time on that. But, uh, but I can't resist because I know, uh, it's, it's only another 3% of the time, or something like that, s-

Lex Fridman 45:33 And it could also be argued that that is what life is about.

Donald Knuth 45:39 Ah, yes. The ... in fact, that's true. Uh, uh, (laughs) like, like I, I work in a garden one day a week, and that's, that's kind of a description of my life, is getting rid of weeds, you know, r- r- removing bugs from programs and ...

Lex Fridman 45:52 So, you know, a lot of writers talk about, you know, basically suffering. The writing process is-

Donald Knuth 45:58 Yeah.

Lex Fridman 45:59 ... having s- you know, it's extremely difficult. And I think of programming, especially the, or technical writing that you're doing can be like that. Do you find yourself ... methodologically, how do you every day sit down to do the work? Is it a challenge?

Donald Knuth 46:18 T-

Lex Fridman 46:18 You, you kind of say it's, you know-

Donald Knuth 46:21 Oh, yeah.

Lex Fridman 46:21 ... it's fun, (laughs) but it'd be interesting to hear if-

Donald Knuth 46:27 Well, yeah, that's true.

Lex Fridman 46:27 ... if there are non-fun parts that you really struggle with.

Donald Knuth 46:31 Yeah. So the f- the fun comes when, when I'm able to p- put together ideas of two diff- two people who didn't k- know about each other. And, and so I, I might be the first person that saw both of their ideas and s- and so then, uh, you, you know, then, then I get to make the synthesis. And that g- gives me a chance to, to be creative. The, but the drudge work, uh, is where I ha- I've got to chase everything down to its root. This leads me in, into really interesting stuff. I mean, I, I, I learn about Sanskrit and I (laughs) -

Lex Fridman 47:03 Yeah.

Donald Knuth 47:03 ... and, and, you know, I try to give credit to all the authors. And so I write le- uh, so I write the people who, who, who know the, the people, authors. If they're dead, I, I co- I communicate this way. I ... and, uh, I got to get the math right. And I got to check all my programs, try to find h- holes in them. And I rewrite the programs over ... after I get a better idea.

Lex Fridman 47:26 Is there ever dead ends?

Donald Knuth 47:28 Dead ends? Oh, yeah. I, I throw stuff out. Yeah. One of the things that I ... I spent a lot of time preparing a major example based on the game of baseball. And I know a lot of people who, (laughs) for whom baseball is the most important thing in the world, you know.

Lex Fridman 47:46 Yes.

Donald Knuth 47:46 But it's ... but I also know a lot of people for whom cricket is the most important in the world, or, or, or, or soccer, or something, you know.

Lex Fridman 47:53 Okay, yeah.

Donald Knuth 47:53 Uh, uh, and, and I realized that if, if I had a big example ... I mean, it was going to have a foldout illustration and everything. And I was saying, "Well, what, what am I really teaching about algorithms here where I had this, this, this, this baseball example?" And if I was a person who, who kn- who knew only cricket, wouldn't they ... w- what would they think about this? And, and so, so I ripped the whole thing out. But I had, you know, I had, I, I had a s- something that would have really appealed to people who grew up with baseball as, as, as a, as a major theme in their life.

Lex Fridman 48:24 Which is a lot of people, but-

Donald Knuth 48:26 But just ... yeah. So-

Lex Fridman 48:27 ... but still a minority.

Donald Knuth 48:29 Small minority. I took out bowling, too. Uh. (laughs)

Lex Fridman 48:33 (laughs) Even a smaller minority.

Donald Knuth 48:35 (laughs)

Lex Fridman 48:35 (laughs)

Lex Fridman 48:36 ... what's the art in, uh, The Art of Programming? Why, why is there... Of the few words in the title, why is art one of them?

Donald Knuth 48:46 Yeah. Well, that's, that's what I wrote my Turing lecture about. And, uh, and so when people talk about art, it, it really... I mean, hi- what the word means is som- something that's not in nature. So, so when you have artificial intelligence, the, the art comes from the same root, saying that this is something that was created by, by human beings. And then it's gotten a, a further meaning, uh, often of fine art, which, which adds this beauty to the, to the mix and says, you know, we have things that are artistically done, and, and this means, uh, not only done by humans but also done in a way that's elegant and, uh, brings joy and, and has, has, uh, um, I, I guess what... Tolstoy versus Dostoevsky, uh, uh-

Lex Fridman 49:42 (laughs) Right.

Donald Knuth 49:43 ... going b- Um, but anyway, it, it, it's that part that, that says that it's done well as well as not only, uh, uh, different from nature. In general then, um, uh, art, uh, is what human beings are specifically good at. And when they say, "Art- artificial intelligence," well, they're trying to mimic human beings.

Lex Fridman 50:07 But there's an element-

Donald Knuth 50:08 (laughs)

Lex Fridman 50:09 ... of fine art and beauty. You are one who-

Donald Knuth 50:11 That's what I, that's what I've tried to also say, that you can write a pro- a program and make a work of art. Mm-hmm.

Lex Fridman 50:20 So,

Lex Fridman 50:21 now in terms of surprising, you know, what ideas in, in writing from sort- in search to the common tutorial algorithms, what ideas have you come across that, um, were particularly surprising to you?

Donald Knuth 50:42 Okay. All right.

Lex Fridman 50:42 That, that changed the way you see a space of problems?

Donald Knuth 50:47 Yeah. Okay. I get a surprise every time I have a bug in my program obviously.

Lex Fridman 50:51 (laughs)

Donald Knuth 50:51 But that, but, but that isn't really what you're... Uh, y- y- you're looking for the-

Lex Fridman 50:54 More transformational than less-

Donald Knuth 50:56 Right. So-

Lex Fridman 50:56 ... than surprising.

Donald Knuth 50:57 So, for example, in volume 4A, I was especially surprised when I learned about data structure called BD- BDD, b- Boolean decision diagram. Uh, because I sort of had the feeling that, uh, as an old-timer, uh, and, you know, I'd been programming since the s- or since the '50s, and, uh, BDDs weren't invented till 1986. And here comes a brand new idea that revolutionizes the way to represent a Boolean function. And Boolean functions are so basic to all kinds of things in... Uh, uh, uh, it mean- logic is (laughs) underlies e- e- e- e- everything we can describe, all of what we know in terms of logic somehow, and, and here... And, and, uh, it... Propositional logic, uh, I thought, uh, that was cut and dried and everything was known, but, but, uh, but here, but here comes, uh, uh, uh, Randy Bryant and, uh, and discovers that BDDs are, are incredibly powerful. Then, then the... Uh, so I, so I, uh, that mean- means I have a whole, whole new section-

Lex Fridman 52:12 Mm-hmm.

Donald Knuth 52:12 ... to the book that I never would have thought of until 1986, and not even until 1990s when I, when, when people started to, uh, uh, to use it for, for, uh, uh, you know, b- billion dollar of applications. Uh, and, and it was, it was the standard way to design computers for a long time until, un- (laughs) until SAT solvers came along when, in the year 2000. So, so that's another great big surprise. So, uh, a lot of these things have re- have totally changed the structure of my book. And the, the middle third of volume 4B is g- is about SAT solvers, and that's 300 plus pages, which is, uh, uh, which is all about mater- uh, mostly about material that was discovered in this century.

Lex Fridman 52:58 Mm-hmm.

Donald Knuth 52:58 Um, and I had to, uh, start from scratch and, you know, meet all the people in the field and write... I have 15 different SAT solvers that I wrote w- uh, while preparing that, and s- seven of them are described in the book. Um, others were from my own experience and...

Lex Fridman 53:16 So, newly invented data structures or ways to represent...

Donald Knuth 53:20 Uh, a wh- a whole new class of algorithm.

Lex Fridman 53:22 A whole new class of algorithm?

Donald Knuth 53:23 Yeah. And, and the interesting thing about the BDDs was that, uh, the theoreticians started looking at it and, and, and started to describe all the things you couldn't do with BDDs, and so they were getting a bad, they, they were getting a bad name, uh, uh, because, you know, okay, they were, they, they were useful but they didn't solve every, every problem, you know.

Lex Fridman 53:48 (laughs)

Donald Knuth 53:48 I'm, I'm sure that the theoreticians are... In the next 10 years are gonna show why machine learning doesn't solve everything.

Lex Fridman 53:56 Right.

Donald Knuth 53:56 But I, you know, not only worried about the worst case, I get a huge delight when I can actually solve a, a, a problem that I couldn't solve before, you know.

Lex Fridman 54:05 Yeah.

Donald Knuth 54:05 Even though I can't solve the problem that's, that is suggested as a further problem, like, uh, I, I, I, I know that I'm way better than I was before. And so I found out that BDDs could do all kinds of miraculous things, um, and so, uh, uh, uh, I, uh, had, had to spend quite a few years, uh, uh, learning, uh, ab- about the, that territory.

Lex Fridman 54:31 So, in general, what brings you more pleasure, uh, proving or showing a worst-case analysis of an algorithm, or-... showing a good average case, or just showing a good case, that you know something good pragmatically can be done with this algorithm.

Donald Knuth 54:49 Yeah, I like a good case that, that is maybe only a million times faster than I was able to do before but the, uh, and not worry about the fact that, uh, uh, that it's still g- that it's still gonna take too long if I double the size of the problem. (clears throat)

Lex Fridman 55:05 So

Lex Fridman 55:06 that said, you popularized the asymptotic notation for describing running time. Obviously in the analysis of algorithms, worst case is such a, such an important part. Do you see any aspects of, uh, that kind of analysis as lacking?

Donald Knuth 55:24 S-

Lex Fridman 55:24 And notation too.

Donald Knuth 55:26 Well, well the, the main per- purpose that we should have notations that, that help us, uh, for the problems that we want to solve and so that-

Lex Fridman 55:33 Right.

Donald Knuth 55:33 ... they match our, they, they match our intuitions. And, uh, people who worked in number theory had used, uh, asymptotic notation in what, in a, in a certain way, but it was only known to a small group of people. And, and I realized that, in fact, it was very useful to be able to have a notation for something that we don't know exactly what it is, but we only know p- partial about it. And so instead ... so, uh, for example, instead of Big O notation, let's just-

Lex Fridman 56:02 Mm-hmm.

Donald Knuth 56:03 ... let's just take a s- a much simpler notation where I say, zero or one, um, or, or, or zero, one or two. And suppose I, suppose that, that, uh, when I had been in high school, we would b- be allowed to put in the middle of our formula X plus zero, one or two (laughs) -

Lex Fridman 56:20 Mm-hmm.

Donald Knuth 56:20 ... equals, uh, Y, okay? And, and, and then, then we, we would learn how to multiply two such expressions together and then, you know, uh, uh, deal with them. Uh, well the same thing Big O notation says, uh, here is something that's, uh, I, I'm not sure what it is but I know it's not too big. I, I know it's not bigger than some constant times N squared or something like that.

Lex Fridman 56:45 Right.

Donald Knuth 56:45 And so, so I write Big O of N squared. And now I, I learn how to add Big O of N squared to Big O of N cubed, and I know how to add Big O of N squared to, uh, plus one and square that, and how to take logarithms and exponentials who have Big Os in the middle of them. And that turned out to be, uh, hugely valuable in, in all of the work that I was trying to do as I'm trying to figure out how good an algorithm is.

Lex Fridman 57:09 So, have there been algorithms in your journey that perform very differently in practice than they do in theory?

Donald Knuth 57:18 Well, the worst case of a combinatorial algorithm is almost always, uh, horrible.

Lex Fridman 57:24 (laughs) .

Donald Knuth 57:24 Uh, but, but, but, but we have SAT solvers that are solving ... where one of the, one of the last exercises in that pa- part of my book was to f- figure out a, a problem that has 100 variables that's, that's difficult for a SAT solver.

Lex Fridman 57:40 Mm-hmm.

Donald Knuth 57:41 But, uh, but you would think that, uh, a problem with 100 Boolean variables has, uh, requires you to do two to the 100th, uh, uh, uh, operations, because that's the number of possibilities when you have two, 100 Boolean variables, and two to the 100th, two, two to the 100th is way bigger than, than we can handle. 10 to the 17th is a lot.

Lex Fridman 58:03 You've mentioned over the past few years that you believe P may be equal to NP, but that it's not really, uh, you know, if somebody does prove that P equals NP, it will not directly lead to an actual algorithm to solve difficult problems.

Donald Knuth 58:19 Right.

Lex Fridman 58:19 Uh, can you explain your intuition here? Has it been changed? And in general on the difference-

Donald Knuth 58:25 Yeah.

Lex Fridman 58:25 ... between easy and difficult problems of P and NP and so on.

Donald Knuth 58:28 Yeah, so, so the, the popular idea is if an algorithm exists then s- somebody will find it, um, and it's just a matter of, of, uh, of writing it down when, wh- wh- uh, uh, but many more e- algorithms exist (laughs) than anybody can under- understand or, or ever make use of.

Lex Fridman 58:51 Or discover, yeah.

Donald Knuth 58:52 Uh, be- because they're just way beyond human comprehension. The, the, the total number of algorithms is, uh, i- is, is more than mind-boggling.

Lex Fridman 59:02 Mm-hmm.

Donald Knuth 59:03 Um, so, so we have situations now where we know that algorithms exist but we don't know w- we don't have the foggiest idea what the al- algorithms are. There are s- there are simple examp- examples based on, on game playing where you have, uh, uh, w- where you say, "Well, there must be an algorithm that exists to win in the game of Hex because, uh, for the first player to win in the game of Hex," because Hex is always either an out, uh, a win for the first player or the second player.

Lex Fridman 59:35 Wait, what's the game of Hex?

Donald Knuth 59:36 There's a game of Hex which is, which based on putting pebbles onto a hex- hexagonal board and, and the white player tries to get a p- a white path f- from left to right and the black player tries to get a black path from bottom to top.

Lex Fridman 59:49 And how does capture occur just so I understand that?

Donald Knuth 59:52 And, and there's no capture. You just put pebbles down o- one at a time. But there's no draws because af- af- after all the white and black are played, there's either gonna be a white path across from east to west or a black path fr- uh, from, from bottom to top. So there's always f- f- you know, it's the perfect information game and people, people play, take turns like, like, uh, Tic-Tac-Toe. Um, and, uh, and the Hex board can be different sizes. But anyway, there's no possibility of a draw and players move one at a time, and so it's gotta be either a first player win or a second player win. Mathematically, uh, you, you follow out all the trees and, uh, and eith- either th- there's always a win for the first player, second player, okay? And it's finite-... the game is finite. So there's an algorithm that will decide, y- you can show it has to be one or the other, be- because the second player could mimic the first player w- with kind of a pairing strategy.

Lex Fridman 1:00:48 Ah.

Donald Knuth 1:00:49 Um, and so you can show that, uh, uh, uh, it has to be one, it has to be one way or the other. But we don't know any algorithm anyway. We, we, we don't know if there is. Now, where there are, there are cases wh- where you can prove the existence of, o- o- o- of a solution, but we, but nobody knows any way how to find it. But more like the algorithm question, uh, there's a d- there's a very powerful th- theorem in graph theory by Robinson and Seymour that says that every class of graphs that is closed under taking minors has a po- has a polynomial-time algorithm to determine whether it's in this class or not. Now a class of graphs, for example, planar graphs, these are graphs that you can draw in a plane without crossing lines.

Lex Fridman 1:01:36 Mm-hmm.

Donald Knuth 1:01:37 And, and a planar graph is clo- uh, taking minors means that you can shrink a- an edge in, into a point or you can delete an edge.

Lex Fridman 1:01:47 Mm-hmm.

Donald Knuth 1:01:48 All right? And so you start with a planar graph and sh- shrink any edge to a point, it's still planar.

Lex Fridman 1:01:53 Mm-hmm.

Donald Knuth 1:01:54 Delete an edge, it's still planar. Uh, okay. Now, uh, but there are millions of different cl- uh, ways to describe a family of graph that still is, remains the same under taking minor.

Lex Fridman 1:02:13 Mm-hmm.

Donald Knuth 1:02:14 And Rob- Robertson and Seymour proved that any such family of graphs, there is a finite number of minimum graphs that are obstructions. It's l- so that if, if it's not in the family, then, then it has to contain e- eh, then there has to be a way to shrink it down and, e- until you get one of these bad minimum graphs-

Lex Fridman 1:02:39 Mm-hmm.

Donald Knuth 1:02:39 ... that's not in the family. For, in the pla- case of a planar graph, the minimum graph is a, is a five-pointed star where every, e- everything pointing to another, and the minimum graph consisting of trying to connect three utilities to three houses without crossing lines.

Lex Fridman 1:02:54 Mm-hmm.

Donald Knuth 1:02:54 And so there are two, there are two bad graphs that are not planar. And every, every non-planar graph contains one of these two gr- bad graphs by, by shrinking o- and, and, and removing edges.

Lex Fridman 1:03:07 Sorry, can, can you say that again? So, uh, the, uh, he proved that there's a finite number of these bad graphs. There's always a finite num- so somebody says, "Here's a family of-" That's hard to believe. (laughs)

Donald Knuth 1:03:17 It, and they proved in this-

Lex Fridman 1:03:19 It's very surprising.

Donald Knuth 1:03:19 ... it's sequence of 20 papers, I mean, and they're, uh, they're, it's, it's deep work. But, but, but it, you know, it's, uh, it's worth-

Lex Fridman 1:03:25 Because that's for any arbitrary class. So it's for any class-

Donald Knuth 1:03:28 A- any arbitrary class that's closed under taking minors.

Lex Fridman 1:03:31 That's closed under... Maybe I'm not understanding.

Donald Knuth 1:03:33 If, if, if, if-

Lex Fridman 1:03:33 Because it seems like a lot of them are closed under taking minors.

Donald Knuth 1:03:36 It, it, almost all the important classes of graphs are. There are tons of, of such graphs, but also hundreds of them that arise in applications.

Lex Fridman 1:03:47 Right.

Donald Knuth 1:03:48 I have a book over here called f- Classes of Graphs, and it, and, and, and it's, it's, it's amazing how many different, uh, classes of graphs that people have looked at. And-

Lex Fridman 1:03:58 So why do you bring up this theorem, uh, or this proof?

Donald Knuth 1:04:02 So, eh, now, there's lots of algorithms that, that are known for special classes of graphs. For example, if I have a cert- if I have a chordograph, then I can color it efficiently.

Lex Fridman 1:04:12 Mm-hmm.

Donald Knuth 1:04:13 Um, if, if I have s- some kinds of graphs, it'll make a great network. It's various things. So, so, so like, you'd like to test it, uh, if somebody gives you a graph, say, "Oh, is it in this family of graphs?" If, if so, then I have, then I can, I can go to the library and find an algorithm that's gonna solve my problem on that graph. Um, okay. So, so, so, so we, we have the, we want to have a graph that says, uh, uh, eh, algorithm that says, y- you, you give me a graph, I'll tell you whether it's in, whether it's in this, uh, family or not. Okay? And so all I have to do is test whether or not, that does this given graph have a minor that's one of the bad ones.

Lex Fridman 1:04:56 Mm-hmm.

Donald Knuth 1:04:57 A minor is, is everything you can get by shrinking and removing edges. And g- given any minor, there's a polynomial-time algorithm saying, "I can tell whether this is a minor of, of, uh, uh, uh, uh, of u." And there's a finite number of bad cases, so I just try, you know, does it have this bad case? P- polynomial time, I got the answer. Does it have this bad case? Polynomial time, I got the answer. A bit, uh, total polynomial time. And so I've solved the problem. However, all we know is that the number of minors is finite. We don't know what e- we, we might only know one or two of those minors, but we don't know that if we've got it, or if, if we've got 20 of them, we don't know if there might be 21, 25, there, there's just so f- all we, all we know is that, is that it's finite. So here we have a polynomial-time algorithm that we don't know.

Lex Fridman 1:05:45 Mm-hmm. That's a really great example of what you worry about, or why you think P equals NP won't be useful. But still, why do you hold the intuition that P equals NP?

Donald Knuth 1:05:59 Uh, because, eh, it, you have to ru- rule out s- so many possible algorithms as, as, as, as being not working.

Lex Fridman 1:06:08 Ah.

Donald Knuth 1:06:08 Uh, eh, eh, there, there, there's c- you, you know, you can, you can take the graph and you can represent it as, uh, eh, uh, in terms of certain prime numbers, and then you can multiply those together, and then you can, m- then, then you can take the bitwise AND, and, and, eh, eh, and, you know, eh, eh, and, uh, construct some certain constant in polynomial time, and then that's, you know, perfectly valid algorithm. And th- there are so many algorithms of that kind. A lo- a lot of times we see random-... uh, re- r- r- uh, y- you take data and, and it, an- and we get coincidences that, that, that some fairly random looking number actually is useful, because, uh, uh, be- be- because y- uh, it ta- it, uh, it, it happens to, it happens to solve, it happens to solve a problem just because, um, you know, there's, there's so many hairs on your head, uh, that, uh, but then s- uh, it, it seems like, uh, unlikely that two people are gonna have the same number of hairs on their head. How, how, how, how ... But, but th- that they're obvious, but you can count how many people there are, and how, and how many hairs on their head, so, so there must be people walking around in the country that have the same number of hairs on their head. Well, th- that's a kind of a coincidence that you, you might say also, you know, this, this particular combination of operations, uh, just happens to prove that the, a graph is, has a Hamiltonian path. I mean, uh, I, I see lots of cases where unexpected things, uh, happen when you have enough, enough possibilities.

Lex Fridman 1:07:43 (laughs) So because the space of possibility is so huge, your intuition just says it's-

Donald Knuth 1:07:47 Th- th- they have to rule them all out.

Lex Fridman 1:07:49 Yeah.

Donald Knuth 1:07:49 And so that, that's the reason for my intuition. Is it by no means a proof.

Lex Fridman 1:07:53 Okay.

Donald Knuth 1:07:53 I mean, some people say, uh, you know, "Well, P, P can't equal NP because you've had all these smart people, uh, y- you know, the smartest d- designers of algorithms have, have been racking their brains for years and years, and, and there's million dollar prizes out there, you know, none of them ... n- n- n- nobody, uh, has thought of, uh, the algorithm, so it must, there must be no such algorithm."

Lex Fridman 1:08:19 Right.

Donald Knuth 1:08:19 On the other hand, I can argue as exactly the same logic, and I can say, "Well, P must be equal to NP because there's so many smart people out here been trying to prove it unequal to NP, and they've all failed." Uh, you know? (laughs)

Lex Fridman 1:08:33 (laughs) This kind of reminds me of the, uh, discussion about the search for aliens.

Donald Knuth 1:08:38 Yeah.

Lex Fridman 1:08:38 Uh, that we've been trying to look for them, and we haven't found them yet, therefore they don't exist.

Donald Knuth 1:08:43 Yeah.

Lex Fridman 1:08:43 Uh, but you can show that there's so many planets out there that they very possibly could exist.

Donald Knuth 1:08:48 Yeah.

Lex Fridman 1:08:48 And, uh ...

Donald Knuth 1:08:49 Right. And then there's also the possibility that, that they exist, but they, they all discovered machine learning or something, and then-

Lex Fridman 1:08:58 (laughs)

Donald Knuth 1:08:58 ... and, and, and then blew each other up.

Lex Fridman 1:09:00 Well, on that small, quick tangent, let me ask, do you think there's intelligent life out there in the universe?

Donald Knuth 1:09:07 I have no idea.

Lex Fridman 1:09:08 Do you hope so? Do you think about it?

Donald Knuth 1:09:10 It ... I, I don't ... I, I don't spend my time thinking about things I, that I could never know really.

Lex Fridman 1:09:16 Mm-hmm. And yet you do enjoy the fact that there are as many things you don't know. You do enjoy the mystery of things.

Donald Knuth 1:09:24 I, I enjoy the fact that there, that I have limits, yeah.

Lex Fridman 1:09:27 (laughs)

Donald Knuth 1:09:27 But I don't ... But, but I don't take time to, to, to answer unsolvable questions, right?

Lex Fridman 1:09:34 Got it. Well, 'cause you've taken on some tough-

Donald Knuth 1:09:38 (laughs)

Lex Fridman 1:09:38 ... questions that may seem unsolvable. You have taken on some tough questions, they may seem unsolvable, but they're in a space-

Donald Knuth 1:09:44 And, and it gives me a thrill when I can get further than I ever thought I could.

Lex Fridman 1:09:47 Right.

Donald Knuth 1:09:48 Yeah.

Lex Fridman 1:09:48 But-

Donald Knuth 1:09:50 But I don't-

Lex Fridman 1:09:50 ... but much like with religion, uh, these-

Donald Knuth 1:09:52 I, I'm glad that there's ... that, that there's no proof that God exists or not.

Lex Fridman 1:09:57 (laughs)

Donald Knuth 1:09:57 I mean, this ... I think-

Lex Fridman 1:09:59 It would spoil the mystery.

Donald Knuth 1:10:00 It, it, it would be, it would be too dull, yeah.

Lex Fridman 1:10:02 (laughs) So, uh,

Lex Fridman 1:10:06 to quickly talk about the other art of artificial intelligence, what is a view, what's your view ... You know, artificial intelligence community has developed as part of computer science and in parallel with computer science since the '60s. Uh, what's your view of the AI community, uh, from the '60s-

Donald Knuth 1:10:25 Mm-hmm.

Lex Fridman 1:10:27 ... to now?

Donald Knuth 1:10:27 So all the way through, the, it was the, the people who were inspired by trying to mimic intelligence or, or to do things that, that were somehow the greatest of achievements of intelligence, that has been inspiration to people who have pushed the envelope of computer science, uh, p- r- m- maybe more than any other group of people. Uh, so it's, all the way through, it's been a great source of, of, uh, good problems to, to, uh, sink your teeth into. And, and getting, getting, um, uh, uh, partial answers, and then more and more successful answers over the years. So th- this has, this has been the inspiration for lots of the great discoveries of computer science.

Lex Fridman 1:11:16 Are you yourself captivated by the possibility of creating ... of algorithms having, um, echoes of intelligence in them?

Donald Knuth 1:11:26 Not as much as, as most of the people in the field, I guess I would say.

Lex Fridman 1:11:30 Right.

Donald Knuth 1:11:30 But, but, uh, that's not to say that they're wrong or that ... It's just y- you asked about my own personal preferences, and-

Lex Fridman 1:11:38 Right.

Donald Knuth 1:11:38 ... uh, but the, but the thing that I, that I, uh, uh, worry about is when people start believing that they've actually succeeded, um-

Lex Fridman 1:11:51 (laughs)

Donald Knuth 1:11:51 ... uh, and, uh, uh, uh, because the ... It seems to me there's huge gap between really understanding something and being able to pretend to understand something and give the i- give the illusion of understanding something.

Lex Fridman 1:12:08 Do you think it's possible to create without understanding?

Donald Knuth 1:12:12 Yeah.

Lex Fridman 1:12:12 So to, uh-

Donald Knuth 1:12:13 Oh, I, I do that all the time too. I mean ...

Lex Fridman 1:12:15 (laughs) Right.

Donald Knuth 1:12:16 I mean, that's why I use random numbers. I, I, I-

Lex Fridman 1:12:19 Yeah.

Donald Knuth 1:12:20 But I, uh, but, but there's, th- there's still w- this great gap. I, I, I don't assert that it's impossible, but I'm like, but I c- I don't see it, anything coming a- a- any closer to really, uh, th- uh, the kind of stuff that I would consider intelligence.

Lex Fridman 1:12:38 So you've mentioned something that, uh, on that line of thinking which-... I, I very much agree with, so The Art of Computer Programming is the book, is focused on single processor algorithms.

Donald Knuth 1:12:52 Uh-huh.

Lex Fridman 1:12:53 And for the most part, uh, you, you mentioned ...

Donald Knuth 1:12:57 It's only because I set the table of contents in 1962, you have to remember.

Lex Fridman 1:13:01 (laughs) For sure. There's no, uh-

Donald Knuth 1:13:04 I'm glad I didn't wait until 1965 or ... (laughs)

Lex Fridman 1:13:08 (laughs) That's ... Uh, one book, uh, maybe we'll touch on the Bible, but one, one, one book can't always cover the entirety of everything. So I'm glad-

Donald Knuth 1:13:18 Yeah.

Lex Fridman 1:13:19 ... uh, um, I'm glad the, uh, the table of contents for, uh, the, The Art of Computer Programming is what it is.

Lex Fridman 1:13:26 But you did mention that, uh, that you thought that understanding of the way ant colonies are able to perform incredibly organized tasks might well be the key to understanding human cognition, so these fundamentally-

Donald Knuth 1:13:40 Yeah.

Lex Fridman 1:13:40 ... distributed systems. So what do you think-

Donald Knuth 1:13:42 Sure.

Lex Fridman 1:13:43 ... is the difference between the way, um, Don Knuth would sort a list and an ant colony would sort a list or-

Donald Knuth 1:13:50 Well, yeah.

Lex Fridman 1:13:50 ... perform an algorithm?

Donald Knuth 1:13:52 Sorting a list isn't the same as cognition though, uh, but, but I know what, what you're getting at, is, uh, so, so, well, the advantage of ant colony, at least we can see what they're doing. We, we, we know which ant has talked to which other ant. And, and, and, and it's much harder, uh, with, with the, with brains to, to, to, to know how, to what extent, uh, neurons are, are passing signals. So I'm just saying that ant colony might be a ... If they have the secret of co- of cognition, like think of an ant colony as a cognitive single being rather than as a, as a colony of lots of different ants. I mean, just like the, the cells of our brain are and, and, and the microbiome and all that is, is, is interacting, uh, uh, entities. But, uh, but somehow the, I consider myself to be (laughs) one single person. Well, you know, an ant colony, uh, you can say might be cognitive, cognitive in somehow and ...

Lex Fridman 1:14:55 It sounds, it sounds strong.

Donald Knuth 1:14:57 Yeah, I mean, you know, I ... Okay, uh, uh, I, I, I smash a certain ant and organism. "Hmm. That stung. What was that?"

Lex Fridman 1:15:06 Right.

Donald Knuth 1:15:06 But if we're going to crack the, the secret of cognition, it might be that we could do so by, by psyching out how ants do it, because we have a better chance to measure. They're communicating by pheromones and by touching each other and sight, but, but not by much more subtle phenomenon like electric currents going through.

Lex Fridman 1:15:30 But even a simpler version of that, what are your thoughts of maybe Conway's Game of Life?

Donald Knuth 1:15:35 Okay, so Conway's Game of Life is, is able to simulate any, any computable process. And, and any deterministic process is, uh-

Lex Fridman 1:15:46 I like how you went there. I mean, that's not its most powerful thing, I would say. I mean, um-

Donald Knuth 1:15:55 But-

Lex Fridman 1:15:55 It can simulate it, but the, the magic is that the individual units are distributed.

Donald Knuth 1:16:01 Yes.

Lex Fridman 1:16:02 And extremely simple.

Donald Knuth 1:16:03 Yes. We, we understand exactly what the primitives are.

Lex Fridman 1:16:06 The primitives. Just like with the ant colony-

Donald Knuth 1:16:08 But-

Lex Fridman 1:16:08 ... even simpler though.

Donald Knuth 1:16:09 But if we ... But still it doesn't say that I understand, uh, I understand life. I, I mean, I under- Uh, it, it gives me an ... It gives me a better insight into what does it mean to, uh, to have a deterministic universe. To ... What does it mean to, um, to have free choice, for example?

Lex Fridman 1:16:35 Do you think God plays dice?

Donald Knuth 1:16:38 Yes. I don't see any reason why God should be forbidden from using the most efficient ways to, to, uh, uh, to ... I mean, we know that dice are extremely important in efficient algorithms. There are things like that couldn't be done well without randomness. And so I don't see any reason why, why God should be, be prohibited from-

Lex Fridman 1:17:02 When the algorithm requires it, uh-

Donald Knuth 1:17:05 Yeah.

Lex Fridman 1:17:05 ... I don't ... You don't see why the-

Donald Knuth 1:17:07 Yeah.

Lex Fridman 1:17:08 ... physics should constrain it. Um-

Donald Knuth 1:17:11 Yeah.

Lex Fridman 1:17:11 So in 2001, you gave a series of lectures at MIT about religion and science.

Donald Knuth 1:17:17 No, that was 1999. But-

Lex Fridman 1:17:19 You published a ... Sorry.

Donald Knuth 1:17:20 The book came out in 2001.

Lex Fridman 1:17:22 In 2000. So in 1999, you spent a little bit of time in Boston enough to give, uh, those lectures.

Donald Knuth 1:17:29 Yeah.

Lex Fridman 1:17:30 And, uh, I read the 2001 version, most of it. It's quite fascinating read, I recommend people ... It's a transcription of your lectures. So what did you learn about how ideas get started and grow from studying the history of the Bible? So you've rigorously studied a very particular part of the Bible, uh, what did you learn from this process about the way us human beings as a society develop and grow ideas, share ideas and-

Donald Knuth 1:18:00 Yeah.

Lex Fridman 1:18:00 ... are defined by those ideas?

Donald Knuth 1:18:01 Well, I ... It's hard to summarize that. Um, I wouldn't say that I, that I learned a great deal of, of really definite things, like where, where I could make conclusions, but I learned more about what I don't know. You have a complex subject, which is really beyond human understanding. Uh, uh, so, so we give up on saying I'm never going to get to the end of the road and I'm never gonna understand it, but you say, but, but maybe it might be good for me to, uh, uh, to get closer and closer and learn more about, more and more about something. And so, you know, how can I do that, uh, uh, efficiently? And the answer, uh, is, well, use randomness. Um, and so-... so, so try a random subset of the, uh, that, that is within my grasp, and, and, and, and study that in detail instead of just, uh, studying parts that somebody tells me to study, or instead of stu- studying nothing, (sighs) because it's too hard. Um, uh, so I, I, I, I decided, uh, uh, for, for my own amusement, uh, one, once that I would, I would take a subset of the ver- of the, uh, verses of the Bible, and I would, um, try to find out what the best thinkers have said about the, the, that small subset.

Lex Fridman 1:19:29 Mm-hmm.

Donald Knuth 1:19:29 And I had, I had about, uh, let's say 60, 60 verses out of, out of 3,000. I think it was one out of 500 or something like this. And so then I went to the libraries which, which are well-indexed. Uh, uh, you can, you, you, I, I spent, um, uh, uh, for example, at, um, at Boston Public Library I, I would go once a week for, for a year, and I went to, uh, uh, I went, uh, uh, have done times to Andover Harvard Library to, to look at the s- you know, books that weren't in the Boston Public. Uh, where they, where scholars had looked, and you can go in the, and you can go down the shelves and you can, and, and you can pretty... And you can look in the index and say, "Oh, is there, is, is this verse, uh, mentioned anywhere in this book? If so, look at page 105." So, so in other words, I, I could learn not only about the Bible, but about the secondary literature about the Bible, the things that scholars have written about it. And so that, that gave me a way to, uh, uh, uh, to zoom in on parts of the thing so that I could get more, more insight. And, and, and so I look at it as, as a way of giving me some, some firm pegs of which I, on which I could hang pieces of information, but not as, as things where I would say, "And therefore this is true."

Lex Fridman 1:20:50 In this, uh, random approach of sampling the Bible-

Donald Knuth 1:20:54 Mm-hmm, yeah.

Lex Fridman 1:20:55 ... what did you learn about the, the most, uh, you know, central... Uh, one of the biggest accumulation of ideas in our community.

Donald Knuth 1:21:05 It seemed, it seemed to me that the, that the main thrust was not the one that most people think of as saying, you know, oh, oh, oh, you know, "Don't have sex," or something like this.

Lex Fridman 1:21:14 (laughs)

Donald Knuth 1:21:15 Um, but that the main thrust (laughs) was, uh, to try to, to, to try to figure out how to live in harmony with God's wishes.

Lex Fridman 1:21:26 Mm-hmm.

Donald Knuth 1:21:26 I'm assuming that God exists, and I, and as I said, I'm glad that I, that there's no way to prove this, because that wouldn't, that would, that I, I would run through the proof once, and then I'd forget it, and, and it would... Uh, and, and I would never, uh, s- uh, speculate about spiritual things and, uh, mysteries, uh, otherwise, and I think my life would be very incomplete. So I'm, uh, uh, so, so I'm, I'm assuming that God exists, but it, if, uh, but a lot of the, uh, the people s- say God doesn't exist, but that's still important to them, and so in, in a wa- in a way, that might sti- still be, uh, w- whether God is there or not, uh, uh, in some sense, uh, in, you know, in, God is important to them. It's, it's... One of the, one of the verses I studied actually is, uh, y- you can interpret it as saying that, you know, it's much better to be an atheist than, than not to care at all. (laughs)

Lex Fridman 1:22:23 Mm-hmm. So I would say it's, yeah, it's similar to the P equals NP discussion, uh...

Donald Knuth 1:22:29 Yeah.

Lex Fridman 1:22:29 You, you mentioned a mental exercise, uh, that I, I, I'd love it if you could partake in yourself. Uh, a mental exercise of, uh, being God and... So how would you, if you were God, Don Knuth, how would you present yourself to the people of Earth?

Donald Knuth 1:22:45 You mentioned, uh, your love of literature, and there was, uh, th- there's this book that, that really, uh, I can recommend to you. If I c- I think, yeah, the title, I think, is Blasphemy. It talks about, um, God revealing himself through a computer in, in, in, in, in Los Alamos.

Lex Fridman 1:23:01 (laughs)

Donald Knuth 1:23:01 And, and, uh, it, um, uh... It's the only book that I've ever read where, uh, the punchline was really the very last word of the book, and it, and explained the whole idea of the book. And so I don't wanna give that away, but it, but it's really m- very much about this question that you're, that, that you raised. Uh, uh, the, uh, but, but s- suppose God, uh, uh, s- said, "Okay, that, my, my prev-, my previous, um, means of communication with the world (laughs) are not the best for the 21st century, so what should I do now?" And, uh, and, and it's conceivable that (laughs) , that it would, uh, that that God would choose the way that's described in this book.

Lex Fridman 1:23:50 Another way to look at this exercise is, uh, looking at the human mind, looking at the human spirit, the human life in a systematic way.

Donald Knuth 1:23:59 I think it's mostly do you wanna learn humility? You wanna r- realize that once we solve one problem, that doesn't mean that we're, that all of a sudden other, other problems are gonna drop out, and, and, and, and we have to realize that, that, uh, uh, that there are, there are things beyond our, beyond our, our ability. Um, I see hubris all around. (laughs)

Lex Fridman 1:24:26 (laughs) Yeah, well said.

Lex Fridman 1:24:28 Uh, if you were to run program analysis on your own life, uh, how did you do in terms of correctness, running time-

Donald Knuth 1:24:37 Oh, yeah, them well-

Lex Fridman 1:24:38 ... resource use, asymptotically speaking, of course.

Donald Knuth 1:24:41 Okay, yeah. Well, I would say, (laughs) that question has not been asked me before.

Lex Fridman 1:24:48 (laughs)

Donald Knuth 1:24:48 Um, and, uh, I...... I, uh, I started out, uh, eh, with library subroutines and, and, uh, uh, learning how to be a automaton that was obedient. And I had the great advantage that I d- didn't have anybody to blame for my failures. If I started getting, uh, n- not understanding something, I, I knew that I should stop playing ping pong and that, that, and it was my fault that, that I was d- I wasn't studying hard enough or something, rather than that somebody was discriminating against me in some way, and, and, uh, I don't know how to avoid this re- the existence of biases in the world. But I, but I, but I know that that's an extra burden that I didn't have to suffer from. Um, and, uh, and, and then I, uh, uh, I f- found the, uh, uh, uh, fr- from, from parents I learned, uh, the idea of, uh, uh, of altru- of service, uh, to, to other people as being more important than p- than, uh, uh, w- what I get out of stuff myself. I, like, know that I need to, I need to be happy enough, uh, e- enough in order to be able to sp- be of service. But I do- but I, you know, but I, I came to a philosophy, uh, for finally that, that I phrase as .8 is enough. Uh, there, there was a TV show once called Eight Is