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

1. 0:00 – 15:00

   The following is a…

   1. LFLex Fridman0: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. 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.

   2. DKDonald Knuth4:00

      Yeah.

   3. LFLex Fridman4:00

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

   4. DKDonald Knuth4: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...

   5. LFLex Fridman4:50

      (laughs)

   6. DKDonald Knuth4: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-

   7. LFLex Fridman5:10

      In resources.

   8. DKDonald Knuth5:11

      ... uh, in memory.

   9. LFLex Fridman5:12

      Yeah.

   10. DKDonald Knuth5: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-

   11. LFLex Fridman5:30

       Still pretty fast. It's... The memory is the constraint, the memory is the problem.

   12. DKDonald Knuth5: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-

   13. LFLex Fridman6:17

       Ooh.

   14. DKDonald Knuth6: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 ...

   15. LFLex Fridman6:31

       Could you have predicted the future 60 years later of computing-

   16. DKDonald Knuth6:36

       No.

   17. LFLex Fridman6:36

       ... from then?

   18. DKDonald Knuth6:37

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

   19. LFLex Fridman6:44

       Mm-hmm.

   20. DKDonald Knuth6: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-

   21. LFLex Fridman6:52

       (laughs)

   22. DKDonald Knuth6: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.

   23. LFLex Fridman7:19

       Mm-hmm.

   24. DKDonald Knuth7:19

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

   25. LFLex Fridman7:25

       It's the first mass market-

   26. DKDonald Knuth7:27

       ... maybe a couple of dozen.

   27. LFLex Fridman7:27

       ... mass produced.

   28. DKDonald Knuth7: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.

   29. LFLex Fridman7:44

       Mm-hmm.

   30. DKDonald Knuth7:44

       And, and so that's why, uh, uh, a lot of students learned about computers at that time.
2. 15:00 – 30:00

   And you're okay with…

   1. DKDonald Knuth15:00

      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-

   2. LFLex Fridman15:13

      And you're okay with that?

   3. DKDonald Knuth15:14

      And not only that, I th-

   4. LFLex Fridman15:16

      Thrive in it.

   5. DKDonald Knuth15:16

      I wish ... You know, I want my kids to be that way.

   6. LFLex Fridman15:18

      (laughs)

   7. DKDonald Knuth15:19

      I want them, et cetera, you know?

   8. LFLex Fridman15:20

      Yeah.

   9. DKDonald Knuth15: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.

   10. LFLex Fridman15:28

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

   11. DKDonald Knuth15:36

       Yeah, that-

   12. LFLex Fridman15:36

       ... you know, literature.

   13. DKDonald Knuth15:37

       That's true. You know more about me than I do, but I, I'll-

   14. LFLex Fridman15:39

       That's true.

   15. DKDonald Knuth15:39

       ... try to be consistent with what you read.

   16. LFLex Fridman15:41

       Yeah, no, just believe me. I, uh ...

   17. DKDonald Knuth15:43

       (laughs)

   18. LFLex Fridman15:44

       Just go with whatever story I tell you.

   19. DKDonald Knuth15:45

       (laughs)

   20. LFLex Fridman15:45

       It'll be easier that way. The conversation will be easier (laughs) .

   21. DKDonald Knuth15:47

       Right, yeah, no, that's true. Yep, yep.

   22. LFLex Fridman15: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?

   23. DKDonald Knuth16:07

       Yeah, okay. Good, good question. So I, so I, I, I met Roth, uh, uh-

   24. LFLex Fridman16:12

       Oh, really?

   25. DKDonald Knuth16:13

       ... well, we both got doctorates from Harvard on the same day, so (laughs) -

   26. LFLex Fridman16:17

       Okay.

   27. DKDonald Knuth16: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-

   28. LFLex Fridman16:26

       (laughs)

   29. DKDonald Knuth16:27

       All right, so you say you, you, uh, you, uh, y- you were a teenager when you left Russia, so-

   30. LFLex Fridman16:33

       Mm-hmm.
3. 30:00 – 45:00

   And arithmetic in the…

   1. DKDonald Knuth30:00

      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.

   2. LFLex Fridman30:37

      And arithmetic in the way a computer would think about arithmetic, so floating point-

   3. DKDonald Knuth30: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-

   4. LFLex Fridman30:53

      I like that one, sort and search.

   5. DKDonald Knuth30:55

      Sorting and searching. Yeah.

   6. LFLex Fridman30:56

      I love sorting.

   7. DKDonald Knuth30: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.

   8. LFLex Fridman31:45

      Mm-hmm.

   9. DKDonald Knuth31: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-

   10. LFLex Fridman32:09

       Well, like, it's a s-

   11. DKDonald Knuth32:10

       It's true-

   12. LFLex Fridman32:10

       ... satisfiability too.

   13. DKDonald Knuth32: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.

   14. LFLex Fridman32:22

       Ah.

   15. DKDonald Knuth32: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.

   16. LFLex Fridman33:01

       Uh, do you like the most of the domain of graphs and graph theory?

   17. DKDonald Knuth33:05

       Graphs are great because they're, they're, they're, they're terrific models of so many things in the real world-

   18. LFLex Fridman33:10

       Right.

   19. DKDonald Knuth33: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-

   20. LFLex Fridman33:48

       That's volume four.

   21. DKDonald Knuth33:50

       That's volume four. Uh-

   22. LFLex Fridman33:52

       What does the future hold?

   23. DKDonald Knuth33: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.

   24. LFLex Fridman34:10

       Mm-hmm.

   25. DKDonald Knuth34: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-

   26. LFLex Fridman35:33

       Right.

   27. DKDonald Knuth35: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-

   28. LFLex Fridman36:21

       (laughs)

   29. DKDonald Knuth36: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. And s-

   30. LFLex Fridman36:49

       What kind of problems were occupying people's minds? What ki- kind of problems in combinatorics? Was it s- sat-
4. 45:00 – 1:00:00

   Uh- …

   1. LFLex Fridman45:00

      write, uh, macros ...

   2. DKDonald Knuth45:02

      Uh-

   3. LFLex Fridman45:02

      You don't think in macros?

   4. DKDonald Knuth45:04

      Not particularly. But when I need a macro, I'll, uh, uh, I'll go ahead and-

   5. LFLex Fridman45:08

      Use it.

   6. DKDonald Knuth45: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.

   7. LFLex Fridman45:17

      Mm-hmm.

   8. DKDonald Knuth45: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.

   9. LFLex Fridman45:24

      Mm-hmm.

   10. DKDonald Knuth45: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-

   11. LFLex Fridman45:33

       And it could also be argued that that is what life is about.

   12. DKDonald Knuth45: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 ...

   13. LFLex Fridman45:52

       So, you know, a lot of writers talk about, you know, basically suffering. The writing process is-

   14. DKDonald Knuth45:58

       Yeah.

   15. LFLex Fridman45: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?

   16. DKDonald Knuth46:18

       T-

   17. LFLex Fridman46:18

       You, you kind of say it's, you know-

   18. DKDonald Knuth46:21

       Oh, yeah.

   19. LFLex Fridman46:21

       ... it's fun, (laughs) but it'd be interesting to hear if-

   20. DKDonald Knuth46:27

       Well, yeah, that's true.

   21. LFLex Fridman46:27

       ... if there are non-fun parts that you really struggle with.

   22. DKDonald Knuth46: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) -

   23. LFLex Fridman47:03

       Yeah.

   24. DKDonald Knuth47: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.

   25. LFLex Fridman47:26

       Is there ever dead ends?

   26. DKDonald Knuth47: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.

   27. LFLex Fridman47:46

       Yes.

   28. DKDonald Knuth47: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.

   29. LFLex Fridman47:53

       Okay, yeah.

   30. DKDonald Knuth47: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.
5. 1:00:00 – 1:15:00

   Ah. …

   1. DKDonald Knuth1:00:00

      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.

   2. LFLex Fridman1:00:48

      Ah.

   3. DKDonald Knuth1: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.

   4. LFLex Fridman1:01:36

      Mm-hmm.

   5. DKDonald Knuth1: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.

   6. LFLex Fridman1:01:47

      Mm-hmm.

   7. DKDonald Knuth1:01:48

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

   8. LFLex Fridman1:01:53

      Mm-hmm.

   9. DKDonald Knuth1: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.

   10. LFLex Fridman1:02:13

       Mm-hmm.

   11. DKDonald Knuth1: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-

   12. LFLex Fridman1:02:39

       Mm-hmm.

   13. DKDonald Knuth1: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.

   14. LFLex Fridman1:02:54

       Mm-hmm.

   15. DKDonald Knuth1: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.

   16. LFLex Fridman1: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)

   17. DKDonald Knuth1:03:17

       It, and they proved in this-

   18. LFLex Fridman1:03:19

       It's very surprising.

   19. DKDonald Knuth1: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-

   20. LFLex Fridman1:03:25

       Because that's for any arbitrary class. So it's for any class-

   21. DKDonald Knuth1:03:28

       A- any arbitrary class that's closed under taking minors.

   22. LFLex Fridman1:03:31

       That's closed under... Maybe I'm not understanding.

   23. DKDonald Knuth1:03:33

       If, if, if, if-

   24. LFLex Fridman1:03:33

       Because it seems like a lot of them are closed under taking minors.

   25. DKDonald Knuth1: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.

   26. LFLex Fridman1:03:47

       Right.

   27. DKDonald Knuth1: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-

   28. LFLex Fridman1:03:58

       So why do you bring up this theorem, uh, or this proof?

   29. DKDonald Knuth1: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.

   30. LFLex Fridman1:04:12

       Mm-hmm.
6. 1:15:00 – 1:27:09

   Right. …

   1. DKDonald Knuth1:15:00

      I, I, I smash a certain ant and organism. "Hmm. That stung. What was that?"

   2. LFLex Fridman1:15:06

      Right.

   3. DKDonald Knuth1: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.

   4. LFLex Fridman1:15:30

      But even a simpler version of that, what are your thoughts of maybe Conway's Game of Life?

   5. DKDonald Knuth1: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-

   6. LFLex Fridman1:15:46

      I like how you went there. I mean, that's not its most powerful thing, I would say. I mean, um-

   7. DKDonald Knuth1:15:55

      But-

   8. LFLex Fridman1:15:55

      It can simulate it, but the, the magic is that the individual units are distributed.

   9. DKDonald Knuth1:16:01

      Yes.

   10. LFLex Fridman1:16:02

       And extremely simple.

   11. DKDonald Knuth1:16:03

       Yes. We, we understand exactly what the primitives are.

   12. LFLex Fridman1:16:06

       The primitives. Just like with the ant colony-

   13. DKDonald Knuth1:16:08

       But-

   14. LFLex Fridman1:16:08

       ... even simpler though.

   15. DKDonald Knuth1: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?

   16. LFLex Fridman1:16:35

       Do you think God plays dice?

   17. DKDonald Knuth1: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-

   18. LFLex Fridman1:17:02

       When the algorithm requires it, uh-

   19. DKDonald Knuth1:17:05

       Yeah.

   20. LFLex Fridman1:17:05

       ... I don't ... You don't see why the-

   21. DKDonald Knuth1:17:07

       Yeah.

   22. LFLex Fridman1:17:08

       ... physics should constrain it. Um-

   23. DKDonald Knuth1:17:11

       Yeah.

   24. LFLex Fridman1:17:11

       So in 2001, you gave a series of lectures at MIT about religion and science.

   25. DKDonald Knuth1:17:17

       No, that was 1999. But-

   26. LFLex Fridman1:17:19

       You published a ... Sorry.

   27. DKDonald Knuth1:17:20

       The book came out in 2001.

   28. LFLex Fridman1:17:22

       In 2000. So in 1999, you spent a little bit of time in Boston enough to give, uh, those lectures.

   29. DKDonald Knuth1:17:29

       Yeah.

   30. LFLex Fridman1: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-

Episode duration: 1:45:55