Donald Knuth: Algorithms, TeX, Life, and The Art of Computer Programming

Donald Knuth is one of the greatest and most impactful computer scientists and mathematicians ever. He is the recipient in 1974 of the Turing Award, considered the Nobel Prize of computing. He is 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 the computational complexity of algorithms. He popularized asymptotic notation, that we all affectionately know as the big-O notation. He also created the TeX typesetting which most computer scientists, physicists, mathematicians, and scientists and engineers use to write technical papers and make them look beautiful. This conversation is part of the Artificial Intelligence podcast. If you would like to get more information about this podcast go to https://lexfridman.com/ai or connect with @lexfridman on Twitter https://twitter.com/lexfridman, LinkedIn https://www.linkedin.com/in/lexfridman/, Facebook https://www.facebook.com/lexfridman, Medium https://medium.com/@lexfridman, or YouTube https://www.youtube.com/lexfridman where you can watch the video versions of these conversations. If you enjoy the podcast, please rate it 5 stars on Apple Podcasts https://podcasts.apple.com/us/podcast/artificial-intelligence/id1434243584, follow on Spotify https://open.spotify.com/show/2MAi0BvDc6GTFvKFPXnkCL, or support it on Patreon https://www.patreon.com/lexfridman. This episode is presented by Cash App. Download it (App Store https://apps.apple.com/us/app/cash-app/id711923939, Google Play https://play.google.com/store/apps/details?id=com.squareup.cash&hl=en_US), use code “LexPodcast”. Episode Links: The Art of Computer Programming (book set) https://amzn.to/39kxRwB Here’s the outline of the episode. On some podcast players you should be able to click the timestamp to jump to that time. 00:00 – Introduction 03:45 – IBM 650 07:51 – Geeks 12:29 – Alan Turing 14:26 – My life is a convex combination of english and mathematics 24:00 – Japanese arrow puzzle example 25:42 – Neural networks and machine learning 27:59 – The Art of Computer Programming 36:49 – Combinatorics 39:16 – Writing process 42:10 – Are some days harder than others? 48:36 – What’s the “Art” in the Art of Computer Programming 50:21 – Binary (boolean) decision diagram 55:06 – Big-O notation 58:02 – P=NP 1:10:05 – Artificial intelligence 1:13:26 – Ant colonies and human cognition 1:17:11 – God and the Bible 1:24:28 – Reflection on life 1:28:25 – Facing mortality 1:33:40 – TeX and beautiful typography 1:39:23 – How much of the world do we understand? 1:44:17 – Question for God

Speaker names marked ? are inferred from speaking time and the show’s known hosts — they are not voice-verified.

• 0:00Lex 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 tech type setting system, which most computer scientists, physicists,

• 0:43Lex Fridman?

  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 big cramp 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.

• 1:28Lex Fridman?

  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 it five stars on Apple Podcasts, follow on Spotify, support on Patreon, or simply connect with me on Twitter at LexFriedman, spelled F-R-I-D-M-A-N.

• 2:10Lex Fridman?

  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.

• 2:55Lex Fridman?

  Broker services are provided by Cash App Investing, a subsidiary of Square and a 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 that 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.

• 3:40Lex Fridman?

  And now here's my conversation with Donald Knuth.

• 4:02Lex Fridman?

  In 1957, at Case Tech, you were once allowed to spend several evenings with an IBM 650 computer, as you've talked about in the past, and you fell in love with computing then. Can you take me back to that moment with the IBM 650? What was it that grabbed you about that computer?

• 4:26Speaker 02

  So the IBM 650 was this, this machine that, well, it didn't fill a room, but 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 I was a freshman. I had a job with the statistics group and I was supposed to punch cards and for data and then sort them on another machine. But then they got this new computer, came in and it had interesting lights, okay. So, well, but I had a key to the building, so I could get in and look at it and got

• 5:11Speaker 02

  a manual for it. And my first experience was based on the fact that I could punch cards, basically, which was a big thing for the, but the IBM 650 was, you know, big in size, but incredibly small in power.

• 5:28Lex Fridman?

  In resources.

• 5:29Speaker 02

  In memory. It had, it had 2,000 words of memory and a word of memory was 10 decimal digits plus a sign. And it would do, to add two numbers together, you could probably expect that would take, I'll say, three milliseconds.

• 5:47Lex Fridman?

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

• 5:51Speaker 02

  That was why it was, it took three milliseconds, because it took five milliseconds for the drum to go around. And you had to wait, I don't know, five cycle times. If you have an instruction, one position on the drum, then it would be ready to read the data for the instruction and you go three notches. The drum is 50 cycles around and you go three cycles 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, otherwise you spin until you get to the right place. And, and we had no random access memory whatsoever until my senior year. Senior year, we got 50 words of random access memory, which were, which were priceless.

• 6:36Speaker 02

  And we would, we would move stuff up to the. Up to the random access memory in sixty word chunks and then we would start again. So a subroutine wanted to go up there and.

• 6:48Lex Fridman?

  Could you have predicted the future sixty years later of computing from then?

• 6:54Speaker 02

  You know, in fact, the hardest question I was ever asked was, what could I have predicted? In other words, the interviewer asked me, she said, you know, what about computing has surprised you? You know, and immediately I ran, rattled off a couple dozen things and then she said, okay, so what didn't surprise? And I was, I tried for five minutes to think of something that I, that I would have predicted and I, and I couldn't. But let me say that this machine, I didn't know, well, it, there wasn't, there wasn't much else in the world at that time. The six fifty was the first machine that was, that there were more than a thousand of ever.

• 7:36Speaker 02

  Before that, there were, you know, there was, each machine there might be a half a dozen examples, maybe.

• 7:42Lex Fridman?

  The first mass market, mass produced.

• 7:45Speaker 02

  It was the first one, yeah, done in quantity. And, and IBM didn't sell them, they, they rented them, but, but they, they rented them to universities at, at great, you know, had a great deal. And, and so that's why a lot of students learned about computers at that time.

• 8:08Lex Fridman?

  So you refer to people, including yourself, who gravitate toward a kind of computational thinking as geeks. At least I've heard you use that terminology.

• 8:20Speaker 02

  It's true that, I think there's something that happened to me as I was growing up that made my brain structure in a certain way that, that resonates with, with computers.

• 8:31Lex Fridman?

  So there's this space of people, it's two percent of the population, you empirically estimate.

• 8:37Speaker 02

  That's a, that's been.

• 8:39Lex Fridman?

  Proven.

• 8:40Speaker 02

  Fairly constant over most of my career. However, it might be different now because kids have different experiences when they're young.

• 8:48Lex Fridman?

  So what does the world look like to a geek? What is, what is this aspect of thinking that is unique to?

• 8:59Speaker 02

  That makes, yeah.

• 9:00Lex Fridman?

  That makes a geek.

• 9:02Speaker 02

  This is a critically important question. In, in the fifties.

• 9:09Speaker 02

  IBM noticed that there were geeks and non-geeks, and so they tried to hire geeks. And they put out Asworth papers saying, "If you play chess, come to Madison Avenue for an interview," or something like this. They were trying for some things. So what is it that I find easy and other people tend to find harder? And I think there's two main things. One is the ability to jump levels of abstraction. So you see something in the large and you see something in the small, and you pass between those unconsciously.

• 9:53Speaker 02

  So you know that in order to solve some big problem, what you need to do is add one to a certain register, and that gets you to another step. And below the... Yeah, 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 going to factor a number or find the root of an equation or something Be out with them. because of what was doing. And as I'm debugging, I'm going through, "Did I make a key punch there? Did I write the wrong instruction? Do I have the wrong thing in a register?" And each level is different.

• 10:37Speaker 02

  And this idea of being able to see something at lots of levels and fluently go between them seems to me to be much more pronounced in the people that resonate with computers. Like I got it. So in my books, I also don't stick just to the high level, but I mix.

• 11:04Speaker 02

  Low level stuff with high level and this means that some people think, you know, that I should write better books and it's probably true, but other people say, well, but that's if you think like that, then that's the way to train yourself, like keep mixing the levels and learn more and more how to jump between. So that's the one thing. The other, the other thing is that it's more of a talent, it to be able to deal with non-uniformity, where there's case one, case two, case three, instead of, instead

• 11:44Speaker 02

  of having one or two rules that govern everything. So, so it doesn't bother me if I need, like an algorithm has 10 steps to it, you know, each step does something else. That doesn't bother me, but a lot of, a lot of pure mathematics is based on one or two rules, which, which are universal and, and, and so this means that people like me sometimes work with systems that are more complicated than necessary because it doesn't bother us that we don't, that we didn't figure out the simple rule.

• 12:18Lex Fridman?

  And you mentioned that while Jacoby, Boole, Abel, and all the mathematicians in 19th century may have had symptoms of geek, the first 100% legit geek was Turing, Alan Turing.

• 12:33Speaker 02

  I, I think he had, yeah, a lot more of the, of this quality than anybody, just from reading the, the kind of stuff he did and.

• 12:44Lex Fridman?

  So how does Turing, what influence has Turing had on you? What, in your way of thinking?

• 12:51Speaker 02

  So I didn't know that aspect of him until after I graduated some years. It, as undergraduate, we had a, a class that talked about computability theory and Turing machines and, and it was all, it sounded like a very specific kind of purely theoretical approach to stuff. So when, how old was I when I, when I learned that he, that he had, you know?

• 13:20Speaker 02

  Design machine and that he wrote the, you know, he wrote a wonderful manual for, for Manchester machines and, and he invented all, you know, subroutines and, and, and he was a real hacker that, that he got his hands dirty. I, I thought for many years that he had only done purely formal work. As I started reading his own publications, I could, you know, I could feel this kinship. And, and of course, he had a lot of peculiarities. Like he wrote numbers backwards because, I mean, left to right instead of right to

• 14:04Speaker 02

  left, because that's, that's, it was easier for computers to process them that way.

• 14:10Lex Fridman?

  What do you mean left to right?

• 14:11Speaker 02

  He would write pi as, you know, nine, five,

• 14:16Lex Fridman?

  Oh, wow.

• 14:17Speaker 02

  one, four, point three. I mean, okay.

• 14:22Lex Fridman?

  Right. Got it.

• 14:24Speaker 02

  Four, one, point three, on the blackboard. I mean, when he, he, he had trained himself to, to do that because the computers he was working with worked that way inside.

• 14:38Lex Fridman?

  Train himself to think like a computer. Well, there you go. That's, that's geek thinking. 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.

• 15:00Speaker 02

  Yeah, absolutely.

• 15:02Lex Fridman?

  So how, do you see those two as conflicting as the formalism of theory and the idea of literate programming?

• 15:08Speaker 02

  So there, there we are in a non-uniform system where I don't, where I don't think one, one size fits all and I don't, and I don't think all truth lies in one, in one kind of expertise. And so somehow, in a way, you'd say my, my life is a convex combination of English and mathematics.

• 15:30Lex Fridman?

  And you're okay with that?

• 15:31Speaker 02

  And not only that, I think.

• 15:33Lex Fridman?

  Thriving.

• 15:34Speaker 02

  I wish, you know, I want my kids to be that way. I want, et cetera. You know, use left brain, right brain at the same time. You get a lot more done. That's, that was part of the.

• 15:45Speaker 02

  Part of the bargain.

• 15:46Lex Fridman?

  And I've heard that you didn't really read for pleasure until into your 30s. And you know, literature.

• 15:54Speaker 02

  That's true. You know more about me than I do, but I'll try to be consistent with what you read.

• 15:58Lex Fridman?

  Yeah, no, just believe me. I just go with whatever story I tell you. It would be easier that way. The conversation.

• 16:04Speaker 02

  Right, yeah, no, that's true.

• 16:07Lex Fridman?

  So I've heard mention of Philip Roth's American Pastoral, which I love as a book. I don't know if it was, it was mentioned as something I think that was meaningful to you as well. In either case, what literary books had a lasting impact on you? What literature?

• 16:25Speaker 02

  Okay, good, good question. So, so I, I met Roth.

• 16:29Lex Fridman?

  Oh, really?

• 16:30Speaker 02

  Well, we both got doctors from Harvard on the same day, so, so we were, you know, we had lunch together and stuff like that. And, but he knew that, you know, computer books would never sell. Well, well. All right, so you say you, you, you, you were a teenager when you left Russia. So I have to say that Tolstoy was one of the big influences on me. I especially like Anna Kornina, not because of, of particular, of the plot of the story where, but because

• 17:07Speaker 02

  there's this character who, you know, the philosophical discussions that it's all, it's a, it got the whole. Way of life is worked out there among the characters. And so, and so that I thought was, was especially beautiful. On the other hand, Dostoevsky, I, I didn't like at all because I, I felt that he, his genius was mostly because he kept forgetting what he, what he had started out to do. And he was just sloppy. I, I, I didn't think that, that, that, that he polished his stuff at all. And I tend to admire somebody who, who dots the i's and crosses the t's.

• 17:49Lex Fridman?

  So the, the music of the prose is what you admire more than?

• 17:53Speaker 02

  I certainly do admire the music of the language, which I couldn't appreciate in the Russian original. But, but I can in Victor Hugo, you know, because it's close, French is much, is closer. But Tolstoy, I like, the same reason I like Herman Wook as a novelist. I think, like, his book, Marjorie Morningstar, has a similar character in who developed his own personal philosophy and it goes in.

• 18:24Lex Fridman?

  Was consistent.

• 18:26Speaker 02

  Yeah, right. And it's worth pondering.

• 18:31Lex Fridman?

  So you don't like Nietzsche and...

• 18:35Speaker 02

  Like what?

• 18:36Lex Fridman?

  You don't like Friedrich Nietzsche?

• 18:37Speaker 02

  Nietzsche, yeah, no, no. I keep seeing quotations from Nietzsche and he never tempted me to read any further.

• 18:46Lex Fridman?

  Well, he's full of contradictions, so you will certainly not appreciate him.

• 18:51Speaker 02

  But Schiller, you know, I'm trying to get across what I appreciate in literature. And part of it is, as you say, the music of the language, the way it flows. And take Raymond Chandler versus Dashiell Hammett. Dashiell Hammett's sentences are awful and Raymond Chandler's are beautiful, they just flow. So I don't read literature because it's supposed to be good for me or because somebody said it's great, but I find things that I like.

• 19:31Speaker 02

  I mean, you mentioned you were dressed like James Bond, so I love Ian Fleming. I think he's got, he had a really great gift for, if he has a golf game or a game of bridge or something and this comes into his story, it'll be the most exciting golf game or the absolute best possible hands of bridge that exists and he exploits it and tells it beautifully.

• 20:02Lex Fridman?

  So in connecting some things here, looking at literate programming and being able to it.

• 20:11Lex Fridman?

  Convey encode algorithms to a computer in a way that mimics how humans speak. How, what do you, what do you think about natural language in general and the messiness of our human world, about trying to express

• 20:30Speaker 02

  Yeah.

• 20:30Lex Fridman?

  difficult things?

• 20:32Speaker 02

  So, the idea of literate programming is to, is really to try to

• 20:41Speaker 02

  understand something better by seeing it from at least two perspectives, the formal and the informal. If we're trying to understand a complicated thing, if we can look at it in different ways. And so, this, this is in fact, the key to technical writing. A good technical writer, trying not to be obvious about it, but says everything twice,

• 21:02Speaker 02

  formally and informally, or maybe three times. But you try to give the, the reader a way to, to put the concept into his own brain or her own brain.

• 21:14Lex Fridman?

  Is that better for the writer or the reader, or both?

• 21:19Speaker 02

  Well, the writer just tries to understand the reader. That's the goal of a writer, is to, is to have a good mental image of the reader. And to, to say what the reader expects next and to, to impress the reader with what has impressed the writer.

• 21:40Speaker 02

  Why something is interesting. So, so when you have a computer program, we try to, instead of looking at it as something that we're just trying to give an instruction to the computer, what we really want to be is giving, giving insight to the person who's, who's going to be maintaining this program or, or to the programmer himself when he's debugging it, as to why this stuff is being done. And so, all the techniques of exposition that, that a teacher uses or a book writer uses, make you better programmer, if your, if your program is going to be not just a one-shot deal.

• 22:18Lex Fridman?

  So, how difficult is that? Do you see hope for the combination of informal and formal for the programming task?

• 22:30Speaker 02

  Yeah, I I'm the wrong person to ask, I guess, because I'm a geek, but but I think for a geek, it's easy. I don't know. Some people have difficulty writing and that might be because there's something in their brain structure that makes it hard for them to write, or it might be something just that they haven't had enough practice. I'm not the right one to judge, but I don't think you can teach any person any particular skill. I do think that that writing is is half of my life, and so I put it together in a little program.

• 23:09Speaker 02

  Even when I'm writing a one-shot program, I I write it in a way because I get it right faster that way.

• 23:21Lex Fridman?

  Now, does it get compiled automatically?

• 23:24Speaker 02

  Yeah.

• 23:25Lex Fridman?

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

• 23:36Speaker 02

  Informally?

• 23:37Lex Fridman?

  Yeah, informally.

• 23:39Speaker 02

  I think whatever works to make it understandable is good, but then you have to also understand how informal is. You have to know the limitations. You have to... So by putting the formal and informal together, this is where this is where it gets locked into your into your brain. You can you can say informally, well, I'm working on a problem right now, so.

• 24:10Lex Fridman?

  Let's go there. Can you give me an example of of connecting the informal and the formal?

• 24:17Speaker 02

  Well, it's a little too complicated an example. There's a puzzle that's self-referential. It's called a Japanese arrow puzzle, and and you're given a bunch of boxes, each one points northeast, 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. So if I put a three in a box, that means that and it's pointing to five other boxes. That means that there's going to be three different numbers in those five boxes. And and those boxes are pointing, one of them might be pointing to me, one of them might be pointing the other the other way. But anyway, I it, yeah, I I'm supposed to find a set of numbers

• 25:02Speaker 02

  that obeys this this complicated condition that each number counts how many distinct numbers it points to. Well, and so a guy sent me his solution to this problem where he where he presents formal statements that that say either this is true, or this is true, or this is true. And and so I try to render that formal statement informally. And I try to say, I contain a three and and the guys I'm pointing to contain the numbers one, two, and six. So by putting it informally and also I convert it into a into a dialogue

• 25:47Speaker 02

  statement, that helps me understand the logical statement that he's written down as a string of numbers in terms of some abstract variables that he had.

• 25:58Lex Fridman?

  That's really interesting. So maybe an extension of that, there has been a resurgence in computer science and machine learning and neural networks. So using data to construct algorithms. So it's another way to construct algorithms, really.

• 26:16Speaker 02

  Yes.

• 26:16Lex Fridman?

  If you can think of it that way.

• 26:19Speaker 02

  Yeah, yeah.

• 26:21Lex Fridman?

  So as opposed to natural language to construct algorithms, use data to construct. So what what's your view of this branch of computer science where data is almost more important than the mechanism of the algorithm?

• 26:36Speaker 02

  It seems to be suited to a certain kind of non geek. And which is probably why it's it's it's taken off that it has its own community that that really that really resonates with that. But it's hard to, you know, to trust something like that because nobody, even the people who who work with it, that they have no idea what has been learned.

• 27:04Lex Fridman?

  That's a really interesting thought that it makes algorithms more accessible to a different community, a different type of brain.

• 27:15Speaker 02

  Yep.

• 27:16Lex Fridman?

  And that's really interesting because just like literate programming perhaps could make programming more accessible to a certain kind of brain.

• 27:27Speaker 02

  There are people who think it's just a matter of education and anybody can learn to be a great programmer, anybody can learn to be a great skier.

• 27:39Speaker 02

  You know, I wish that were true, but I know that there's a lot of things that I've tried to do and I was well motivated and I kept trying to build myself up and I never got past a certain level. I can't view, for example, I can't view three dimensional objects in my head. 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, but other people are good at four dimensions.

• 28:11Lex Fridman?

  Physicists.

• 28:13Speaker 02

  Yeah.

• 28:15Lex Fridman?

  So let's go to the art of computer programming. In 1962, you set the table of contents for this magnum opus, right?

• 28:30Speaker 02

  Yep.

• 28:31Lex Fridman?

  It was supposed to be a single book with 12 chapters. Now today, what is it, 57 years later, you're in the middle of volume four of seven?

• 28:44Speaker 02

  In the middle of volume 4B is more precisely.

• 28:47Lex Fridman?

  Can I ask you for an impossible task, which is try to summarize the book so far, maybe by giving 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.

• 29:07Speaker 02

  Elevator, that's great. Yeah, right.

• 29:09Lex Fridman?

  But depending how many floors there are in the building.

• 29:11Speaker 02

  Yeah. The first volume called Fundamental Algorithms talks about. It's something that you can't, the stuff you can't do without. You have to, you have to know some basic concepts of, of what is a program? What is, what is an algorithm? And, and, and it also talks about a low level machine. So you can have some, some kind of an idea what, what's going on. And it has basic concepts of input, output and subroutines.

• 29:43Lex Fridman?

  Induction.

• 29:45Speaker 02

  Induction, right? Mathematical preliminary. So, so the thing that makes my book different from a lot of others is that all, that I try to not only present the algorithm, but I try to analyze them, which means to quantitatively, I say, not only does it work, but it works this fast. Okay. And so I need math for that. And then there's the standard way to structure data inside and represent information in the computer. So that's all volume one. Uh, volume two talks, it's called semi numerical algorithms. And here we're, here we're, we're writing programs, but we're also de- dealing with numbers. Algorithms deal with, with, with any kinds of objects, but, but specific, when there's

• 30:29Speaker 02

  objects or 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 algebraic concepts that have numbers in structured ways.

• 30:54Lex Fridman?

  And arithmetic and the way a computer would think about arithmetic. So floating point.

• 30:58Speaker 02

  Floating point arithmetic, high precision arithmetic, not only addition, subtraction, multiplication, but also comparison of numbers.

• 31:08Speaker 02

  So then, then volume three talks about...

• 31:11Lex Fridman?

  I like that one, sorting and search.

• 31:12Speaker 02

  Sorting and search.

• 31:13Lex Fridman?

  I love sorting.

• 31:14Speaker 02

  Right, so, so here, you know, we're not dealing necessarily with numbers, because you sort letters and other objects, and searching, we're doing all the time with Google nowadays, but I mean, we have to find stuff. So, again, algorithms that, that underlie all kinds of applications. You know, none of these volumes is about a particular application, but the applications are examples of, of why people want to know about sorting, why people want to know about random numbers. So then, volume four goes into combinatorial algorithm. This is where we have zillions of things to deal with,

• 31:52Speaker 02

  and we, and here, we keep finding cases where one good idea can, can make something go more than a million times faster. And, and, and we're dealing with problems that are probably never going to be solved efficiently, but that doesn't mean we give up on them, and, and, and we have this chance to have good ideas and, and go much, much faster on them. So, so that's combinatorial algorithms, and those are the ones that are, I mean, you say sorting is most fun for you.

• 32:27Lex Fridman?

  Well, I like the satisfiability, too.

• 32:29Speaker 02

  It's true, it's fun, but combinatorial algorithms are the ones that I always, that I always enjoyed the most, because that's when my skillet programming had the most payoff. And the difference, the difference between an obvious algorithm that you think up first thing, and a, you know, and a good, and a, and an interesting subtle algorithm that not so obvious, but, but runs circles around the other one. That's, that's where computer science really comes, comes in. And, and a lot of these combinatorial methods were found first in application started, if you're intelligence or cryptography.

• 33:11Speaker 02

  And in my case, I just liked them and it was associated more with puzzles.

• 33:18Lex Fridman?

  Do you like them most in the domain of graphs and graph theory?

• 33:22Speaker 02

  Graphs are great because they're terrific models of so many things in the real world. And you throw in numbers on a graph, you've got a network and so there you have many more things. But combinatorial in general is any arrangement of objects that has some kind of a higher structure, non-random structure. And is it possible to put something together satisfying all these conditions? Like I mentioned arrows a minute ago, is there a way to put these numbers on a bunch of boxes that are pointing to each other? Is that going to be possible at all?

• 34:06Lex Fridman?

  That's volume four.

• 34:07Speaker 02

  That's volume four.

• 34:09Lex Fridman?

  What does the future hold?

• 34:10Speaker 02

  Volume four A was part one. And what happened was in 1962, when I started writing down a table of contents, it wasn't going to be a book about computer programming in general. It was going to be a book about how to write compilers. And I was asked to write a book explaining how to write a compiler. And at that time, there were only a few dozen people in the world who had written compilers and I happened to be one of them. And I also had some experience writing for like the campus newspaper and things like that. So I said, okay, great.

• 34:55Speaker 02

  I'm the only person I know who's written a compiler but hasn't invented any new techniques for writing compilers. And all the other people I knew had super ideas, but I couldn't see that they would be able to write a book that would describe anybody else's ideas but their own. So I could be the journalist and I could explain what all these cool ideas about compiler writing were. And then I started putting down, well, yeah, you need...

• 35:26Speaker 02

  Have a chapter about data structures, you need to have some introductory material. I want to talk about searching because a compiler writer has to, has to look up the variables in a symbol table and find out, you know, which, which, when you, when you write the name of a variable in one place, it's supposed to be the same as the one you put somewhere else. So you need all these basic techniques and I, and I, you know, kind of know some arithmetic and stuff. So I, so I threw in these chapters and I threw in a chapter on combinatorics because that was what I really enjoyed programming the most, but there weren't many algorithms known about combinatorial methods in 1962.

• 36:11Speaker 02

  So that was a kind of a short chapter, but it was sort of thrown in just for fun. And chapter 12 was going to be actual compilers, applying all the stuff in chapters one to 11 to make compilers. Well, okay. So that was my table of contents from 1962. And during the seventies, the whole field of combinatorics went through a huge explosion. People talk about a combinatorial explosion and they usually mean by that, that the number of cases goes up, you know, you change N to N plus one and all of a sudden you, your problem has, has gotten more than 10 times harder. But there was a, an explosion of ideas about

• 36:52Speaker 02

  combinatorics in the seventies to the point that, but it like take 1975, I, I bet you more than half of all the journals of computer science were about combinatorial method.

• 37:06Lex Fridman?

  What kind of problems were occupying people's minds? What kind of problems in combinatorics? Was it satisfiability, graph theory?

• 37:14Speaker 02

  Yeah, graph theory was, was quite dominant. I mean,

• 37:19Speaker 02

  But all of the NP hard problems that you have, like, you know, Hamiltonian path

• 37:25Lex Fridman?

  Charles Salsman.

• 37:27Speaker 02

  Going beyond, yeah, yeah, going beyond graphs, you had operation research. Whenever it was a small class of problems that had efficient solutions and they were usually associated with Matroid, the special mathematical construction. But once we went 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 you have, if you have clauses, 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 a clause, then nobody knows how to do it.

• 38:09Speaker 02

  So these articles were about trying to find better, better ways to, to solve cryptography problems and graph theory problems. Where we have lots of data, but we didn't know how to find the best subsets of the data. Like with sorting, we could get the answer, didn't take long.

• 38:30Lex Fridman?

  So how did it continue to change from the seventies to today?

• 38:33Speaker 02

  Yeah, so now there may be 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 seventies. But still, there's huge amount of work being done 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 whole bunch of brand new methods that, as far as I know, there's no other, there's no other book that covers, that covers this particular approach.

• 39:17Speaker 02

  And, and so I'm trying to do my best of exploring the tip of the iceberg and, and I try out lots of things and, and keep, keep rewriting, finding, as I find better, better method.

• 39:33Lex Fridman?

  So what's your writing process like? What's your thinking and writing process like every day?

• 39:39Speaker 02

  So.

• 39:41Lex Fridman?

  What's your routine even?

• 39:43Speaker 02

  I, yeah, I, I guess it's actually the best question because I, I spend seven days a week.

• 39:50Lex Fridman?

  You're doing it. You're the most prepared to answer it.

• 39:53Speaker 02

  Yeah, but, okay, so.

• 39:58Speaker 02

  The chair I'm sitting in is where I do.

• 40:02Lex Fridman?

  It's where the magic happens.

• 40:03Speaker 02

  Well, I, I, reading and writing, the, my chair is usually sitting over there where I have other book, or some reference book, but, but I, I found this chair.

• 40:14Speaker 02

  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 the stand up 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.

• 40:37Speaker 02

  Standing up.

• 40:38Lex Fridman?

  The kernel of the idea is first put on paper.

• 40:41Speaker 02

  Yeah.

• 40:42Lex Fridman?

  That's where.

• 40:43Speaker 02

  Right. And I, I'll write maybe five programs a week.

• 40:48Speaker 02

  Of course, literate programming. And 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 at the end of January, I, I learned of a, 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, and I had to take their approach and I had to, I had to try it out

• 41:29Speaker 02

  on a couple of dozen of the other problems I had already worked out with, with my old methods. And so that took another couple of weeks. And then I, you know, then I, then I started to see the light and I, and, and I started writing the, the final draft and, and then I would, you know, type it up. Involved some new mathematical questions. And so I wrote to my friends and who, who might be good at solving those problems and, and they solved some of them. And so I put that in as exercises and.

• 42:03Speaker 02

  And so a month later, I had absorbed one new idea that I that I learned and 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, I my publisher is going to shoot me.

• 42:28Lex Fridman?

  Well, so in the process, in that one month process, are some days harder than others?

• 42:36Speaker 02

  Are some days harder than others? Well, 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 many days I'll say, why do I have to have such high standards? Why couldn't I just be sloppy and not try this out and, you know, just just report the answer? But I but I know that that people are counting me to do this. And so, 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, you know, I'm getting good results and and and I get and I even more when I see that somebody

• 43:17Speaker 02

  has actually read and understood what I wrote and told me how to make it even better. I did want to mention something about the about the method. So I got this tablet here where

• 43:31Lex Fridman?

  Wow.

• 43:33Speaker 02

  where I do the first, you know, the first writing of of concepts. Okay, so so

• 43:42Lex Fridman?

  And what language is that in?

• 43:44Speaker 02

  Right. So here, take a look at it. But, you know, here, random say, explain how to draw such skewed pixel diagrams. Okay, so I got this paper about 40 years ago when I was visiting my sister in Canada and they make tablets of paper with this nice large size and just the right

• 44:05Lex Fridman?

  In a very small space between lines.

• 44:06Speaker 02

  Small spaces, yeah, yeah.

• 44:08Lex Fridman?

  Maybe also just show it.

• 44:11Speaker 02

  Yeah.

• 44:12Lex Fridman?

  Yeah. Wow.

• 44:15Speaker 02

  You know, I've got these manuscripts going back to the 60s.

• 44:21Speaker 02

  And, and, and those are when I get my ideas on paper, okay? But I'm a good typist. In fact, I went to typing school when I was, when I was in high school. And so I can type faster than I think. So then when I do the editing and stand up and type, then I, then I revise this and it comes out a lot different than what, you know, for, for style and rhythm and things like that come out at the, at the typing stage.

• 44:48Lex Fridman?

  And you type in tech?

• 44:50Speaker 02

  And I type in tech.

• 44:51Lex Fridman?

  And can you, can you think in tech?

• 44:54Speaker 02

  No.

• 44:55Lex Fridman?

  So.

• 44:56Speaker 02

  To a certain extent, I have, I have only a small number of, of idioms that I use. Like, you know, I'm beginning a theorem, I do something for displayed equation, I do something and so on, but I, but I, I have to see it and.

• 45:10Lex Fridman?

  In the way that it's on paper here?

• 45:12Speaker 02

  Yeah, right.

• 45:13Lex Fridman?

  So for example, Turing wrote, what, The Other Direction? You don't write macros, you don't think in macros?

• 45:21Speaker 02

  Not particularly, but when I need a macro, I'll, I'll go ahead and, and do it. But, but, 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, I'll, you know, it's like haiku. I'll figure out a way to rewrite the sentence so that it'll look better on the page. And I shouldn't be wasting my time on that, but, but I can't resist because I know it's only another 3% of the time or something like that.

• 45:51Lex Fridman?

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

• 45:56Speaker 02

  Ah, yes, in fact, that's true.

• 46:00Speaker 02

  Like, like I work in the garden one day a week and that's, that's kind of a description of my life is getting rid of weeds, you know, removing bugs for programs and.

• 46:10Lex Fridman?

  So you know, a lot of writers talk about, you know, basically suffering, the writing process is having, 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? You, you kind of say it's, you know?

• 46:38Speaker 02

  Oh, yeah.

• 46:39Lex Fridman?

  It's fun.

• 46:42Lex Fridman?

  But it'd be interesting to hear if there are non-fun parts that you really struggle with.

• 46:48Speaker 02

  Yeah, so the fun comes when I'm able to put together ideas of two people who didn't know about each other. And so I might be the first person that saw both of their ideas. And so then, you know, then I get to make the synthesis and that gives me a chance to be creative. But the dredge work is where I've got to chase everything down to its root. This leads me into really interesting stuff. I mean, I learn about Sanskrit and I, you know, I try to give credit to all the authors. And so I write, so I write to

• 47:26Speaker 02

  people who know the people, authors if they're dead, or I communicate this way. And I got to get the math right. And I got to tackle all my programs, try to find holes in them. And I rewrite the programs after I get a better idea.

• 47:44Lex Fridman?

  Is there ever dead ends?

• 47:46Speaker 02

  Dead ends? Oh, yeah. 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, for whom baseball is the most important thing in the world, you know, but it's, but I also know a lot of people for whom cricket is the most important in the world, or soccer or something, you know. And, and I realized that if, if I had a big example, I mean, it was going to have a fold out illustration and everything. And I was saying, well, what, what am I really teaching about algorithms here where I had this, this, this baseball example? And if I was a person who, who knew only cricket,

• 48:28Speaker 02

  wouldn't they, what would they think about this? And so I ripped the whole thing out. But I, you know, I had, I had a, something that would have really appealed to people who grew up with baseball as, as, as a major theme in their life.

• 48:41Lex Fridman?

  Which is a lot of people, but.

• 48:43Speaker 02

  But just, yeah.

• 48:44Lex Fridman?

  A small minority.

• 48:46Speaker 02

  Small minority. I took out bowling, too.

• 48:50Lex Fridman?

  Even a smaller minority. What's the art in the art of programming? Why, why is there, of the few words in the title, why is art one of them?

• 49:03Speaker 02

  Yeah, well, that's, that's what I wrote my Turing lecture about. And, and so when people talk about art, it really, I mean, what the word means is

• 49:17Speaker 02

  something that's not in nature. So, so when you have artificial intelligence, that art comes from the same root, saying that this is something that was created by, by human beings. And then it's gotten a further meaning, often of fine art, which has this beauty to the, to the mix and says, you know, we have things that are artistically done and, and this means not only done by humans, but also done in a way that's elegant and brings joy and, and has, has, I guess, Tolstoy versus Dostoevsky.

• 50:00Lex Fridman?

  Right.

• 50:01Speaker 02

  But anyway, it, it's that part that, that says that it's done well as well as not only different from nature. In general, then, art is what human beings are specifically good at. And when they say artificial intelligence, well, they're trying to mimic human beings.

• 50:24Lex Fridman?

  But there's an element of fine art and beauty. You are one.

• 50:29Speaker 02

  That's what I, that's what I try to also say, that you can write a, a program and make a work of art.

• 50:37Lex Fridman?

  So now in terms of.

• 50:42Lex Fridman?

  Surprising, you know, what ideas in writing from sort in search to the combinatorial algorithms, what ideas have you come across that were particularly surprising to you? That's that changed the way you see a space of problems?

• 51:04Speaker 02

  I get a surprise every time I have a bug in my program, obviously, but that isn't really what you're at.

• 51:11Lex Fridman?

  More transformational than surprising.

• 51:14Speaker 02

  For example, in volume four A, I was especially surprised when I learned about data structure called BDD, Boolean Decision Diagram, because I sort of had the feeling that as an old timer, and you know, I'd been programming since the 50s, and BDDs weren't invented until 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, I mean, logic is, underlies

• 51:55Speaker 02

  everything we can describe, all of what we know in terms of logic somehow, and propositional logic, I thought that was cut and dried and everything was known, but here comes Randy Bryant and discovers that BDDs are incredibly powerful. Then, then, so that means I have a whole new section to the book that I never would have thought of until 1986, not even until 1990s, when people started to use it for,

• 52:40Speaker 02

  you know, billion dollar of applications. And it was, it was the standard way to design computers for a long time until SAT solvers came along in the year 2000. So that's another great big surprise. So a lot of these things have totally changed the structure of my book. And the middle third of volume four B is about SAT solvers, and that's

• 53:06Speaker 02

  300 plus pages, which is, uh, which is all about material, mostly about material that was discovered in this century. And I had to start from scratch and meet all the people in the field and write, I have 15 different sets, Albers, that I wrote while preparing that. Seven of them are described in the book, others were from my own experience.

• 53:33Lex Fridman?

  So newly invented data structures or ways to represent?

• 53:37Speaker 02

  A whole new class of algorithm.

• 53:39Lex Fridman?

  Whole new class of algorithm.

• 53:41Speaker 02

  Yeah, and the interesting thing about the BDDs was that the theoreticians started looking at it and started to describe all the things you couldn't do with BDDs. And so they were getting a bad, they were getting a bad name. Because, you know, okay, they were, they were useful, but they didn't solve every problem. I'm sure that the theoreticians are, in the next 10 years, are going to show why machine learning doesn't solve everything. But I, you know, not only worried about the worst case, I get a huge delight when I can actually solve a problem that I couldn't solve before.

• 54:22Speaker 02

  Even though I can't solve the problem that's, that it suggests as a further problem. Like, 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. And so I had to spend quite a few years learning about the, that territory.

• 54:48Lex Fridman?

  So in general, what brings you more pleasure? 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?

• 55:06Speaker 02

  Yeah, I like a good case that, that is maybe only a million times faster than I was able to do before. But, and not worry about the fact that, that it's still, that it's still going to take too long if I double the size of the problem.

• 55:22Lex Fridman?

  So that said, you popularized the asymptotic notation for describing running time, obviously in the analysis of algorithms, worst case is such an important part. Do you see any aspects of that kind of analysis is lacking? And notation too?

• 55:43Speaker 02

  Well, the main purpose, we have notations that that help us for the problems we want to solve and so that they match our they match our intuitions. And people who worked in number theory had used asymptotic notation in a certain way, but it was only known to a small group of people. 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 partial about it. And so, for example, instead of big O notation, let's just let's just take a much simpler notation where I'd say zero or one, or zero, one or two.

• 56:27Speaker 02

  And suppose that when I had been in high school, we would be allowed to put in the middle of our formula, x plus zero, one or two equals y. Okay. And then we would learn how to multiply two such expressions together and, you know, deal with them. Well, the same thing, big O notation says, here's something that's, I'm not sure what it is, but I know it's not too big. I know it's not bigger than some constant times n squared or something like that. And so I write big O of n squared. And now I learn how to add big O of n squared to big O of n cubed.

• 57:08Speaker 02

  And I know how to add big O of n squared to 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 hugely valuable in all of the work that I was trying to do as I'm trying to figure out how good an algorithm is.

• 57:26Lex Fridman?

  So have there been algorithms in your journey that perform very differently in practice than they do in theory?

• 57:35Speaker 02

  Well, the worst case of a combinatorial algorithm is almost always horrible. But we have SAT solvers that are solving where one of the last exercises in that part of my book was figure out a problem that has 100 variables that's difficult for a SAT solver. But you would think that a problem with 100 Boolean variables requires you to do 2 to the 100th operations, because that's the number of possibilities when you have 100 Boolean variables and 2 to the 100th. 2 to the 100th is way bigger than we can handle. 10 to the 17th is a lot.

• 58:19Lex Fridman?

  You've mentioned over the past few years that you believe P may be equal to NP, but that is not really, you know, if somebody does prove that P equals NP, it will not directly lead to an actual algorithm to solve difficult problems. Can you explain your intuition here? Has it been changed? And in general, on the difference between easy and difficult problems of P and NP and so on?

• 58:46Speaker 02

  Yeah, so the popular idea is if an algorithm exists, then somebody will find it. And it's just a matter of writing it down. But many more algorithms exist than anybody can understand or ever make use of.

• 59:09Lex Fridman?

  Or discover, yeah.

• 59:10Speaker 02

  Because they're just way beyond human comprehension. The total number of algorithms is more than mind-boggling. So we have situations now where we know that algorithms exist, but we don't know, we don't have the foggiest idea what the algorithms are. There are simple examples based on

• 59:34Speaker 02

  On game playing where you have, where you say, "Well, there must be an algorithm that exists to win in the game of Hex, because for the first player to win in the game of Hex, because Hex is always either a win for the first player or the second player."

• 59:52Lex Fridman?

  Well, what's the game of Hex?

• 59:53Speaker 02

  There's a game of Hex, which is based on putting pebbles onto a hexagonal board, and the white player tries to get a white path from left to right, and the black player tries to get a black path from bottom to top.

• 1:00:06Lex Fridman?

  And how does capture occur? Just so I understand.

• 1:00:09Speaker 02

  And there's no capture. You just put pebbles down one at a time. But there's no draws, because after all the white and black are played, there's either going to be a white path across from east to west, or a black path from bottom to top. So there's always, you know, it's a perfect information game, and people take turns like tic-tac-toe. And the Hex board can be different sizes, but there's no possibility of a draw. And players move one at a time. And so it's got to be either a first-player win or a second-player win. Mathematically, you follow out all the trees, and there's always a win for the first player, second player, okay? And it's finite.

• 1:00:54Speaker 02

  The game is finite. So there's an algorithm that will decide. You can show it has to be one or the other. Because the second player could mimic the first player with kind of a pairing strategy. And so you can show that it has to be one or the other. But we don't know any algorithm anyway. We don't know the algorithm. In other words, there are cases where you can prove the existence of a solution, but nobody knows any way how to find it. More like the algorithm question, there's a very powerful theorem in graph theory by Robinson and Seymour that says that every...

• 1:01:38Speaker 02

  Class of graphs that is closed undertaking minors 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. And a planar graph, taking minors means that you can shrink an edge into a point, or you can delete an edge. And so you start with a planar graph, shrink any edge to a point is still planar, delete an edge is still planar.

• 1:02:13Speaker 02

  Okay, now, but there are millions of different ways to describe a family of graphs that still is, remains the same undertaking minor. And Robertson and Seymour proved that any such family of graphs, there's a finite number of minimum graphs that are obstructions. So that if it's not in the family, then it has to contain, then there has to be a way to shrink it down until you get one of these bad minimum graphs that's not in the family.

• 1:02:58Speaker 02

  For, in the case of a planar graph, the minimum graph is a five-pointed star where everything pointing to another, and the minimum graph consisting of trying to connect three utilities to three houses without crossing lines. 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 bad graphs by shrinking and moving edges.

• 1:03:24Lex Fridman?

  Sorry, can you say it again? So he proved that there's a finite number of these bad graphs.

• 1:03:29Speaker 02

  There's always a finite, so somebody says, here's a family of...

• 1:03:32Lex Fridman?

  It's hard to believe.

• 1:03:33Speaker 02

  And they proved in this sequence of 20 papers, I mean, and it's deep work, but it, you know, it's...

• 1:03:42Lex Fridman?

  Because that's for any arbitrary class.

• 1:03:44Speaker 02

  Any arbitrary class that's closed undertaking minors.

• 1:03:48Lex Fridman?

  That's closed under, maybe I'm not understanding, because it seems like a lot of them are closed undertaking minors.

• 1:03:54Speaker 02

  Almost all the important classes of graphs are. There are tons of such graphs, but also...

• 1:04:02Speaker 02

  Hundreds of them that arise in applications. I have a book over here called Classes of Graphs. And it's amazing how many different classes of graphs that people have looked at.

• 1:04:16Lex Fridman?

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

• 1:04:19Speaker 02

  So now, there are lots of algorithms that are known for special class of graphs. For example, if I have a certain, if I have a chordal graph, then I can color it efficiently. If I have some kinds of graphs, it'll make a great network. So you'd like to test.

• 1:04:39Speaker 02

  Somebody gives you a graph, it's always in this family of graphs. If so, then I can, I can go to the library and find an algorithm that's going to solve my problem on that graph.

• 1:04:50Speaker 02

  Okay, so we have, we want to have a graph that says, an algorithm that says,

• 1:04:59Speaker 02

  you give me a graph, I'll tell you whether it's in, whether it's in this family or not. Okay, and so all I have to do is test whether or not, does this given graph have a miner? That's one of the bad ones. A miner is, is everything you can get by shrinking and removing edges. And given any miner, there's a polynomial time algorithm saying, I can tell whether this is a miner of you. And there's a finite number of bad cases. So I just try, you know, does it have this bad case? Polynomial time, I got the answer. Does it have this bad case? Polynomial time, I got the answer.

• 1:05:38Speaker 02

  Total polynomial time. And so I've solved the problem. However, all we know is that the number of minors is finite. We don't know what, we might only know one or two of those minors, but we don't know that if we've got, if we've got 20 of them, we don't know, there might be 21, 25.

• 1:05:56Speaker 02

  All we, all we know is that, is that it's finite. So here we have a polynomial time algorithm that we don't know.

• 1:06:03Lex Fridman?

  That's a really great example of what you worry about, or why you think P equals NP won't be useful. But still, why do you hold the intuition that P equals NP?

• 1:06:17Speaker 02

  Because you have to rule out so many possible algorithms as being not working. You know, you can, you can take the graph and you can represent it as in terms of certain prime numbers and then you can multiply those together and then you can, then you can take the bitwise and, and, you know, and construct some certain constant in polynomial time and then that's, you know, perfectly valid algorithm and there are so many algorithms

• 1:06:52Speaker 02

  of that kind, a lot of times we see random, you take data and, and we get coincidences that, that, that some fairly random looking number actually is useful because, because it happens to, it happens to solve, it happens to solve a problem just because, you know, there's, there's so many hairs on your head, but it, it seems like unlikely that two people are going to have the same number of hairs on their head, but, but they're obvious, but

• 1:07:34Speaker 02

  you can count how many people there are and how many hairs on their heads. There must be people walking around in the country that have the same number of hairs on their head. Well, that's a kind of a coincidence that you, you might say also, you know, this, this particular combination of operations just happens to prove that a graph is, has a Hamiltonian path. I mean, I, I see lots of cases where unexpected things happen when you have enough, enough possibilities.

• 1:08:00Lex Fridman?

  So because the space of possibilities is so huge, your Jewish.

• 1:08:04Speaker 02

  They have to rule them all out. And so that's the reason for my intuition is it by no means a proof. I mean, some people say, you know, well, P can't equal NP because you've had all these smart people, you know, the smartest designers' algorithms have been racking their brains for years and years and, and there's million dollar prizes out there and, you know, none of them, nobody has thought of the algorithm. So it must, there must be no such algorithm. On the other hand. I can use exactly the same logic and I can say, well, P must be equal to NP because there are so many smart people out here have been trying to prove it unequal to NP

• 1:08:47Speaker 02

  and they've all failed, you know.

• 1:08:51Lex Fridman?

  This kind of reminds me of the discussion about the search for aliens. They've been trying to look for them and we haven't found them yet, therefore they don't exist.

• 1:09:00Speaker 02

  Yeah.

• 1:09:01Lex Fridman?

  But you can show that there's so many planets out there that they very possibly could exist.

• 1:09:05Speaker 02

  Yeah.

• 1:09:06Lex Fridman?

  And.

• 1:09:07Speaker 02

  And then there's also the possibility that that they exist, but they they all discovered machine learning or something and and and then blew each other up.

• 1:09:18Lex Fridman?

  Well, on that small, quick tangent, let me ask, do you think there's intelligent life out there in the universe?

• 1:09:24Speaker 02

  I have no idea.

• 1:09:25Lex Fridman?

  Do you hope so? Do you think about it?

• 1:09:27Speaker 02

  It I I don't I don't spend my time thinking about things that I could never know, really.

• 1:09:34Lex Fridman?

  And yet you do enjoy the fact that there's many things you don't know. You do enjoy the mystery of things.

• 1:09:41Speaker 02

  I I enjoy the fact that there that I have limits, yeah. But I don't but but I don't take time to to to answer unsolvable questions.

• 1:09:51Lex Fridman?

  Got it.

• 1:09:53Lex Fridman?

  Well, because you've taken on some tough questions that may seem unsolvable. You have taken on some tough questions that may seem unsolvable.

• 1:10:01Speaker 02

  And it gives me a thrill when I can get further than I ever thought I could.

• 1:10:05Lex Fridman?

  Right.

• 1:10:05Speaker 02

  Yeah.

• 1:10:06Lex Fridman?

  But.

• 1:10:07Speaker 02

  But I don't.

• 1:10:08Lex Fridman?

  But much like with religion, these.

• 1:10:10Speaker 02

  I'm glad that there that that there are no proof that God exists or not. I mean, this, I think.

• 1:10:16Lex Fridman?

  It would spoil the mystery.

• 1:10:18Speaker 02

  It it would be it would be too dull, yeah.

• 1:10:21Lex Fridman?

  So to quickly talk about the other art of artificial intelligence. What is if you 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. What's your view of the AI community from the 60s to now?

• 1:10:44Speaker 02

  So all the way through, it was the people who were inspired by trying to mimic.

• 1:10:51Speaker 02

  Intelligence or to do things that that were somehow the greatest achievements of intelligence that had been inspiration to people who have pushed the envelope of computer science, maybe more than any other group of people. So all he threw, it's been a great source of of good problems to to sink teeth into. And and getting getting partial answers and then more and more successful answers over the year. So this has this had been the inspiration for lots of the great discoveries of computer science.

• 1:11:33Lex Fridman?

  Are you yourself captivated by the possibility of creating of algorithms having echoes of intelligence in them?

• 1:11:41Speaker 02

  Not as much as most of the people in the field, I guess I would say, but but that's not to say that they're wrong or that it's just you asked about my own personal preferences and but the but the thing that I that I worry about is when people start believing that they've actually succeeded. And because the seems to me this huge gap between really understanding something and being able to pretend to understand something and give the give the illusion of understanding something.

• 1:12:25Lex Fridman?

  Do you think it's possible to create without understanding?

• 1:12:28Speaker 02

  Yeah.

• 1:12:29Lex Fridman?

  So to

• 1:12:30Speaker 02

  I do that all the time, too. I mean, that's why I use random numbers. But I but but there's there's still this great gap. I don't assert that it's impossible, but I but I don't see anything coming any closer to really

• 1:12:51Speaker 02

  The kind of stuff that I would consider intelligence.

• 1:12:56Lex Fridman?

  So you've mentioned something that on that line of thinking, which I very much agree with. So The Art of Computer Programming is the book is focused on single processor algorithms. And for the most part, you mentioned.

• 1:13:14Speaker 02

  That's only because I set the table of contents in 1962, you have to remember.

• 1:13:19Lex Fridman?

  For sure. There's no.

• 1:13:21Speaker 02

  I'm glad I didn't wait until 1965.

• 1:13:26Lex Fridman?

  One book, maybe we'll touch on the Bible, but one book can't always cover the entirety of everything. So I'm glad.

• 1:13:37Lex Fridman?

  I'm glad the table of contents for The Art of Computer Programming is what it is. But you did mention that 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 distributed systems. So what do you think is the difference between the way Don Knuth would sort a list and an ant colony would sort a list? Or performing algorithm?

• 1:14:10Speaker 02

  Sorting a list isn't the same as cognition, though, but I know what you're getting at is.

• 1:14:17Speaker 02

  Well, the advantage of ant colony, at least we can see what they're doing. We know which ant has talked to which other ant and it's much harder with the brains to know to what extent neurons are passing signal. So I understand that ant colony might be, if they have the secret of cognition, think of an ant colony as a cognitive. Single being rather than as a colony of lots of different ants. I mean, just like the cells of our brain are and the microbiome and all that is

• 1:14:57Speaker 02

  interacting entities, but somehow I consider myself to be a single person. Well, you know, an ant colony, you can say might be cognitive somehow.

• 1:15:12Lex Fridman?

  That's some suggestion.

• 1:15:14Speaker 02

  Yeah, I mean, you know, like, OK, I smash a certain ant and the organism thinks, hmm, that stung, what was that?

• 1:15:23Lex Fridman?

  Right.

• 1:15:24Speaker 02

  But if we're going to crack the secret of cognition, it might be that we could do so 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 not by much more subtle phenomenon like current going through.

• 1:15:47Lex Fridman?

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

• 1:15:52Speaker 02

  OK, so Conway's Game of Life is able to simulate any computable process. And any deterministic process is.

• 1:16:04Lex Fridman?

  I like how you went there. I mean, that's not its most powerful thing, I would say. I mean, it can simulate it, but the magic is that the individual units are distributed.

• 1:16:19Speaker 02

  Yes.

• 1:16:19Lex Fridman?

  And extremely simple.

• 1:16:21Speaker 02

  Yes, we understand exactly what the primitives are.

• 1:16:24Lex Fridman?

  The primitives, just like with the ant colony, even simpler though.

• 1:16:26Speaker 02

  But if we, but still, it doesn't say that I understand, I understand life. I mean, I understand.

• 1:16:36Speaker 02

  It gives me a better insight into what does it mean to have a deterministic universe? What does it mean to have free choice, for example?

• 1:16:52Lex Fridman?

  Do you think God plays dice?

• 1:16:55Speaker 02

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

• 1:17:20Lex Fridman?

  When the algorithm requires it, you don't see why the physics should constrain it. So in 2001, you gave a series of lectures at MIT about religion and science.

• 1:17:34Speaker 02

  No, that was 1999.

• 1:17:36Lex Fridman?

  You published, sorry.

• 1:17:38Speaker 02

  The book came out in 2001.

• 1:17:40Lex Fridman?

  So in 1999, you spent a little bit of time in Boston enough to give those lectures. And 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. What did you learn from this process about the way us human beings as a society develop and grow ideas, share ideas, and are defined by those ideas?

• 1:18:18Speaker 02

  It's hard to summarize that. I wouldn't say that I learned a great deal of really definite things where I could make conclusions, but I learned more about what I don't know. If you have a complex subject, which is really beyond human understanding, so we give up on saying, I'm never going to get to the end of the road and I'm never going to understand it. But you say, but maybe it might be good for me to get closer and closer and learn more and more about something. And so, you know, how can I do that efficiently? And the answer is, well, use randomness. And so.

• 1:19:03Speaker 02

  So try a random subset of that is within my grasp and study that in detail, instead of just studying parts that somebody tells me to study, or instead of studying nothing, because it's too hard.

• 1:19:24Speaker 02

  So I decided for my own amusement, once, that I would take a subset of the verses of the Bible, and I would try to find out what the best thinkers have said about that small subset. And I had about, let's say, sixty verses out of three thousand. I think it's one out of five hundred, or something like this. And so then I went to the libraries, which are well indexed. I spent, for example, at Boston Public Library, I would go once a week for a year.

• 1:20:09Speaker 02

  And I went a half dozen times to Hanover Harvard Library to look at books that weren't in the Boston Public, where scholars had looked, and you can go down the shelves, and you can look in the index and say, oh, is this verse mentioned anywhere in this book? If so, look at page one hundred and five. So in other words, 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 gave me a way to zoom in on parts of the thing, so that I could get more insight.

• 1:20:53Speaker 02

  And so I look at it as a way of giving me... Some firm pegs which I could hang pieces of information, but not as things where I would say, and therefore, this is true.

• 1:21:08Lex Fridman?

  In this random approach of sampling the Bible, what did you learn about the most, you know, central, one of the biggest accumulation of ideas?

• 1:21:22Speaker 02

  It seemed to me that the main thrust was not the one that most people think of as saying, you know, don't have sex or something like this. But the main thrust was to try to,

• 1:21:39Speaker 02

  to try to figure out how to live in harmony with God's wishes. I'm assuming that God exists, and as I say, I'm glad that I, that there's no way to prove this, because that would, that would, I would run through the proof once, and then I'd forget it, and it would, and I would never speculate about spiritual things and mysteries. Otherwise, and I think my life would be very incomplete. So I'm, so I'm assuming that God exists, but if, but a lot of the people say God doesn't exist, but that's still important to them.

• 1:22:20Speaker 02

  And so in a way, that might still be whether God is there or not, in some sense, God is important to them. It's one of the, one of the verses I studied, that you can interpret as saying, you know, it's much better to be an atheist than not to care at all.

• 1:22:42Lex Fridman?

  So I would say it's, yeah, it's similar to the P equals NP discussion. You mentioned a mental exercise that I'd love it if you could partake in yourself, a mental exercise of being God. And so how would you, if you were God, Don Newth, how would you present yourself to the people of earth?

• 1:23:02Speaker 02

  You mentioned your love of literature, and there was, there's this book that really I can recommend to you. If I, yeah, the title I think is Blasphemy. It talks about God revealing himself through a computer in Los Alamos. And, and it.

• 1:23:24Speaker 02

  It's the only book that I've ever read where the punchline was really the very last word of the book. And it explained the whole idea of the book. And so I don't want to give that away. But it but it's really very much about this question that you that you raised. But but suppose God said, OK, that my previous means of communication with the world are not the best for the 21st century. So what should I do now? And and and it's conceivable that that it would that that God would choose the way that's described in this book.

• 1:24:08Lex Fridman?

  Another way to look at this exercise is looking at the human mind, looking at the human spirit, the human life in a systematic way.

• 1:24:16Speaker 02

  I think it mostly you want to learn humility. You want to realize that once we solve one problem, that doesn't mean that we're that all of a sudden other problems are going to drop out. And and and and we have to realize that that that there are there are things beyond our beyond our our ability. I see hubris all around.

• 1:24:43Lex Fridman?

  Yeah, well said. If you were to run program analysis on your own life, how did you do in terms of correctness, running time, resource use, asymptotically speaking, of course?

• 1:24:58Speaker 02

  OK, yeah, well, I would say that question has not been asked me before. And I I I started out with library of subroutines and and learning how to be an automaton that was obedient. And I had the great advantage that I didn't. Have anybody to blame for my failures. If I started getting, not understanding something, I, I knew that I should stop playing ping pong

• 1:25:41Speaker 02

  and that, that it was my fault that, that I was, that I wasn't studying hard enough or something, rather than that somebody was discriminating against me in some way. And, and I don't know how to avoid this, 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. And, and, and then I, I found the, from, from parents, I learned the idea of, of altruism, of service to other people as being more important than, than what I get out of stuff

• 1:26:26Speaker 02

  myself. I, I know that I need to, I need to be happy enough, enough in order to be able to be of service, but I, but I, you know, but I, I came to a philosophy, finally, that, that I phrase as point eight is enough. There was a TV show once called Eight is Enough, which was about a, you know, somebody had eight kids. But, but I, I, I say point eight is enough, which means if, if I can have a way of rating happiness, I think it's good design that, to have, to have an organism that's happy

• 1:27:10Speaker 02

  about eighty percent of the time. And if it was a hundred percent of the time, it would be like every, like everybody's on drugs and, and never, and, and, and, and everything collapses and nothing works because everybody's just too happy.

• 1:27:26Lex Fridman?

  Do you think you've achieved that point eight optimal balance?

• 1:27:29Speaker 02

  There are times when I, when I'm down and I, you know, and I, I mean, I know that I'm chemically, that I, I know that I, I've actually been programmed to be, uh, uh, to be depressed a certain amount of time. And, and, and if, if that gets out of kilter and I'm more depressed than you, you know, I, sometimes I, I find myself trying to think, now, who should I be mad at today? There must be a reason why I'm, you know.

• 1:27:55Lex Fridman?

  Yeah.

• 1:27:56Speaker 02

  But I, but then I realize, you know, it's just my, it's just my chemistry telling me that I'm supposed to be mad at somebody. And so, and so I trick it off, say, oh, okay, go to sleep and get better. But, but if I'm, but if I'm not a hundred percent happy, that doesn't mean that I should find somebody that, that's screwing me and, and, and try to silence them. But I, but I, I, I'm saying, you know, okay, I'm not a hundred percent happy, but, but I, I'm happy enough to, to, to be a, you know, part of a, of a sustainable situation. So, so that's kind of the, the numerical analysis I do.

• 1:28:38Lex Fridman?

  You've converged towards the optimal, which for human life is a point eight.

• 1:28:42Speaker 02

  Yeah.

• 1:28:42Lex Fridman?

  I hope it's okay to talk about, as you talked about previously, in 2006, you were diagnosed with prostate cancer. Has that encounter with mortality changed you in some way or the way you see the world?

• 1:28:57Speaker 02

  Yeah, it did. The first encounter with mortality was my, when my dad died and I, I went through a month when I,

• 1:29:07Speaker 02

  it sort of came to, uh, can't, you know, uh, be comfortable with the fact that I was going to die someday. And during that month, uh, I don't know, uh, I, uh, I, I felt okay, but I couldn't sing.

• 1:29:26Speaker 02

  And you know, and I, and I couldn't do original research either. I, I can, I sort of remember after three or four weeks, the first time I started having a technical thought that made sense and was maybe slightly creative. I could sort of feel that, that, that something was starting to move again, you know, but that was, you know, so I felt very empty for, until I came to grips with the, I, yes, I learned that this is sort of a standard grief process that people go through. Okay. So then, now I'm at a point in my life, even more so than in 2006, where, where all of my goals have been fulfilled,

• 1:30:08Speaker 02

  except for finishing the art of computer programming. I, I, I had one major unfulfilled goal. I'd wanted all my life to, to write a piece of, a piece, piece of music that, and I had an idea for, for, for a certain kind of music that I thought ought to be written, at least somebody ought to try to do it. And I, and I felt that it was, that it wasn't going to be easy, but I wanted to, I, I wanted it proof of concept. I wanted to know if it was going to work or not. And so I spent a lot of time. And finally, I finished that piece and we had the, we had the world premiere last year on my 80th

• 1:30:52Speaker 02

  birthday and we had another premiere in Canada and there's talk of concerts in Europe and various things. So that, but that's done. It's part of the world's music now and it's either good or bad, but I, I did what I was hoping to do. So the only thing that I, that I have on my agenda is to, is to try to do as well as I can with the art of computer programming until I go see now.

• 1:31:20Lex Fridman?

  Do you think there's a element of point eight that might apply there?

• 1:31:24Speaker 02

  Of what? Point eight?

• 1:31:25Lex Fridman?

  Yeah.

• 1:31:25Speaker 02

  Well, I, I look at it more that I got actually to, to, to 1.0 with, when, when that concert was over with. I mean, I, I, I, you know, I.

• 1:31:41Speaker 02

  So in 2006, I was at point eight. So when I was diagnosed with prostate cancer, then I said, okay, well, maybe this is, you know, I've had all kinds of of good luck all my life and there's no, I have nothing to complain about. So I might die now. And we'll see what happens. And so, so it's quite seriously, I went and I didn't, I had no expectation that I deserved better. I didn't make any plans for the future. I had my surgery, I came out of the surgery and and

• 1:32:26Speaker 02

  spent some time learning how to walk again and so on. It was painful for a while.

• 1:32:33Speaker 02

  But I got home and I realized I hadn't really thought about what to do next. I hadn't, I hadn't any expectation. You know, I said, okay, hey, I'm still alive. Okay, now I can write some more books. But I didn't come with the attitude that, you know,

• 1:32:50Speaker 02

  this was terribly unfair. And I just said, okay, I was accepting whatever turned out.

• 1:33:02Speaker 02

  I'd gotten, I'd gotten more than my share already. So why should I?

• 1:33:10Speaker 02

  Why? And I didn't, and I really,

• 1:33:15Speaker 02

  when I got home, I realized that I had really not thought about the next step, what I would do after I would, after I would be able to work again. I had sort of thought of it as if, as this might, I was comfortable with the fact that it was at the end.

• 1:33:32Speaker 02

  But I was hoping that I would still, you know, be able to.

• 1:33:38Speaker 02

  Learn about satisfiability and also someday even write music. I didn't start, I didn't start seriously on the music project until 2012.

• 1:33:52Lex Fridman?

  So I'm going to be in huge trouble if I don't talk to you about this.

• 1:33:57Lex Fridman?

  In the seventies, you've created the tech type setting system together with meta font language for font description and computer modern family of typefaces. That has basically defined the methodology in the aesthetic of countless research fields, right? Math, physics, beyond computer science, so on. Okay. Well, first of all, thank you. I think I speak for a lot of people in saying that. But a question in terms of beauty. There's a beauty to typography that you've created and yet beauty is hard to quantify.

• 1:34:35Speaker 02

  Right.

• 1:34:38Lex Fridman?

  How does one create beautiful letters and beautiful equations? Like what?

• 1:34:44Speaker 02

  So.

• 1:34:45Lex Fridman?

  I mean, perhaps there's no words to be describing, to be describing the process, but.

• 1:34:52Speaker 02

  So the great Harvard mathematician George D. Burckhardt wrote a book in the 30s called Aesthetic Measure, where he would have pictures of vases and underneath would be a number. And this was how beautiful the vase was. And he had a formula for this. And, and he actually also wrote about music. And so he could, he could, you know, so I thought maybe I would, part of my musical composition, I would try to program his algorithms and, and, you know, so that I would, I would write something that had the highest number by his score. Well, it wasn't quite rigorous enough for, for a computer to, to do.

• 1:35:36Speaker 02

  But anyway, people have tried to. To put numerical value on beauty, but and he did probably the most serious attempt. And George Gershwin's teacher also wrote two volumes where he talked about his method of composing music. But you're talking about another kind of beauty and beauty in letters and letter.

• 1:36:00Lex Fridman?

  Elegance and whatever that curvature is.

• 1:36:03Speaker 02

  Right. So, so, and so that's in the eye of the beholder, as they say, but striving for excellence in whatever definition you want to give to beauty, then you try to get as close to that as you can somehow with.

• 1:36:18Lex Fridman?

  I guess, I guess I'm trying to ask, and there may not be a good answer. What loose definitions were you operating under with the community of people that you were working on?

• 1:36:30Speaker 02

  Oh, the loose definition, I wanted, I wanted it to appeal to me, to me.

• 1:36:38Lex Fridman?

  To you personally?

• 1:36:39Speaker 02

  Yeah.

• 1:36:40Lex Fridman?

  That's a good start.

• 1:36:41Speaker 02

  Yeah, no, and it failed that test when I got, volume two came out with the, with the new printing and I was expecting it to be the happiest day of my life and I, I felt like a burning, like how angry I was that I opened the book and it was in the same beige covers and, but, but it didn't look right on the page. The number two was particularly ugly. I couldn't stand any page that had a two in its page number. And I was expecting that it was, you know, I spent all this time making measurements

• 1:37:18Speaker 02

  and I had, had, had looked at stuff in different, different ways and I, I had, I had great technology, but, but it did, you know, but I, but I wasn't done. I had, I had to retune the whole thing after 1961.

• 1:37:37Lex Fridman?

  Has it ever made you happy finally?

• 1:37:39Speaker 02

  Oh, oh, yes.

• 1:37:40Lex Fridman?

  Or is it a point eight?

• 1:37:43Speaker 02

  No, and so many books have come out that would never have been written without this. I just, it just, it's just, it's so joy, but I could, but now I could. I mean, all these pages that are sitting up there, I don't have a if I didn't like them, I would change them. That's my, nobody else has this ability. They have to stick with what I gave them.

• 1:38:07Lex Fridman?

  Yeah. So in terms of the other side of it, there's the typography. So the look of the type and the curves and the lines, what about the spacing?

• 1:38:18Speaker 02

  What about the?

• 1:38:19Lex Fridman?

  The spacing between the white space.

• 1:38:22Speaker 02

  Yeah.

• 1:38:24Lex Fridman?

  It seems like you could be a little bit more systematic about the layout or technical.

• 1:38:29Speaker 02

  Oh, yeah, you can always go further. I didn't, I didn't stop at point eight. I stopped about point nine eight.

• 1:38:39Lex Fridman?

  It seems like you're not following your own rule for happiness.

• 1:38:43Speaker 02

  No, no, no. There's, okay, of course, there's this, what is the Japanese word, wabi sabi or something? Where the most beautiful works of art are those that have flaws because then the person who perceives them adds their own appreciation and that gives the viewer more satisfaction or so on. But, but I, but no, no, with typography, I wanted it to look as good as I could in the vast majority of cases. And then when it doesn't, then I I say, okay, that's 2% more work for the author.

• 1:39:28Speaker 02

  But I didn't want to, I didn't want to say that my job was to get 200% and take all the work away from the author. That's what I meant by that.

• 1:39:39Lex Fridman?

  So if you were to venture a guess, how much of the nature of reality do you think we humans understand? So you mentioned you appreciate mystery. How much of the world about us is shrouded in mystery? Are we, are we, if you were to put a number on it, what percent of it all do we understand? Are we totally?

• 1:40:03Speaker 02

  How many leading zeros, 0.0000? I don't know. No, I think it's infinitesimal.

• 1:40:09Lex Fridman?

  How do we think about that? And what do we do about that? Do we continue one step at a time?

• 1:40:14Speaker 02

  Yeah, we muddle through. I mean, we do our best. We realize that nobody's perfect and we. And we try to keep advancing, but we don't spend time saying we're not there. We're not all the way to the end. Some mathematicians that would be in the office next to me when I was in the math department, they would never think about anything smaller than countable infinity. And I never, you know, we intersected that countable infinity because I rarely got up to countable infinity. I was always talking about finite stuff. But even limiting to finite stuff, which is, which is, which the universe might be,

• 1:40:59Speaker 02

  there's no way to really know whether the universe isn't just made out of capital N, whatever units you want to call them, quarks or whatever, where capital N is some finite number, all of the numbers that are comprehensible are still way smaller than most, almost all finite numbers. I got this one paper called Supernatural Numbers where I, I guess you probably ran into something called Knuth arrow notation. Did you ever run into that? Where, anyway, so you take a number, I think it's like, and I called it super K.

• 1:41:44Speaker 02

  I named it after myself, but it's, but in arrow notation, it's something like 10 and then four arrows and a three or something like that. Okay, no, the arrow notation, if you have, if you have no arrows, that means multiplication. X Y means X times X times X times X Y times. If you have one arrow, that means exponentiation. So X one arrow Y means X to the X to the X to the X to the X Y times. So I found out by the way that this notation was invented by a guy in 1830.

• 1:42:20Speaker 02

  And, and he was, he was a, a, one of the English nobility who, who spent his time thinking about stuff like this. And, and it was exactly the same concept that I, that I, that I used arrows and he used a slightly different notation. But anyway, this, and then this Ackerman's function is, is based on the same kind of ideas, but Ackerman was 1920s. But anyway, you got this. Number ten quadruple arrow three. So that says, well, we take, you know, we take ten to the ten to the ten to the ten to the tenth. How many times do we do that?

• 1:43:04Speaker 02

  Oh, ten double arrow two times or something. I mean, how tall is that stack? But then we do that again, because that was only ten triple or quadruple arrow two. We take quadruple arrow three.

• 1:43:17Lex Fridman?

  It gets to be a pretty large number.

• 1:43:18Speaker 02

  It gets way beyond comprehension. Okay.

• 1:43:24Speaker 02

  And, and, and so, but it's so small compared to what finite numbers really are. Because I want to using four arrows and, you know, and a ten and a three. I mean, let's have that, let's have that many number arrows. I mean.

• 1:43:40Lex Fridman?

  The, the boundary between infinite and finite is incomprehensible for us humans anyway.

• 1:43:47Speaker 02

  Infinity is a good, is a useful way for us to think about extremely large, extremely large things. And, and, and we can, we can manipulate it, but, but we can never know that the universe is actually here and we're near that. So it just, so I realize how little we know.

• 1:44:19Speaker 02

  But, but, but we, we found an awful lot of, of, of things that are too hard for any one person to know, even with, even in our small universe.

• 1:44:31Lex Fridman?

  Yeah, and we did pretty good. So when you go up to heaven and meet God and get to ask one question that would get answered, what question would you ask?

• 1:44:47Speaker 02

  What kind of browser do you have up here?

• 1:44:52Speaker 02

  No, I actually, I don't think it's meaningful to ask this question, but I certainly hope we had good internet.

• 1:45:06Lex Fridman?

  Okay, on that note, that's beautiful, actually. Don, thank you so much. It was a huge honor to talk to you. I really appreciate it.

• 1:45:13Speaker 02

  Well, thanks for the gamut of questions.

• 1:45:16Lex Fridman?

  Yeah, it was fun. Thanks for listening to this conversation with Donald Knuth. And thank you to our presenting sponsor, Cash App. Download it, use code LEGSPODCAST, you'll get $10 and $10 will go to FIRST, a STEM education nonprofit that inspires hundreds of thousands of young minds to learn and to dream of engineering our future. If you enjoy this podcast, subscribe on YouTube, give it five stars on Apple Podcasts, support it on Patreon, or connect with me on Twitter. And now, let me leave you with some words of wisdom from Donald Knuth. "We should continually be striving to transform every art into a science, and in the process, we advance the art."

• 1:46:00Lex Fridman?

  Thank you for listening and hope to see you next time.