Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life | Lex Fridman Podcast #219

1. 0:00 – 0:48

   Introduction

   1. LFLex Fridman0:00

      The following is a conversation with Donald Knuth, his second time on this podcast. Don is a legendary computer scientist, Turing Award winner, father of algorithm analysis, author of The Art of Computer Programming, creator of TeX that led to LaTeX, and one of the kindest and most fascinating human beings I've ever got a chance to talk to. I wrote him a letter a long time ago. He responded, and the rest, as they say, is history. We've interacted many times since then and every time has been joyful and inspiring. To support this podcast, please check out our sponsors in the description. This is the Lex Fridman Podcast, and here is my conversation with Donald Knuth.

2. 0:48 – 24:11

   First programs

   1. LFLex Fridman0:48

      Your first large-scale program, you wrote it in IBM 650 Assembler in the summer of 1957.

   2. DKDonald Knuth0:55

      I wrote it in decimal machine language. I didn't know about Assembler until a year later.

   3. LFLex Fridman1:00

      But the year 1957-

   4. DKDonald Knuth1:02

      The year, it was, it was-

   5. LFLex Fridman1:02

      ... and the program is tic-tac-toe.

   6. DKDonald Knuth1:04

      Y- yeah. I might have learned about A- Assembler later that summer. Yeah, I probably did. In 1957, hardly anybody had heard of assemblers. You looked at the user manuals, (laughs) "H- h- how do you write a program for this machine?" It would, it, it would, it would say, um, uh, y- y- y- you know, you would say 69 which meant load the distributor and, and then you would give the address of, of the number you wanted to load into the distributor.

   7. LFLex Fridman1:26

      Mm-hmm.

   8. DKDonald Knuth1:27

      Uh, yesterday, uh, my friend at, uh, Doug Spicer at the Computer History Museum sent me a link to something that just went on YouTube. It was IBM's, uh, progress report from 1956 which was, you know, very contemporary with 1957. (laughs)

   9. LFLex Fridman1:44

      (laughs) Yes.

   10. DKDonald Knuth1:44

       Um, and in 1956, IBM had donated to Stanford University an IBM 650, one of the first ones. When they showed a picture of the assembly line for IBM 650s and they said, you know, "This is number 500 or something coming off the assembly line." And-

   11. LFLex Fridman2:00

       Mm-hmm.

   12. DKDonald Knuth2:01

       ... and I had never seen so many (laughs) IBM 650s ex- I did in this movie that was, uh, it's on YouTube now.

   13. LFLex Fridman2:08

       Mm-hmm.

   14. DKDonald Knuth2:08

       Um, and, and it showed the picture from Stanford, uh, that, that's, m- m- you know, they, they, they said, you know, "We, we donated one of these to Stanford, one to MIT," and they mentioned one other, oh, oh, one other college. And in, in December of '56, they donated to, to my university, Case Tech.

   15. LFLex Fridman2:28

       Mm-hmm.

   16. DKDonald Knuth2:29

       Um, but anyway, they showed a picture then, uh, of a class session, uh, where a guy was teaching programming and on the blackboard, it said, "69 8,000." I mean, he-

   17. LFLex Fridman2:42

       Mm-hmm.

   18. DKDonald Knuth2:43

       ... he, he, it, it was, uh, the, he was teaching them how to write, uh, code for this IBM 650 which was in decimal numbers. So, so, so the instructions were 10 di- 10 decimal digits. You had, you had two digits that said what, wh- wh- what to do-

   19. LFLex Fridman3:00

       Mm-hmm.

   20. DKDonald Knuth3:00

       ... four digits to say, uh, uh, what to do it to (laughs) -

   21. LFLex Fridman3:04

       (laughs)

   22. DKDonald Knuth3:04

       ... and four more digits to say where to get your next instruction.

   23. LFLex Fridman3:08

       And there's a manual that describes what each of the numbers mean?

   24. DKDonald Knuth3:11

       And the manual was actually what, uh, if the manual had been well written, I probably never would have gone into computer science. But it was so badly written, I figured, uh, that I must have a talent for it because I'm only a freshman and I c- and I could write a better manual.

   25. LFLex Fridman3:25

       (laughs)

   26. DKDonald Knuth3:26

       Uh, and, and-

   27. LFLex Fridman3:27

       That's what you did.

   28. DKDonald Knuth3:28

       ... a- a- and so I, I, I started working at the computer center, um, uh, and, and, uh, wrote some manuals then. But, but, (laughs) yeah, but, but this was, uh, uh, but this was the way we did it. And, and my first program then was June of, uh, 1957.

   29. LFLex Fridman3:46

       The tic-tac-toe. That-

   30. DKDonald Knuth3:48

       No. That was the second program. The first, this, the third pro- the, the first program was factoring a, a number.
3. 24:11 – 27:20

   Literate programming

   1. LFLex Fridman24:11

      Bach, if somebody looked at Don Knuth code, would they be able to tell that this, uh, is a distinct style of thinking going on here?

   2. DKDonald Knuth24:22

      Huh.

   3. LFLex Fridman24:23

      What do you think?

   4. DKDonald Knuth24:24

      Uh ...

   5. LFLex Fridman24:26

      (laughs) And what, what would be the defining-

   6. DKDonald Knuth24:28

      I, I, yeah, uh-

   7. LFLex Fridman24:28

      ... uh, characteristic of the style?

   8. DKDonald Knuth24:31

      Well, uh, uh, my code now is, uh, it, it, it is literate programming so I'm, it's a combination of English and C mostly. (laughs) But, but, but e- if you just looked at the C part of it, you would also probably notice that I don't, y- uh, that it, you can't, you know, that I use a lot of global variables that other people don't and, and, and I, and I expand things inline more than in- instead of calling ... anyway, I, I have different subset of C that I use. Um-

   9. LFLex Fridman25:00

      Okay. But that's, that's a little bit stylistic, uh-

   10. DKDonald Knuth25:03

       Yeah. But, but with literate programming, you alternate between English and, and, and, and C or whatever, or, yeah, yeah, yeah. And, um-

   11. LFLex Fridman25:11

       And by the way, people listening to this should look up literate programming. It's very interesting, uh, concept that you, uh, that you proposed and developed over the years.

   12. DKDonald Knuth25:21

       Yeah. Yeah. The ... I, I'm s- that, that's the most, uh, significant thing f- I think to come out of the TeX project is the pro- is, is that I-

   13. LFLex Fridman25:33

       Mm-hmm.

   14. DKDonald Knuth25:33

       ... uh, uh, I, I realized that, uh, um, my programs w- were to be read by people and not-

   15. LFLex Fridman25:42

       (laughs)

   16. DKDonald Knuth25:42

       ... (laughs) not just by computers and, and, and that typography could massively enhance that. And, and, and, and, and so, uh, I mean, it, there are just wonderf- if they're gonna look it up, that they should also look up this book by, it's called Physically Based Rendering-

   17. LFLex Fridman25:59

       Mm-hmm.

   18. DKDonald Knuth26:00

       ... by Matt Fahr and, gosh, uh, anyway, it, you know, got an Academy Award. But it's, but, but all the eff- all the graphic effects you see in movies, uh, like, uh, you know, are accomplished by algorithms. And this book, it is, the whole book is a literate program. It tells you not only h- how you do all the shading and, uh, and, and, uh, bring images in that you need for ani- animation and textures and so on, but it also, uh, you can run the code. (laughs)

   19. LFLex Fridman26:31

       Mm-hmm.

   20. DKDonald Knuth26:32

       Uh, so, uh, and, and, and so, uh, I find it, uh, uh, an extension of the way I, uh, of, of, of how to teach programming is, it is but by, is by telling a story, uh, as part of the program. (clears throat)

   21. LFLex Fridman26:47

       So it's, uh, it, it works as a program, but it's also readable by humans.

   22. DKDonald Knuth26:53

       Uh, e- e- e- es, and especially by me, uh-

   23. LFLex Fridman26:56

       (laughs) Yeah.

   24. DKDonald Knuth26:57

       ... uh, a week later or a year later.

   25. LFLex Fridman26:58

       That's a good test.

   26. DKDonald Knuth26:59

       Yeah.

   27. LFLex Fridman26:59

       If you yourself understand the code-

   28. DKDonald Knuth27:02

       Yeah.

   29. LFLex Fridman27:02

       ... uh, easily, uh, a week or month-

   30. DKDonald Knuth27:05

       Write it.
4. 27:20 – 33:15

   Beauty in programming

   1. LFLex Fridman27:20

      Okay. You, uh, dodged this question in an interview I listened to. Uh, so let me ask you again here. (laughs) Uh, what makes for a beautiful program?

   2. DKDonald Knuth27:30

      What makes for a beautiful program?

   3. LFLex Fridman27:32

      Yeah. What are the characteristics you see? Like you just said literate programming, what are the characteristics you see in a program that make you sit back and say, "That's pretty good."

   4. DKDonald Knuth27:43

      Well, the reason I didn't answer it because there are mo- there are dozens and dozens of answers to that bec- be- because e- each-

   5. LFLex Fridman27:50

      Yes.

   6. DKDonald Knuth27:50

      ... you, you can define beauty, the same person will define beauty a different way from hour to hour. I mean, it depends on what, uh, uh, on what you're looking for. It, it, at one level, you, it's, it's beautiful just if it works at all. (laughs) At another level, it's beautiful if it's, I- if it, uh, uh, uh, can be understood easily. If it's b- it's, it's, it's beautiful if it, uh, uh, if it's literate programming, it's beautiful, it makes you laugh. I mean, uh ...

   7. LFLex Fridman28:21

      Yeah. I'm actually, so I'm with you. I think beauty, if it's readable.

   8. DKDonald Knuth28:27

      Readable, yeah.

   9. LFLex Fridman28:28

      Is if you understand what's going on, and also understand the elegance of thought behind it, and then also as you said, wit and humor. I was always, um ... I remember having this conversation, I had this conversation on Stack Overflow whether humor is good in comments. And I think it is.

   10. DKDonald Knuth28:51

       Wh- wh- whether humor, is, is good in comments?

   11. LFLex Fridman28:53

       Like, uh, when you add comments-

   12. DKDonald Knuth28:54

       Yeah.

   13. LFLex Fridman28:55

       ... to your code.

   14. DKDonald Knuth28:56

       Yeah.

   15. LFLex Fridman28:56

       Uh, I always thought a little bit of humor is good. (laughs) It shows personality.

   16. DKDonald Knuth29:02

       Mm-hmm.

   17. LFLex Fridman29:02

       It shows character, shows wit and fun and all those kinds of things-

   18. DKDonald Knuth29:06

       Mm-hmm. Yeah.

   19. LFLex Fridman29:07

       ... of, of the personality of the programmer.

   20. DKDonald Knuth29:08

       Yeah. Okay. So, uh, a couple of days ago, I received a, uh, a wonderful present from my former editor at Addison-Wesley. He, he, he's downsizing his house and he found, uh, that, that somebody at the company had, had found all the, all of their internal files about The Art of Computer Programming from the 1960s-

   21. LFLex Fridman29:32

       Mm-hmm.

   22. DKDonald Knuth29:32

       ... and they gave it to him. (laughs) Uh, and then, uh, you know, before throwing, throwing in the garbage. And then he, so he said, "Oh, yeah," he, he planned to keep it for posterity, but now he realized that posterity is a, it's a bit too much for him to handle, so he sent it to me.

   23. LFLex Fridman29:48

       (laughs)

   24. DKDonald Knuth29:49

       Uh, and so, and, and so I just received, uh, this big, big stack of, uh, of letters. Uh, some of which I had written to them, but, but many of which they had written to early guinea pigs who were, who, telling 'em whether they, they should publish or not, you know?

   25. LFLex Fridman30:06

       Mm-hmm.

   26. DKDonald Knuth30:07

       And, and one of the things wh- was, uh, uh, in, in the, uh, in the comments to, to volume one, uh-... uh, the, the major, the major reader was, was Bob Floyd, uh, who, who was my great, uh, co-worker in the '60s, um, died early unfortunately. But, but, uh, uh, and, and he, he, he commented about the humor I- i- in it. And so, so, so we had, you know, he loo- r- ran it by me, you know, he says, you know, "Keep this joke in or not?" You know.

   27. LFLex Fridman30:42

       (laughs) yeah.

   28. DKDonald Knuth30:43

       Uh, uh, he, you know, they also sent it out to focus groups, you know (laughs) , "What do you think about humor in a, i- i- i- in a book about computer programming?"

   29. LFLex Fridman30:50

       What's the conclusion?

   30. DKDonald Knuth30:51

       And I stated my philosophy is, it says, you know, the ideal thing is, uh, that it's, it's like, it's something where the reader knows that there's probably a joke here if you only understood it, and this is a motivation to understand, to, to, to think about it a little bit. Um, but, but anyway, it, it, it, it's a very delicate humor. It's a very... I mean, it's, it's really a... each, each century invents a different kind of humor too. I mean, and, uh, and, and d- different cultures have different, different kinds of humor, um.
5. 33:15 – 42:26

   OpenAI

   1. LFLex Fridman33:15

      Let me explain it, maybe you'll find it interesting. So OpenAI is a company that, that does, uh, AI work. And they have this language model, it's a neural network that can generate language pretty well.

   2. DKDonald Knuth33:30

      Uh huh.

   3. LFLex Fridman33:31

      But they also have, on top of that, developed something called OpenAI Codex, and together with GitHub, they developed a system called OpenAI Copilot. Let me explain what it does. There's echoes of literate programming in it. So what you do is you start writing code and it completes the code for you.

   4. DKDonald Knuth33:55

      Uh huh.

   5. LFLex Fridman33:55

      So for example, you start... let's go to your factoring program. You start, you write in JavaScript, in Python, in any language...

   6. DKDonald Knuth34:04

      Yeah.

   7. LFLex Fridman34:04

      ... that it trained on. Uh, you start l- you write the first line and some comments, like what this code does, and it generates the function for you. And it does an incredibly good job. Like, it's not provably right, but it often does a really good job of completing the code for you.

   8. DKDonald Knuth34:23

      I see. Whether... but how do you know whether it did a good job or not?

   9. LFLex Fridman34:27

      You could see a lot of examples where it did a good job, and so you... it's, it's not a thing that generates the code for you.

   10. DKDonald Knuth34:35

       Yeah, exactly.

   11. LFLex Fridman34:35

       It starts... it gives you, um... uh, so it puts the human in the seat of fixing issues-

   12. DKDonald Knuth34:43

       Yeah.

   13. LFLex Fridman34:43

       ... versus writing from scratch. Do you find that kind of idea at all interesting?

   14. DKDonald Knuth34:48

       Every year, we're gonna be losing more and more control over what machines are doing. And, e- e- and people are saying, "Well, it seems to..." I, when I was (laughs) a professor at Caltech, uh, in the, in the '60s, we had this, this guy who, who talked a good game. He could give inspiring lectures and you'd think, "Well, he..." uh, th- thrilling things he was talking about and an hour later, you'd say, "Well, what did he say?"

   15. LFLex Fridman35:17

       (laughs)

   16. DKDonald Knuth35:17

       Um, uh, but what, but, but he really felt that it didn't matter whether computers got the right answer or not, it just mattered whether it made you happy or not. In other words, if, you know, if, if, if your boss paid for it, uh, he, uh, he, you know, then you had a job, you could, you, you know, you could, you could take care of your wife and-

   17. LFLex Fridman35:35

       So happiness is more important than truth.

   18. DKDonald Knuth35:37

       E- exactly. He didn't believe in truth, but he was a philosopher. (laughs)

   19. LFLex Fridman35:42

       (laughs) I like it. Um, and somehow, you, you see a...

   20. DKDonald Knuth35:46

       But w- we're going that way. I mean, w- so, so many more things are, are taken over by saying, "Well, this seems to work." And-

   21. LFLex Fridman35:53

       So-

   22. DKDonald Knuth35:54

       ... and, and when there's, when, when there is, uh, competing interests involved, neither side understands why the decision is being made. Uh, uh, uh, it, uh, it, you know, we, we realize now that it's, that it's bad. But, uh, but consider what happens five, five year, 10 year-

   23. LFLex Fridman36:11

       Mm-hmm.

   24. DKDonald Knuth36:12

       ... years down the line when, when things get even more f- further detached and each thing is based on s- something from the previous year.

   25. LFLex Fridman36:20

       Yeah. So you start to lose... the more you automate, the more you start to lose track of, uh, some deep-

   26. DKDonald Knuth36:26

       Exponentially.

   27. LFLex Fridman36:28

       ... human things. Exponentially. But, so that's the dark side.

   28. DKDonald Knuth36:32

       That is.

   29. LFLex Fridman36:32

       The positive side is...... the more you automate, the more you let humans do what humans do best. So, maybe programming this, you know, maybe humans should focus on a small part of programming that requires that genius, the magic of the human mind and the mess you let the machine generate.

   30. DKDonald Knuth36:54

       Yeah.
6. 42:26 – 48:31

   Optimization

   1. LFLex Fridman42:26

      In The Art of Computer Programming, you wrote, "The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times. Premature optimization is the root of all evil."... in parentheses, or at least most of it, in programming. Can you, uh, explain this idea? Uh, what's the wrong time? What is the wrong place for optimization?

   2. DKDonald Knuth42:54

      So, f- first of all, the word "optimization." I, I, I started out writing software, uh, and optimization was... I was a compiler writer, so optimization meant, uh, making the, uh, making a better translation, it- it- it, so that it would run faster on a- o- on a machine.

   3. LFLex Fridman43:15

      Mm-hmm.

   4. DKDonald Knuth43:15

      So an optimized program is just like, you know, you, you, you run a pr- program and you set the optimization level f- uh, f- uh, to- to the compiler. So that's one w- word for optimization. Um, and at that time, I, uh, I happened to be looking in an unabridged dictionary, uh, for some reason or other and I came to the word optimize. I said, "What's the meaning of the word optimize?" And it says, "To view with optimism."

   5. LFLex Fridman43:43

      (laughs)

   6. DKDonald Knuth43:44

      And, and you, you look in Webster's-

   7. LFLex Fridman43:46

      Yeah.

   8. DKDonald Knuth43:47

      ... Dictionary of English Language in 196- or the 1960s, that's what optimize mean- meant. Okay. Um, eh, now, eh, uh, now, so people started doing cost optimization, other kinds of things, uh, uh, you know, c- whole subfields of, uh, of, uh, algorithms and economics and whatever are, are based on what they call optimization now. But, uh, but to me, optimization, when I was saying that, was saying, uh, uh, changing a program to make it more, uh, tuned to the machine. And I found out that, um, w- when a person writes a program, uh, e- e- he or she tends to think that the parts that were hardest to write are gonna be hardest for the computer to execute. S- s- so, so, so maybe I have 10 pages of code, but I, I had to work a week writing this page. I, uh, mentally think that when the com- computer gets to that page, it's gonna slow down.

   9. LFLex Fridman44:51

      (laughs) Right.

   10. DKDonald Knuth44:52

       Uh, it's gonna say, "Oh, I don't understand what I'm doing. I better, I better be more care..." Anyway, this is, of course, silly, but it's, it, it's something that we, that we, that we don't know when we write a piece of code. We don't know what-

   11. LFLex Fridman45:05

       Mm-hmm.

   12. DKDonald Knuth45:05

       ... wha- whether the computer is actually gonna be executing that code very much.

   13. LFLex Fridman45:09

       Mm-hmm.

   14. DKDonald Knuth45:10

       S- so, so people had a, had a very poor understanding of, o- of wh- what the computer was actually doing.

   15. LFLex Fridman45:18

       Mm-hmm.

   16. DKDonald Knuth45:18

       Uh, I, I made one test where, w- where we, we studied a, uh, Fortran compiler and it was spending more than 80% of its time reading the comments card.

   17. LFLex Fridman45:29

       Mm-hmm.

   18. DKDonald Knuth45:30

       Um, but as a programmer, we were really concerned about how fast it could take a complicated expression that had lots of levels of parentheses-

   19. LFLex Fridman45:37

       Mm-hmm.

   20. DKDonald Knuth45:38

       ... and, a- and, and convert that in- in- into something. But that was just, you know, less than 1% of the... (laughs) Uh, uh, so if we optimize that, uh, uh, we didn't know what we were doing. But it, but, but if, if we knew that it was spending 80% of its time on the comments-

   21. LFLex Fridman45:55

       Mm-hmm.

   22. DKDonald Knuth45:55

       ... card, you know, in 10 minutes, we could, we could make the, the, uh, the compiler run more than twice as fast.

   23. LFLex Fridman46:01

       And you can only do that once you've completed the program and then you empirically-

   24. DKDonald Knuth46:05

       Right.

   25. LFLex Fridman46:05

       ... study where-

   26. DKDonald Knuth46:06

       I had some kind of profiling that, that I knew what was important. Yeah.

   27. LFLex Fridman46:10

       So, uh, you, you don't think this applies generally? I mean, there is something that rings true to this across all programs.

   28. DKDonald Knuth46:15

       I'm glad that it applied generally, but it, but it was, it was only my good luck. I, I said it, but he, you know, but it, but I did, but I said it in a limited context and I, and, and I'm gl- glad if it makes people think about stuff because I, you know, I'm... But it applies i- in another sense too that is, um, sometimes I will do optimization in a, in a way that does help the, the, the actual running time but makes the program impossible to change next week-

   29. LFLex Fridman46:50

       Right.

   30. DKDonald Knuth46:50

       ... because I've changed my data structure or something that, that made it less adaptable. So one of the great, uh, uh, principles of computer science is, uh, is, uh, is laziness or whatever you call it, uh, uh, late binding. Uh, you know, don't... Hold, hold off decisions w- when you can.
7. 48:31 – 57:14

   Consciousness

   1. DKDonald Knuth48:31

   2. LFLex Fridman48:31

      Let me ask you a weird question. So Roger Penrose, uh, has talked about computation, computers and, uh, he proposed that...... the way the human mind discovers mathematical ideas is something more than a computer, that, that a universal Turing machine cannot, uh, do everything that a human mind can do.

   3. DKDonald Knuth48:57

      Mm-hmm.

   4. LFLex Fridman48:58

      Now this includes discovering mathematical ideas and it also includes, he's written a book about it, consciousness. So I don't know if you know Roger, but-

   5. DKDonald Knuth49:09

      Mm. Yeah.

   6. LFLex Fridman49:09

      ... do you think-

   7. DKDonald Knuth49:10

      My, uh, my daughter's kids played with his kids in Oxford. (laughs)

   8. LFLex Fridman49:14

      (laughs) Nice. So do you think there is such a limit to the computer? Do you think consciousness is more than a computation? Do you think the human mind, the way it thinks is more than a computation?

   9. DKDonald Knuth49:29

      I, I mean, I, I, I could say yes or no but, but, but I don't be- I have no reason t- I, I mean-

   10. LFLex Fridman49:36

       So you don't find it useful to have an intuition in one way or the other? Like when you think about algorithms, do you-

   11. DKDonald Knuth49:42

       Mm. Well-

   12. LFLex Fridman49:42

       ... isn't it useful to think about-

   13. DKDonald Knuth49:43

       ... I, I think it's an unanswerable-

   14. LFLex Fridman49:44

       ... the limits?

   15. DKDonald Knuth49:45

       ... uh, unanswerable question. And my opinion is, is no better than anybody else's.

   16. LFLex Fridman49:49

       You think it's unanswerable? So you-

   17. DKDonald Knuth49:51

       Yeah.

   18. LFLex Fridman49:51

       ... you don't think eventually science will be able to-

   19. DKDonald Knuth49:52

       How many angels can dance on the head of a p- I mean, I don't know.

   20. LFLex Fridman49:55

       No, but angels aren't-

   21. DKDonald Knuth49:57

       ... I, I, I, anyway, there, there are lots of things that are beyon- that, uh, that we can speculate about but, uh, I don't want somebody to say, "Oh yeah, Knuth said this and, and so he's, he's, he's smart and so, so he, so that must be..."

   22. LFLex Fridman50:10

       (laughs)

   23. DKDonald Knuth50:10

       I, I mean, I, I say it's something that, uh, we'll, we'll never know, uh ...

   24. LFLex Fridman50:16

       Interesting. I, uh, okay, that's a strong statement. I, I don't, I personally think it's something we will know eventually. Like there's no reason to me why the-

   25. DKDonald Knuth50:25

       Yeah.

   26. LFLex Fridman50:26

       ... workings of the human mind are not within the reach of science.

   27. DKDonald Knuth50:31

       That's absolutely possible and I'm not denying it.

   28. LFLex Fridman50:34

       Yeah.

   29. DKDonald Knuth50:35

       Uh, and, and, it, no-

   30. LFLex Fridman50:35

       But right now you don't have a good intuition one way or the other.
8. 57:14 – 1:10:01

   Conway's game of life

   1. DKDonald Knuth57:14

   2. LFLex Fridman57:14

      So, there's a tricky thing, I don't know if you have any expertise in this, you might be a little bit on the sideline, it'd be interesting to ask though, what are your thoughts on cellular automata and the Game of Life? Have you ever played with those kind of little, uh, games?

   3. DKDonald Knuth57:29

      I think, uh, The Game of Life, uh, it is- is wonderful and, uh, uh, and- and- and shows all kind of stuff about how things can evolve without the creator understanding anything more than the- the power of learning in a way. But to me, the most im- (laughs) important thing about The Game of Life is the- is- is how it focused for me what it- what it meant to have free will or not.

   4. LFLex Fridman58:03

      (laughs)

   5. DKDonald Knuth58:05

      Because The Game of Life is obviously totally deterministic.

   6. LFLex Fridman58:09

      Yes.

   7. DKDonald Knuth58:10

      And- and I- I find it hard to believe that anybody who's ever had children cannot believe in free will.

   8. LFLex Fridman58:16

      Right.

   9. DKDonald Knuth58:17

      On the other hand, this makes it crystal clear, uh, John Conway said, uh, he wondered whether it was im- immoral to shut the computer off after he got into a particularly interesting play of The Game of Life.

   10. LFLex Fridman58:36

       Yeah.

   11. DKDonald Knuth58:36

       Um...

   12. LFLex Fridman58:36

       Wow. Yeah, so there is... uh, to me, the reason I love The Game of Life is exactly as you said, a clear illustration that from simple initial conditions with simple rules, you know exactly how the system is operating, it's deterministic, and yet if you let yourself, uh, if- if you allow yourself to lose that knowledge a little bit enough to see the bigger organisms that emerge, and then all of a sudden they seem conscious, they- they seem, uh, not conscious but living.

   13. DKDonald Knuth59:11

       If- if- if the universe is finite, it- we're all living in The Game of Life, just slowed down, uh, I mean sped up a lot. Uh...

   14. LFLex Fridman59:21

       But do you think technically some of the ideas that you used for analysis of algorithms can be used to analyze The Game of Life? Can we make sense of it or is it too weird of a system?

   15. DKDonald Knuth59:33

       Yeah. I mean I- I've got- I've got a dozen exercises in volume four of Fascicle 6, uh, that actually work rather well for that purpose. (laughs)

   16. LFLex Fridman59:46

       But...

   17. DKDonald Knuth59:47

       Bill Gospers came up with the- with- with- with the algorithm that- that allows- that allowed Golly to- uh, to- you know, to run thousands and thousands of times faster, to get... you know the website called Golly?

   18. LFLex Fridman1:00:03

       Uh...

   19. DKDonald Knuth1:00:03

       G-O-L-L-Y, just-

   20. LFLex Fridman1:00:04

       It simulates the cellular automata, like Game of Life?

   21. DKDonald Knuth1:00:07

       Yeah, you got- you gotta check it out, yeah.

   22. LFLex Fridman1:00:10

       Can I ask you about John Conway?

   23. DKDonald Knuth1:00:12

       Yes. In fact, uh, I- I'm just reading now the- the issue of Mathematical Intelligence that came in last- last week. It's a whole issue devoted to- to (laughs) , uh, uh, you know, mem- remembrance of- of- of him. (clears throat)

   24. LFLex Fridman1:00:28

       Did you know him?

   25. DKDonald Knuth1:00:30

       I- I slept overnight in his house several times. I- (laughs) yeah.

   26. LFLex Fridman1:00:36

       He recently passed away.

   27. DKDonald Knuth1:00:38

       Yeah, he die- he died a year ago, um, May I think it was, of COVID.

   28. LFLex Fridman1:00:48

       What are you... what are some memories of him, of his work that stand out for you? Is... did- uh, did... on, o- on a technical level, did any of his work inspire you? On a personal level, did-

   29. DKDonald Knuth1:01:02

       (laughs)

   30. LFLex Fridman1:01:02

       ... did he himself inspire you in some way?
9. 1:10:01 – 1:13:21

   Stable marriage

   1. LFLex Fridman1:10:01

      So, you mentioned your wife, Jill. You mentioned stable marriage. Can you tell the story of how you two met?

   2. DKDonald Knuth1:10:09

      So we celebrated 60 years of wedded bliss, like, uh, last month (laughs) .

   3. LFLex Fridman1:10:14

      (laughs)

   4. DKDonald Knuth1:10:14

      And, and we met because of, uh, I was dating her roommate. This, this was my sophomore year or her freshman year, and I was dating her roommate and I wanted her advice on strategy or something like this. And anyway, I found I enjoyed her advice better (laughs) than, than her. I enjoyed her roommate.

   5. LFLex Fridman1:10:36

      (laughs) You guys were ma- majoring the same thing?

   6. DKDonald Knuth1:10:39

      No, no, no.

   7. LFLex Fridman1:10:40

      'Cause I, 'cause I read something about, uh, working on a com- computer in grad school on a difficult computer science topic.

   8. DKDonald Knuth1:10:49

      So, so, so she's an artist and I'm a-

   9. LFLex Fridman1:10:52

      Okay.

   10. DKDonald Knuth1:10:53

       ... and I'm a, a, you know, a geek and-

   11. LFLex Fridman1:10:55

       What was she doing with a computer science book? Or I read the... Was it the manual that she was reading? What was she reading?

   12. DKDonald Knuth1:11:02

       I wrote the manual that she had, had. She had to take a class in computer science.

   13. LFLex Fridman1:11:07

       Okay.

   14. DKDonald Knuth1:11:08

       And, and, and, uh-

   15. LFLex Fridman1:11:09

       So you're the tutor?

   16. DKDonald Knuth1:11:10

       No, no, yeah. No, we... Yeah, we... There were careful times, uh, uh, you know, trying to learn cer- certain concept. But I learned art from her. And so we, we worked together, uh, you know, occasionally in design pro- projects. But, but every year we, we write a Christmas card and, and we each have to compromise our, our own s-

   17. LFLex Fridman1:11:38

       (laughs)

   18. DKDonald Knuth1:11:38

       ... notions of beauty. (laughs)

   19. LFLex Fridman1:11:39

       Yes. Uh, when did you fall in love with her?

   20. DKDonald Knuth1:11:45

       That day that I asked her about her, her roommate. (laughs)

   21. LFLex Fridman1:11:50

       (laughs) Okay.

   22. DKDonald Knuth1:11:50

       I mean-

   23. LFLex Fridman1:11:51

       You, you-

   24. DKDonald Knuth1:11:51

       No, I, I, I... Okay, so you're... I, I don't mind telling these things, uh, depending on how you far- how far you go, but, uh-

   25. LFLex Fridman1:12:00

       (laughs)

   26. DKDonald Knuth1:12:01

       ... but, but, but let, let me tell-

   27. LFLex Fridman1:12:03

       I promise, I promise not to go too far. (laughs)

   28. DKDonald Knuth1:12:05

       ... let, let me tell you this, that I, I never really enjoyed kissing, uh, uh, uh, until I found how she did it.

   29. LFLex Fridman1:12:14

       (laughs) Wow. And 60 years.

   30. DKDonald Knuth1:12:18

       Yeah.
10. 1:13:21 – 1:24:15

    Richard Feynman

    1. LFLex Fridman1:13:21

       uh, you mentioned that Richard Feynman was someone you looked up to.

    2. DKDonald Knuth1:13:25

       Yep.

    3. LFLex Fridman1:13:26

       Um, probably you've met him in Caltech?

    4. DKDonald Knuth1:13:30

       Uh, well, we knew each other th- th- yeah, at Caltech for sure. Yeah, I- I-

    5. LFLex Fridman1:13:35

       Uh, you are one of the seminal personalities of computer science. He's one for physics.

    6. DKDonald Knuth1:13:42

       Yep.

    7. LFLex Fridman1:13:42

       Have you ever ... Hav- is there specific things you picked up from him by way of inspiration or, uh-

    8. DKDonald Knuth1:13:49

       So, so we used to go to each other's lectures and s- and, and, uh, but, uh, but if I saw him sitting in the front row (laughs) it would throw me for a loop actually and I, I, I would, I would miss a few, a few sentences. Oh, what unique story do I have about ... I mean, I, I, I've s- ... You know, I, I, I, I often refer to his, his time in Brazil, uh, where he, um, es- essentially s- said they were teaching all the physics students the wrong way. They were just bl- they were just learning how to pass exams and not learning any physics and s- ... And he said, uh, tu- ... You know, "If you want me to prove it," you know, "here, I'll turn to any page of this textbook and, uh, a- a- and I'll tell you what's wrong with this page." And, and, and he did so. And, and the textbook had been written by his host and, (laughs) and he, and it was, uh, a big embarrassing incident. But he had previously asked his host if, if he was supposed to tell the truth. Um, eh, but, but anyway, it, it re- epitomizes the way, uh, uh, e- education goes wrong, uh, in all kinds of fields-

    9. LFLex Fridman1:14:58

       Mm-hmm.

    10. DKDonald Knuth1:14:58

        ... uh, and has to periodically b- be brought back f- from h- from, from a process of m- of giving credentials to a process of giving knowledge. (clears throat)

    11. LFLex Fridman1:15:10

        Yeah, it's probably a story that continues to this day in, in a bunch of places where it's too easy for, uh, educational institutions to fall into credentialism versus, uh, ins- inspirationalism. (laughs)

    12. DKDonald Knuth1:15:27

        Mm-hmm.

    13. LFLex Fridman1:15:28

        I don't know if those are words but sort of, uh-

    14. DKDonald Knuth1:15:30

        Yeah, uh-

    15. LFLex Fridman1:15:31

        ... understanding versus just giving a little, um, uh-

    16. DKDonald Knuth1:15:35

        It, it, it, it-

    17. LFLex Fridman1:15:36

        ... plaque.

    18. DKDonald Knuth1:15:37

        ... uh, and, you know, it, it's a, it's very much like what we were talking about if you want the computer to (laughs) ... If you want to be, be able to believe the answer a computer is-

    19. LFLex Fridman1:15:46

        Sure.

    20. DKDonald Knuth1:15:47

        ... uh, is doing. That, w- one of the things Bob Floyd showed me in the '60s, there was a, uh, h- he loved this cartoon. There was a ... There, there, there were two m- guys standing in front of ... In those days, a computer was a big thing, you know, and the-

    21. LFLex Fridman1:16:01

        Okay.

    22. DKDonald Knuth1:16:01

        And, and the first guy says to the other guy, he said, "This machine can do in one second what it would take, uh, a million people to do in 100 years." And the other guy says, "Oh, so how do you know it's right?"

    23. LFLex Fridman1:16:16

        (laughs) Ah, that's a good line.

    24. DKDonald Knuth1:16:19

        Mm-hmm.

    25. LFLex Fridman1:16:19

        Uh, (laughs) d- is there some interesting distinction between physics and math to you? H- have you looked at physics much to, like, speaking of Richard Feynman? So, uh, th- the difference between the physics community, the physics way of thinking, the physics intuition versus the computer science, the theoretical computer science, the mathematical sciences. Do you see that as a gap? Are they strongly overlapping?

    26. DKDonald Knuth1:16:44

        Y- I, uh, it's quite different, I, uh, i- in my opinion. I, um, I started as a physics major and I switched into math, uh, and p- probably the reason was that I could, I could get A+ on the physics exam but I'd, but I never had any idea why I would (laughs) have been able to come up with the problems that were on those exams.

    27. LFLex Fridman1:17:06

        Mm-hmm.

    28. DKDonald Knuth1:17:06

        Uh, but, but in math, uh, I, I, I, I knew wh- you know, why the teacher set those problems and I thought of other problems that I could s- do.

    29. LFLex Fridman1:17:16

        Mm-hmm.

    30. DKDonald Knuth1:17:16

        And I believe it's, it's quite a different mentality. Uh-
11. 1:24:15 – 1:33:47

    Knuth-Morris-Pratt Algorithm

    1. LFLex Fridman1:24:16

       Can you describe what the, uh, Knuth-Morris-Pratt algorithm does, and how did you come to develop it? One of the many things that you're known for and has your name attached to it.

    2. DKDonald Knuth1:24:29

       Yeah. All right. So it should be actually Morris-Pratt-Knuth-

    3. LFLex Fridman1:24:34

       (laughs)

    4. DKDonald Knuth1:24:35

       ... but we decided to use alphabetical order when we published the paper. The problem is, uh, something that everybody knows now if they're, if they're using a search engine, uh, uh, you k- you have a, a large collection of texts, and, and you wanna know if, if the word Knuth appears anywhere in the text we'll say, or, or some, some other word that's less interesting than Knuth.

    5. LFLex Fridman1:25:03

       (laughs)

    6. DKDonald Knuth1:25:03

       Okay? But anyway, like, like-

    7. LFLex Fridman1:25:04

       That's the most interesting word, yeah.

    8. DKDonald Knuth1:25:05

       ... Morris or something.

    9. LFLex Fridman1:25:06

       Like Morris, right. (laughs)

    10. DKDonald Knuth1:25:07

        So anyway, we have, we have, uh, a large piece of text, and, and it, it's all one long one-dimensional thing, you know? It's first letter, second letter, and et cetera, et cetera, et cetera. And so, uh, the, the ques- uh, uh, you would like to be able to do this quickly. Um-And the obvious way is, uh, cl- let's say we're looking for Morris (soft music plays) , then, okay, go there. So we would, we would go through and wait till we get to letter M. Then we look at the next word and, uh, sure enough, it's an O, and then a- an R. But then there, oh, oop, too bad, um, you know, the next letter is, is E.

Episode duration: 2:21:26