Lex Fridman PodcastDonald Knuth: Algorithms, Complexity, and The Art of Computer Programming | Lex Fridman Podcast #62
EVERY SPOKEN WORD
150 min read · 30,195 words- 0:00 – 3:45
Introduction
- LFLex Fridman
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.
- 3:45 – 7:51
IBM 650
- LFLex Fridman
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.
- DKDonald Knuth
Yeah.
- LFLex Fridman
Can you take me back to that moment with the IBM 650? What, what was it that grabbed you about that computer?
- DKDonald Knuth
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...
- LFLex Fridman
(laughs)
- DKDonald Knuth
... 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-
- LFLex Fridman
In resources.
- DKDonald Knuth
... uh, in memory.
- LFLex Fridman
Yeah.
- DKDonald Knuth
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-
- LFLex Fridman
Still pretty fast. It's... The memory is the constraint, the memory is the problem.
- DKDonald Knuth
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-
- LFLex Fridman
Ooh.
- DKDonald Knuth
... 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 ...
- LFLex Fridman
Could you have predicted the future 60 years later of computing-
- DKDonald Knuth
No.
- LFLex Fridman
... from then?
- DKDonald Knuth
No. Y- you know, in fact, the hardest question I was ever asked was, uh, "What could I have predicted?"
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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-
- LFLex Fridman
(laughs)
- DKDonald Knuth
... 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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
And before that, there were, you know, there was, uh, each machine there might be a half a dozen examples, maybe, maybe-
- LFLex Fridman
It's the first mass market-
- DKDonald Knuth
... maybe a couple of dozen.
- LFLex Fridman
... mass produced.
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
And, and so that's why, uh, uh, a lot of students learned about computers at that time.
- 7:51 – 12:29
Geeks
- DKDonald Knuth
- LFLex Fridman
So you-
- DKDonald Knuth
Mm-hmm.
- LFLex Fridman
... 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.
- DKDonald Knuth
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-
- LFLex Fridman
(laughs)
- DKDonald Knuth
... structured in a certain way that, that resonates with, with computers.
- LFLex Fridman
So there's this space of people, it's 2% of the population, you empirically estimate.
- DKDonald Knuth
That, that's a per- per- that's been-
- LFLex Fridman
Proven? (laughs)
- DKDonald Knuth
... fairly constant over most of my career. However, uh, it might be different now because kids have different experiences when they're young.
- LFLex Fridman
So-
- DKDonald Knuth
I'm just saying. (clears throat)
- LFLex Fridman
... what does the world look like to a geek? What is, what is this aspect-
- DKDonald Knuth
(clears throat)
- LFLex Fridman
... of thinking that is, uh, unique to, uh-
- DKDonald Knuth
That makes, they, yeah.
- LFLex Fridman
... that makes a geek?
- DKDonald Knuth
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-"
- LFLex Fridman
(laughs)
- DKDonald Knuth
"... and for an interview," or something like this.
- LFLex Fridman
Right.
- DKDonald Knuth
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-
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
... of an equation or something-
- LFLex Fridman
The algorithm.
- DKDonald Knuth
... 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-
- LFLex Fridman
Yeah.
- DKDonald Knuth
... 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-
- LFLex Fridman
Mm-hmm.
- 12:29 – 14:26
Alan Turing
- LFLex Fridman
... What influence has Turing had on you? What-
- DKDonald Knuth
Well, okay, so-
- LFLex Fridman
... in your way of thinking?
- DKDonald Knuth
... 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-
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
... 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-
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
... 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-
- LFLex Fridman
Hmm.
- DKDonald Knuth
... 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.
- LFLex Fridman
What do you mean left to right?
- DKDonald Knuth
He would write pi (laughs) as, you know, 9514.3.
- LFLex Fridman
Oh, wow.
- DKDonald Knuth
I mean, okay?
- LFLex Fridman
Okay. (laughs)
- DKDonald Knuth
Uh, uh-
- LFLex Fridman
Right. Uh, got it.
- DKDonald Knuth
... 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.
- LFLex Fridman
Trained himself to think like a computer?
- DKDonald Knuth
Yeah.
- LFLex Fridman
Well, there you go. That's-
- DKDonald Knuth
Mm-hmm.
- LFLex Fridman
... that's geek thinking.
- DKDonald Knuth
Yeah.
- 14:26 – 24:00
My life is a convex combination of english and mathematics
- DKDonald Knuth
- LFLex Fridman
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.
- DKDonald Knuth
Abs- ... Yeah, absolutely the-
- LFLex Fridman
So how do you see those two as conflicting, as the-
- DKDonald Knuth
Well-
- LFLex Fridman
... formalism of theory, and the idea of literate programming?
- DKDonald Knuth
So there, there we are in a non-uniform system where I don't-
- LFLex Fridman
(laughs)
- DKDonald Knuth
... 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-
- LFLex Fridman
And you're okay with that?
- DKDonald Knuth
And not only that, I th-
- LFLex Fridman
Thrive in it.
- DKDonald Knuth
I wish ... You know, I want my kids to be that way.
- LFLex Fridman
(laughs)
- DKDonald Knuth
I want them, et cetera, you know?
- LFLex Fridman
Yeah.
- DKDonald Knuth
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.
- LFLex Fridman
And I've heard that you didn't really read for pleasure until into your 30s, and-
- DKDonald Knuth
Yeah, that-
- LFLex Fridman
... you know, literature.
- DKDonald Knuth
That's true. You know more about me than I do, but I, I'll-
- LFLex Fridman
That's true.
- DKDonald Knuth
... try to be consistent with what you read.
- LFLex Fridman
Yeah, no, just believe me. I, uh ...
- DKDonald Knuth
(laughs)
- LFLex Fridman
Just go with whatever story I tell you.
- DKDonald Knuth
(laughs)
- LFLex Fridman
It'll be easier that way. The conversation will be easier (laughs) .
- DKDonald Knuth
Right, yeah, no, that's true. Yep, yep.
- LFLex Fridman
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?
- 24:00 – 25:42
Japanese arrow puzzle example
- LFLex Fridman
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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."
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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.
- LFLex Fridman
That's really interesting.
- 25:42 – 27:59
Neural networks and machine learning
- LFLex Fridman
So, maybe an extension of that, there has been a resurgence in computer science and machine learning and, uh, neural networks.
- DKDonald Knuth
Yeah.
- LFLex Fridman
So, using data to construct algorithms, so it's another way to construct algorithms, really.
- DKDonald Knuth
Yes, exactly.
- LFLex Fridman
If you can think of it that way.
- DKDonald Knuth
Yeah, yeah.
- LFLex Fridman
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?
- DKDonald Knuth
It seems to be, um, suited to a certain kind of non-geek, uh (laughs) -
- LFLex Fridman
(laughs) Sure, sure.
- DKDonald Knuth
... and which, which is probably why it's, it's, uh, uh, it's taken off. The... It has its own community-
- LFLex Fridman
Got you.
- DKDonald Knuth
... 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.
- LFLex Fridman
That's a really interesting thought that it's, uh, it makes algorithms more accessible to a different community, a different type of brain.
- DKDonald Knuth
Yep.
- LFLex Fridman
And that's really interesting because, uh, just like literal programming, perhaps could make programming more accessible to a certain kind of brain.
- DKDonald Knuth
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-
- LFLex Fridman
(laughs)
- DKDonald Knuth
... 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)
- LFLex Fridman
Physicists. (laughs)
- DKDonald Knuth
Yeah.
- LFLex Fridman
So,
- 27:59 – 36:49
The Art of Computer Programming
- LFLex Fridman
let's go to, uh, The Art of Computer Programming. In 1962, you set the table of contents for this, uh, magnum opus, right?
- DKDonald Knuth
Yep.
- LFLex Fridman
It was supposed to be a single book with 12 chapters. Now, today, what is it? F- f- fifty, uh, seven years later-
- DKDonald Knuth
(laughs)
- LFLex Fridman
... you're in the middle of volume four of seven, uh-
- DKDonald Knuth
In the middle of volume 4B is-
- LFLex Fridman
4B.
- DKDonald Knuth
... more precisely.
- LFLex Fridman
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.
- DKDonald Knuth
(laughs) Elevator, that's great.
- LFLex Fridman
(laughs)
- DKDonald Knuth
Yeah, right.
- LFLex Fridman
Well, depending how many floors there are in the building, of course.
- DKDonald Knuth
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.
- LFLex Fridman
Induction.
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
Okay. And so I need math for that. And then there's, uh, the standard way to structure data inside and represent-
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
... 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.
- LFLex Fridman
And arithmetic in the way a computer would think about arithmetic, so floating point-
- DKDonald Knuth
Floating point arithmetic, high precision arithmetic. Not only addition, subtraction, multiplication, but also comparison of numbers. So then ch- then volume three talks about-
- LFLex Fridman
I like that one, sort and search.
- DKDonald Knuth
Sorting and searching. Yeah.
- LFLex Fridman
I love sorting.
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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-
- LFLex Fridman
Well, like, it's a s-
- DKDonald Knuth
It's true-
- 36:49 – 39:16
Combinatorics
- DKDonald Knuth
And s-
- LFLex Fridman
What kind of problems were occupying people's minds? What ki- kind of problems in combinatorics? Was it s- sat-
- DKDonald Knuth
Graph theory.
- LFLex Fridman
... satisfiability? Graph theory?
- DKDonald Knuth
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-
- LFLex Fridman
Travel salesman.
- DKDonald Knuth
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.
- LFLex Fridman
So how did it continue to change from the '70s to today?
- DKDonald Knuth
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.
- 39:16 – 42:10
Writing process
- DKDonald Knuth
- LFLex Fridman
So what's your writing process like? What's your thinking and writing process like every day?
- DKDonald Knuth
So, um-
- LFLex Fridman
What's your routine even?
- DKDonald Knuth
My... yeah, I guess it's actually a the best question because I spend seven days a week-
- LFLex Fridman
(laughs)
- DKDonald Knuth
... (laughs) doing it. Uh-
- LFLex Fridman
You're the most prepared to answer it. Yeah.
- DKDonald Knuth
Uh, yeah. But, um, okay, so, uh, uh, the chair I'm sitting in is where I do... (laughs)
- LFLex Fridman
It's where the magic happens? (laughs)
- DKDonald Knuth
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...
- LFLex Fridman
But...
- DKDonald Knuth
Uh, I'm standing up.
- LFLex Fridman
The kernel of the idea is first put on paper.
- DKDonald Knuth
Yep.
- LFLex Fridman
That's where...
- DKDonald Knuth
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
- 42:10 – 48:36
Are some days harder than others?
- DKDonald Knuth
to shoot me.
- LFLex Fridman
(laughs) Well, so in the process, in that one month process, are some days harder than others?
- DKDonald Knuth
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 ...
- LFLex Fridman
Wow.
- DKDonald Knuth
... where, where I do the first, y- y- you know, the first writing, uh, of, of concepts. Okay? So, so, um-
- LFLex Fridman
And what language is that then? (laughs)
- DKDonald Knuth
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-
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
... 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.
- LFLex Fridman
And a very small space between lines.
- DKDonald Knuth
Small spaces, yeah, yeah. Take a look.
- LFLex Fridman
Do you mind if I maybe, uh, also just show it? (laughs) .
- DKDonald Knuth
Yeah. Sure.
- LFLex Fridman
Yeah. Wow.
- DKDonald Knuth
S- you know, I've got these manuscripts going back to the '60s.
- LFLex Fridman
Get you out of ... yeah, yeah.
- DKDonald Knuth
(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.
- LFLex Fridman
Okay.
- DKDonald Knuth
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.
- LFLex Fridman
And you type in tech?
- DKDonald Knuth
And I type in tech, yeah.
- LFLex Fridman
And can you s- can you think in tech?
- DKDonald Knuth
No.
- LFLex Fridman
So-
- DKDonald Knuth
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-
- LFLex Fridman
In the way that it's on paper here?
- DKDonald Knuth
... it's ... yeah, right. And-
- LFLex Fridman
So for example, Turing wrote, what, The Other Direction.
- DKDonald Knuth
Mm-hmm.
- LFLex Fridman
You don't write, uh, macros ...
- 48:36 – 50:21
What's the "Art" in the Art of Computer Programming
- LFLex Fridman
... 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?
- DKDonald Knuth
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-
- LFLex Fridman
(laughs) Right.
- DKDonald Knuth
... 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.
- LFLex Fridman
But there's an element-
- DKDonald Knuth
(laughs)
- LFLex Fridman
... of fine art and beauty. You are one who-
- DKDonald Knuth
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.
- LFLex Fridman
So,
- 50:21 – 55:06
Binary (boolean) decision diagram
- LFLex Fridman
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?
- DKDonald Knuth
Okay. All right.
- LFLex Fridman
That, that changed the way you see a space of problems?
- DKDonald Knuth
Yeah. Okay. I get a surprise every time I have a bug in my program obviously.
- LFLex Fridman
(laughs)
- DKDonald Knuth
But that, but, but that isn't really what you're... Uh, y- y- you're looking for the-
- LFLex Fridman
More transformational than less-
- DKDonald Knuth
Right. So-
- LFLex Fridman
... than surprising.
- DKDonald Knuth
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-
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
... 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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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...
- LFLex Fridman
So, newly invented data structures or ways to represent...
- DKDonald Knuth
Uh, a wh- a whole new class of algorithm.
- LFLex Fridman
A whole new class of algorithm?
- DKDonald Knuth
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.
- LFLex Fridman
(laughs)
- DKDonald Knuth
I'm, I'm sure that the theoreticians are... In the next 10 years are gonna show why machine learning doesn't solve everything.
- LFLex Fridman
Right.
- DKDonald Knuth
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.
- LFLex Fridman
Yeah.
- DKDonald Knuth
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.
- LFLex Fridman
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.
- DKDonald Knuth
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)
- LFLex Fridman
So
- 55:06 – 58:02
Big-O notation
- LFLex Fridman
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?
- DKDonald Knuth
S-
- LFLex Fridman
And notation too.
- DKDonald Knuth
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-
- LFLex Fridman
Right.
- DKDonald Knuth
... 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-
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
... 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) -
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
... 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.
- LFLex Fridman
Right.
- DKDonald Knuth
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.
- LFLex Fridman
So, have there been algorithms in your journey that perform very differently in practice than they do in theory?
- DKDonald Knuth
Well, the worst case of a combinatorial algorithm is almost always, uh, horrible.
- LFLex Fridman
(laughs) .
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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.
- 58:02 – 1:10:05
P=NP
- DKDonald Knuth
- LFLex Fridman
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.
- DKDonald Knuth
Right.
- LFLex Fridman
Uh, can you explain your intuition here? Has it been changed? And in general on the difference-
- DKDonald Knuth
Yeah.
- LFLex Fridman
... between easy and difficult problems of P and NP and so on.
- DKDonald Knuth
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.
- LFLex Fridman
Or discover, yeah.
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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.
- LFLex Fridman
Wait, what's the game of Hex?
- DKDonald Knuth
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.
- LFLex Fridman
And how does capture occur just so I understand that?
- DKDonald Knuth
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.
- LFLex Fridman
Ah.
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
All right? And so you start with a planar graph and sh- shrink any edge to a point, it's still planar.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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-
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
... 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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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.
- LFLex Fridman
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)
- 1:10:05 – 1:13:26
Artificial intelligence
- LFLex Fridman
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-
- DKDonald Knuth
Mm-hmm.
- LFLex Fridman
... to now?
- DKDonald Knuth
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.
- LFLex Fridman
Are you yourself captivated by the possibility of creating ... of algorithms having, um, echoes of intelligence in them?
- DKDonald Knuth
Not as much as, as most of the people in the field, I guess I would say.
- LFLex Fridman
Right.
- DKDonald Knuth
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-
- LFLex Fridman
Right.
- DKDonald Knuth
... 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-
- LFLex Fridman
(laughs)
- DKDonald Knuth
... 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.
- LFLex Fridman
Do you think it's possible to create without understanding?
- DKDonald Knuth
Yeah.
- LFLex Fridman
So to, uh-
- DKDonald Knuth
Oh, I, I do that all the time too. I mean ...
- LFLex Fridman
(laughs) Right.
- DKDonald Knuth
I mean, that's why I use random numbers. I, I, I-
- LFLex Fridman
Yeah.
- DKDonald Knuth
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.
- LFLex Fridman
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.
- DKDonald Knuth
Uh-huh.
- LFLex Fridman
And for the most part, uh, you, you mentioned ...
- DKDonald Knuth
It's only because I set the table of contents in 1962, you have to remember.
- LFLex Fridman
(laughs) For sure. There's no, uh-
- DKDonald Knuth
I'm glad I didn't wait until 1965 or ... (laughs)
- LFLex Fridman
(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-
- DKDonald Knuth
Yeah.
- LFLex Fridman
... uh, um, I'm glad the, uh, the table of contents for, uh, the, The Art of Computer Programming is what it is.
- 1:13:26 – 1:17:11
Ant colonies and human cognition
- LFLex Fridman
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-
- DKDonald Knuth
Yeah.
- LFLex Fridman
... distributed systems. So what do you think-
- DKDonald Knuth
Sure.
- LFLex Fridman
... is the difference between the way, um, Don Knuth would sort a list and an ant colony would sort a list or-
- DKDonald Knuth
Well, yeah.
- LFLex Fridman
... perform an algorithm?
- DKDonald Knuth
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 ...
- LFLex Fridman
It sounds, it sounds strong.
- DKDonald Knuth
Yeah, I mean, you know, I ... Okay, uh, uh, I, I, I smash a certain ant and organism. "Hmm. That stung. What was that?"
- LFLex Fridman
Right.
- DKDonald Knuth
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.
- LFLex Fridman
But even a simpler version of that, what are your thoughts of maybe Conway's Game of Life?
- DKDonald Knuth
Okay, so Conway's Game of Life is, is able to simulate any, any computable process. And, and any deterministic process is, uh-
- LFLex Fridman
I like how you went there. I mean, that's not its most powerful thing, I would say. I mean, um-
- DKDonald Knuth
But-
- LFLex Fridman
It can simulate it, but the, the magic is that the individual units are distributed.
- DKDonald Knuth
Yes.
- LFLex Fridman
And extremely simple.
- DKDonald Knuth
Yes. We, we understand exactly what the primitives are.
- LFLex Fridman
The primitives. Just like with the ant colony-
- DKDonald Knuth
But-
- LFLex Fridman
... even simpler though.
- DKDonald Knuth
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?
- LFLex Fridman
Do you think God plays dice?
- DKDonald Knuth
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-
- LFLex Fridman
When the algorithm requires it, uh-
- DKDonald Knuth
Yeah.
- LFLex Fridman
... I don't ... You don't see why the-
- DKDonald Knuth
Yeah.
- 1:17:11 – 1:24:28
God and the Bible
- DKDonald Knuth
Yeah.
- LFLex Fridman
So in 2001, you gave a series of lectures at MIT about religion and science.
- DKDonald Knuth
No, that was 1999. But-
- LFLex Fridman
You published a ... Sorry.
- DKDonald Knuth
The book came out in 2001.
- LFLex Fridman
In 2000. So in 1999, you spent a little bit of time in Boston enough to give, uh, those lectures.
- DKDonald Knuth
Yeah.
- LFLex Fridman
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-
- DKDonald Knuth
Yeah.
- LFLex Fridman
... are defined by those ideas?
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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."
- LFLex Fridman
In this, uh, random approach of sampling the Bible-
- DKDonald Knuth
Mm-hmm, yeah.
- LFLex Fridman
... what did you learn about the, the most, uh, you know, central... Uh, one of the biggest accumulation of ideas in our community.
- DKDonald Knuth
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.
- LFLex Fridman
(laughs)
- DKDonald Knuth
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.
- LFLex Fridman
Mm-hmm.
- DKDonald Knuth
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)
- LFLex Fridman
Mm-hmm. So I would say it's, yeah, it's similar to the P equals NP discussion, uh...
- DKDonald Knuth
Yeah.
- LFLex Fridman
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?
- DKDonald Knuth
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.
- LFLex Fridman
(laughs)
- DKDonald Knuth
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.
- LFLex Fridman
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.
- DKDonald Knuth
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)
- LFLex Fridman
(laughs) Yeah, well said.
- 1:24:28 – 1:28:25
Reflection on life
- LFLex Fridman
Uh, if you were to run program analysis on your own life, uh, how did you do in terms of correctness, running time-
- DKDonald Knuth
Oh, yeah, them well-
- LFLex Fridman
... resource use, asymptotically speaking, of course.
- DKDonald Knuth
Okay, yeah. Well, I would say, (laughs) that question has not been asked me before.
- LFLex Fridman
(laughs)
- DKDonald Knuth
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 Enough, which was about a, uh, uh, you know, somebody had eight kids. Um, but, but, uh, I, I, I say .8 is enough, which means i- i- if I can have a way of rating happiness, I think it's good design that, uh, uh, to have, uh, to have an organism that's happy about 80% of the time. Um, and if, if it was 100% of the time, it would be like ev- like everybody's on drugs, and, and never, and, and, and, and, and, and everything collapses and nothing works because everybody's just too happy.
Episode duration: 1:45:55
Install uListen for AI-powered chat & search across the full episode — Get Full Transcript
Transcript of episode 2BdBfsXbST8
