#219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life

Lex Fridman: the following is a conversation with Donald Kenneth his second time in this podcast. Don is a legendary computer scientist touring award winner. Father of algorithm analysis, author of the art of computer programming, creator of tech that led to lay tech and one of the kindest and most fascinating human beings I've ever got a chance to talk to. I wrote him a letter a long time ago. He responded and the rest as they say is history. We've interacted many times since then and every time it's been joyful and inspiring to support this podcast, please check out our sponsors in the description. As usual. I'll do a few minutes of us now. No ads in the middle. I try to make this interesting so hopefully you know skip but if you do please still check out the sponsor links in the description. It is in fact the best way to support this podcast. I use their stuff. I enjoy it. Maybe you will too. This show is brought to you by coin base which is a trusted and easy to use platform to buy, sell and spend. Cryptocurrency. I use it. I love it. You can buy a Bitcoin ethereum garden. Oh dodge coin and all the most popular digital currencies ever since I did a bunch of podcasts on Cryptocurrency. There would be people that come up to me kind of curious about Cryptocurrency and ask for advice on how they can get started with it and I always recommend coin base. I think it's the easiest way to uh buy Cryptocurrency and also to learn about the different cryptocurrencies. In fact I agreed at some point recently but also a long time ago to talk to a coin bay ceo brian armstrong on this podcast. He's a fascinating guy that's unrelated to the sponsorship but I very much look forward to uh that because I liked the way he uh looks at the digital currency. But even just the technology world anyway, go to coin base dot com slash lex for a limited time. New users can get $5 in free Bitcoin when you sign up today at coin base dot com slash lex. That's coin base dot com slash lex. This show is also brought to you by Inside Tracker, a service that used to track biological bio data. They have a bunch of plans, most of which include a blood test that gives you a lot of information that you can then make decisions based on. They have algorithms that analyze your blood data. DNA data and fitness tracker data to provide you with a clear picture of what's going on inside you and to offer you science backed recommendations for positive diet and lifestyle changes. The great the powerful Andrew Huberman talks a lot about Inside Tracker. David Sinclair also talks a lot about Inside Tracker including in my conversation with him. They love it. I love it in general. I just love the idea of using actual data from your body to make actionable decisions about lifestyle for a limited time you can get 25% off the entire inside trackers story if you go to inside tracker dot com slash lex, that's inside Tracker dot com slash lex. This show is also brought to you by net suite. That's what allows you to manage financials, human resources, inventory, e commerce and many more business related details all in one place. Running a company of any size really is very hard because of all the moving pieces involved. I've actually recently had a few conversations with Jim Keller offline about various aspects of what it takes to not just design great products but manufacture them at scale. It's a lot easier than it sounds if you make good decisions and think from first principles and make great hiring decisions. So you build a great team. But it's also a lot more difficult if you go in naively it can be both easier than you think and harder than you think depending on the choices you make. And again, depending on the tools you use anyway right now, special financing is back for net suite Head to netsuite dot com slash legs to get their one of a kind financing program that's not sweet dot com slash lex. That's sweet dot com slash lex. This show is also brought to you by express VPN. I use them to protect my privacy on the internet. I S B s are able to collect your data. You know, use the VPN even when you're using incognito mode on your browser, it can still collect the data. So if you want to protect yourself from the sbs and use a great tool for the job of preserving your privacy, you should definitely use a VPN and express VPN is my favorite. VPN. Another useful reason to use expressive pianist. You can change your location to watch shows that are only available to certain parts of the world so you can travel the world without ever actually leaving your computer. Finally, I really just enjoy the quality of the interface. It does one job and it does it really well. It works on basically any operating system including Lennox, my favorite operating system. But anyway, if you go to express VPN dot com slash like spot, you'll get extra three months free that express VPN dot com slash lex pod. This episode is also brought to you by better help spelled h E L p help. They figure out what you need and match you with a licensed professional therapist in under 48 hours. I've actually recently had a conversation with jay Mcclelland who is one of the seminal figures in the early history of artificial intelligence and neuroscience sort of at the intersection of those or perhaps not neuroscience but also cognitive science. So that whole sort of mix of biology and computation. He was part of the group with Geoff Hinton from which emerged the back propagation paper. Anyway, I mentioned all that because I had a conversation with him about psychiatry. He also wanted to be a psychiatrist growing up as I have. And so very much believes in the magic of talk therapy, of exploring the human mind through talking. And so I think better help. It's worth trying. It's easy, private, affordable, available worldwide. Check them out at better help dot com slash lex. That's better help dot com slash lex. This is a lex Friedman podcast.

Lex Fridman: And here is my conversation with Donald Knuth, Your first large scale program. You wrote it in IBM 650 assembler in the summer of 1957.

Donald Knuth: I wrote it in decimal machine language. I didn't know about assembler until a year later,

Lex Fridman: But the year 1957. The year. And the program is

Donald Knuth: Yeah, I might have learned about assembler later that summer. I probably did 957, hardly anybody had heard of assemblers. You looked at the user manuals, how did you write a program for this machine? It was, It would say uh you know, you would say 69, which meant load the distributor and then you would give the address of the number you wanted to load into the distributor. Uh yesterday my friend at Doug Spicer at the Computer history Museum sent me a link to something that just went on youtube. It was the iBMS uh progress report from 1956 which is, you know, very contemporary with 1957. Um and in 1956 IBM had donated to stanford University An IBM 651 of the first ones when they showed a picture of the assembly line for IBM six fifties and they said you know this is number 500 or something coming off the assembly line. And I had never seen so many IBM 6 56. I did in this movie that was on Youtube now. Uh and and it showed the picture from stanford uh that you know, they said look, you know, we we donated one of these two stanford one to M. I. T. And they mentioned one other, one other college. And in December of 56 they donated to my university case tech. Um but anyway They showed a picture then a class session where a guy was teaching programming and on the blackboard it said 69 8000. I mean he it was he was teaching them how to write uh code for the IBM 6 50 which was in decimal numbers. So the instructions were tended 10 decimal digits. You have two digits and said what what to do, four digits to say. Uh what to do it, two and four more digits to say where to get your next instruction.

Lex Fridman: And there's a manual that describes what each of the numbers mean. And

Donald Knuth: Emmanuel was actually one. Uh If the manual had been well written I probably never would have gone into computer science but it was so badly written, I figured that I must have a talent for it because I'm only a freshman and I and I could write a better manual. Uh You did and so I I started working at the computer center uh and And uh wrote some manuals that, but but but but this was uh but this is the way we did it. And my first program then was June of 1957.

Lex Fridman: The tic tac toe.

Donald Knuth: No, that was the second program, the 1st 3rd program, the first program was factor in a number. So you dial the number on the on the uh the switches, I mean you sat at this big man mainframe and you turn the dials set a number and then it would punch out the factors of that number on cars.

Lex Fridman: So that's the input, is the

Donald Knuth: input was yeah, the input, what, what was the number attended a number. And and uh and the output was its factors and and and I wrote that program, uh I still have a copy of it somewhere.

Lex Fridman: And um how many lines of code do you remember?

Lex Fridman: Well,

Donald Knuth: yeah, it started out as about 20, but then I kept hearing me debug it, I discovered debugging of course when I wrote my first program. And

Lex Fridman: what does the debugging look like on a program with just all numbers?

Donald Knuth: Well, you sit there and you, I don't remember how I got it into the machine, but but I think there was a way to punch, punch it on cards so each each instruction would would be 11 card. Or maybe I could get seven instructions on the card to read instructions. I don't know. But anyway so I'm sitting there at the at the council of the machine. I mean I'm doing this at night when nobody else is around of course. Um and and so you have one set of switches where you dial the number I'm inputting but there's another switch that you know that says okay now execute one instruction and show me what you've done what you did. Or you or you there was another four switches and say stop. If you get to those if you get to that instruction so I can see now go until you get there again and watch. Okay so I could watch, you know it would take that number and divide it by two and if it's you know there's no remainder then. Okay too is a factor. So so then I work on but if if if not divisible by two, divide by three. Okay keep trying and uh until you know you're you're at the end

Lex Fridman: and uh you would find a bug if uh if you were just surprised that something weird happened.

Donald Knuth: Well certainly I mean first of all I might have You know try to divide by one instead of two off by one errors that people make all the time. But maybe I go to the wrong instruction, maybe I you know, maybe I I left left something in a register that I shouldn't have done, but the first bugs were pretty, you know, I probably uh on the first night I was able to I was able to get the factors of 30, you know, is equal to 23 and five. Okay. Um

Lex Fridman: so you're sorry to interrupt, You were so you're sitting there late at night, so it feels like you spent many years late at night working on a computer. So like what's that like? So most of the world is sleeping and you have to be there at night because that's when you get access to the computer

Donald Knuth: between my freshman sophomore year, I didn't need to sleep, I used to do all night when I was in high school, I used to I used to do the whole student newspaper every monday night. I would, you know, I just stay up all night and and it would be done on Tuesday morning. Um uh that was, I didn't get ulcers and stuff like that until later. Yeah, but

Lex Fridman: uh well uh I don't know if you know Rodney brooks, Rod brooks of course, yeah, he told, he told me a story that he really your you know, he really looked up to you, he was actually afraid of you uh because he was uh but when he tells a story, when you were working on tech that they screwed up something with a machine, I think this might have been m I. T I don't know. And you were waiting for them to fix the machine so you can get back to work late at night. Oh, that happened all the time. He was really intimidating. He's like doc and youth is not happy with.

Donald Knuth: That's interesting. But no, no, the machine at stanford Ai lab was uh was down an awful lot because we they had uh they had many talented programmers changing the operating system every day. And so operating system was getting better every day, but it was also crashing. So so so I wrote almost the entire manual for tech during downtime. Uh but that's another story.

Lex Fridman: Okay, well, he was saying they it's a hardware problem, they they tried to fix it and they re inserted something and smoke was everywhere. He was,

Donald Knuth: it didn't happen as often as the operation. But yeah,

Lex Fridman: it was, it's a funny story because you're saying there's this tall uh don knew that I look up to and I see it was pressure to, I think the computer. Well, it's funny, okay, the kind of things we remember that stick in Our

Donald Knuth: memory. Well, okay, yeah, well, I can tell you a bunch of Rod Brooks story. Stupid. Let's let's go back to the 50. So Uh so I'm debugging this, my first program and I I had more bugs in it than a number of lines of code. I mean, the number of lines of code kept growing and let me explain. So, I had to punch the answers on cards. All right. So suppose I suppose I'm factoring the number 30. Then I got then I I gotta I gotta put two somewhere on the car and I got to put a three somewhere on the car. And I got to put a five somewhere on the card. Right? And, and you know what? It was my first program. I I probably screwed up and, you know, it fell off the edge of the card or something like that, but, but I didn't realize that there was some tentative numbers that have That have more than eight factors. Um, and the card has only 80 columns. And so I need 10 columns for every factor. So, my first program didn't take account for the fact that I would have to punch more than one card. My first program, you know, just lying the stuff up in memory and then I punched the card. But after, you know, so by the time I finished, I had to had to deal with lots of lots of things. Also, I, Uh, if you put a large prime number in there, my program might have said there for 10 minutes or 650 was pretty slow. And so it would sit there spinning its wheels and you wouldn't know if it was in a loop or whatever

Lex Fridman: that tended is.

Donald Knuth: Yeah, so I think the largest, his sort of 9999999997 or something like that? That would you know that that would take me a while uh for that first point anyway, that was my first program. Well,

Lex Fridman: what was your goal with that program? You were hoping to find a large prime maybe, or no, the opposite.

Donald Knuth: You know? My goal was to see the lights flashing and understand how this magical machine would be able to do something that took so long by hand.

Lex Fridman: So what was your second program?

Donald Knuth: My second program was a converted number from from binary to decimal or something like that. It was much, much simpler. Didn't have that many bugs in it. My third program was tic tac toe

Lex Fridman: and he had some, so the tic tac toe program, it's interesting on many levels, but one of them is that it had some, you can call machine learning in it.

Donald Knuth: That's yeah, that's right. Uh I don't know how long it's gonna be before the name of our field has changed from computer science to machine learning, but uh but anyway, uh it was my first experience with machine learning because okay, so here we had,

Lex Fridman: how does the program? Well, first of all, what is the problem you were solving? What is Tik Tak toe, What are we talking about? And then um Right, what, how was it designed?

Donald Knuth: Right so you got you got a three by three grid and each it can be in three states, it can be empty or it can have an excellent. Oh alright so three to the ninth is a uh well what is how big is it should know but it's 80, 81 times 81 times three. So um Anyway eight is like two to the third and so that would be uh that would be like two to the sixth. uh but that would be 64 then you have to anyway

Lex Fridman: I love how you're doing the calculation. So a lot of anyway the three comes from the fact that it's either empty an X. Or an O.

Donald Knuth: And The 6:50. What was it was a machine that had only ah 2000. Yeah yeah 10 digit words you go from 0000 to 1999 and that's it and each word you have a 10 digit number so that's not many bits. I mean I got to have in order to have a memory of every position I've seen I need 3 to the 9th bit. Uh Okay but it was a decimal machine to, it didn't have this but it did have it did have a strange instruction where if if you had a 10 digit number that but all the digits were either eight or nine uh You'll be 89988 or something like that Would uh You can make a test whether it was eight or nine. That was one of the strange things IBM engineers put into the machine. I have no idea why. Well um hardly ever used but anyway I needed one digit for every every position I've seen. Zero met it was a bad position. I meant it was good position. I think I started out at five or six. You know? But if you if you win a game then you uh then you increase the value of that position for you but you decrease it for your opponent. Uh But but I could I had that much total memory for every every possible position was one digit and I had a total of 20,000 digits which had which had to also include my program and all the logic and everything including how to how to ask the user what the moves are and things like this. Okay so so I think I had to work it out. Get every every position in tic tac toe, It is equivalent to roughly eight others because you can rotate the board um which gives you a factor of four when you can also flip it over. And that's another factor too. So I might you know, so I might have needed only three to the 9th over eight positions of a plus a plus a little bit. Uh So I had but anyway that was that was a part of the program to squeeze it into this tiny,

Lex Fridman: so you tried to find an efficient representation that took account for that kind of rotate. I

Donald Knuth: had to otherwise I couldn't do the learning. Um, so, so, but but I had three parts of my tic tac toe program. Uh and I call it brain one, brain 2 in brain three. So brain one just played a uh let's see it at random. Okay, it's your turn. Okay? You gotta put an X. Somewhere has to go on an empty space. But that's that's it. Okay, choose Choose one and play their brain to uh had a candle routine. And I think it was, it also, maybe it had maybe to assume you were the first player or maybe it allowed you to be first. I think you're hard to be either first or second, but had a canned built in strategy known to be optimum for detect. Oh, before I forget, by the way I learned uh, many years later that Charles Babbage had had planned to have thought about programming tic tac toe for his, for his dream machine that he, that he was never able to finish.

Lex Fridman: So that was the program he thought about

Donald Knuth: more than 100 years ago. He had uh, he did that. Okay. And I had, and I had been influenced by a demonstration at the Museum of Science and industry in Chicago. It's like, it's like boston's science museum. I think bell labs had had prepared a special exhibit about a telephones and relay technology and they had a tic tac toe playing uh, machine as part of that exhibit. So that had been one of my uh, you know, something I'd seen before. I was a freshman in college and and inspired me to see if I could write a program for, okay, so anyway, I brain one random uh, knowing nothing brain to knowing everything. Then brain three was the learning one and I could, I could play brain one against brain one brain one against brain to and so on. And so uh, You can also play against the user against a live in person. But uh, so I started going the learning thing and I said, Okay, you know, take two random random people just playing, uh, detect oh, uh, knowing nothing. Um, and after about, I forget the number now, but it converged after about 600 games uh, to a safe draw. The way my program learned was actually, it learned how not to make mistakes because uh it didn't try to do anything for winning, It just tried to say news.

Lex Fridman: So that

Donald Knuth: was probably because of the way I designed to learn anything. I could have had a different uh, reinforcement function that would, that would reward brilliant play. But anyway, it didn't and uh, and if if I took a novice against uh, you know, the skilled player, uh it was able to learn how to play a good game. So that was?

Donald Knuth: And that was really my, but after I finished that, I felt I understood programming

Lex Fridman: was there. Did you did a curiosity and interest in learning systems persist for you? So Why, Why did you want brain 3 to learn?

Donald Knuth: Yeah, I think naturally it's, we're talking about Rod brooks. Uh He he was teaching all kinds of very small devices uh to to learn stuff um if a leaf drops off of a tree, uh uh you know, he was saying something while it learns if there's wind or not, but I mean he he pushed that a little bit too far, but he said he could probably train some little mini bugs to scour out dishes if he had enough a financial support. I don't like

Lex Fridman: that. Can I, can I ask you about that? Because um he also mentioned that during those years, there was discussion about inspired by touring about computation. You know, of what is computation? Yeah. And

Donald Knuth: yeah, I never thought about any stuff like that. That was that was way too philosophical. I was I was a freshman after, I mean, I didn't, I was pretty much a machine.

Lex Fridman: So it's almost like, yeah, I got you. It's a tinkering mindset. Uh not a philosophical mindset,

Donald Knuth: it was just exciting to me to uh to be able to control something, but not, but not, but not to say my solving a big problem or something like that Or is this a step for humankind? Right. No. No.

Lex Fridman: When did you first start thinking about computation in the big sense? You know like the universal turing machine? Well

Donald Knuth: I mean I had to pass and I had to take I had to take classes on compute ability when I was a senior. So you know we read this book by martin Davis and yeah this is cool stuff but you know I learned about it because I know I need to pass the exams but I didn't I didn't invent any of that stuff but I had create fun playing with the machine. You know I um I wrote program because it was fun to write programs and get this. I mean it was like watching miracles happen.

Lex Fridman: You mentioned in an interview that when reading a program you can tell when the author of the program changed

Donald Knuth: uh

Lex Fridman: how the heck can you do that? Like what makes a distinct style for programmer do you think? You know there's different Hemingway has a style of writing versus James Joyce or something? Well those are

Donald Knuth: pretty, yeah those are pretty easy to imitate but it's the same with music and whatever you can. I found uh well during the pandemic I spend a lot more time playing the piano and I found something that I'd had I had when I was taking lessons uh before I was a teenager and uh it was yankee doodle uh played in the style of you know, and you had you had you had Beethoven and you had W. C. And Chopin and you know, and the last one was Gershwin and and I played over and over again. I thought it was so brilliant. But but it was so easy. But also to appreciate how this uh this uh author Mario somebody or other had have been able to reverse engineers the styles of those computers. So but now particularly uh to your question, I mean there would be there, it was it was pretty obvious in this program I was reading, it was it was a compiler uh and it had been written by a team at at Carnegie Mellon and I have no idea which program was responsible for, but you would get to a part where the guy would just not know how to how to move things between registers very efficiently and so and so everything that that could be done and one instruction would take three or something like that, that would be a pretty obvious change in style, but there were but then they were also flashes of brilliance where you could do in one instruction. Normally I used to because you knew enough about the way the machine work that you could that you could accomplish two goals in one step. So it was mostly the brilliance of the concept more than the semi colons and or the you know the use of short sentences versus long sentences.

Lex Fridman: So you would see the idea in the code and yeah, see the different style thinking. It was

Donald Knuth: yeah, it was stylistic. I mean I could identify authors by their, by the amount of technical aptitude they had, but not by style in the sense of a rhythm or something like that.

Lex Fridman: So if you think about Mozart, Beethoven bach, if somebody looked at don canoe the code, would they be able to tell that this is a distinct style of thinking going on here? What do you think? Uh and what what would be the defining characteristic of the style?

Donald Knuth: Well, my code now is is literate programming. So I'm it's a combination of english and see mostly, but if you just looked at the sea part of it, you would also probably notice that I don't, you know, that I use a lot of global variables that other people don't and I expand things in line more than instead of calling anyway, I have different subset of C that I use.

Lex Fridman: Okay, but that's a little bit stylistic. Uh but

Donald Knuth: but with literate programming, you alternate between english and and see or whatever and

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

Donald Knuth: Yeah, yeah, I'm that's the most uh significant thing I think to come out of the tech project. It is that I I realized that uh programs were to be read by people and not just by computers and and that typography could massively enhance that. And and so uh I mean it they're just wonderful if they're going to look it up, that they should also look up this book by called physically based rendering by matt far and gosh, anyway, it got an academy award. But it's but all the all the graphic effects you see in movies, uh you know, are accomplished by algorithms in this book is the whole book is illiterate program. It tells you not only how you do all the shading and and uh bringing images in that you need for animation and textures and so on. But it also you can run the code uh and and so I find it uh uh extension of the way i uh of how to teach programming. It is but by by telling a story as part of the program.

Lex Fridman: So it's uh it works as a program but it's also readable by humans.

Donald Knuth: Yes. And especially by me. Uh Yeah, a week later, a year Later.

Lex Fridman: That's a good test. If you yourself understand the code easily a week or 30 year later.

Donald Knuth: So it's uh this place, it's the greatest thing since sliced bread

Lex Fridman: programming or literate literate program.

Donald Knuth: Okay.

Lex Fridman: Uh you heard it here first. Okay. You dodged this question in an interview I listen to. So when you ask you again here, uh, what makes for a beautiful program?

Donald Knuth: What makes for a beautiful program?

Lex Fridman: What are the characteristics you see? Like you just said literate programming? What are the characteristics you see in a program that make you sit back and say, that's pretty good?

Donald Knuth: Well, the reason I didn't answer is because there are there are dozens and dozens of answers to that.

Donald Knuth: Because each you can define beauty the same personal. Do you find beauty in a different way from our our I mean, it depends on what on what you're looking for at one level. It's beautiful. Just if it works at all another level. It's beautiful. If it's, if it uh, it can be understood easily. It's beautiful. If it, uh, if it's a literate programming is beautiful, it makes you laugh. I mean,

Lex Fridman: yeah, I'm actually, so I'm with you. I think beauty. If it's readable,

Donald Knuth: readable

Lex Fridman: is if you understand what's going on and also understand the elegance of thought behind it.

Lex Fridman: And then also, as you said, wit and humor, I was always uh, remember having this conversation, I had this conversation on stack overflow. Whether humor is good in comments and I think it is whether

Donald Knuth: it is good in comments.

Lex Fridman: Like when you add comments in code, I I always thought a little bit of humor is good. It shows personality. It shows character shows wit and fun and all those kinds of things of the personality of the program.

Donald Knuth: Okay, so, uh, a couple days ago I received a wonderful present from my former editor at Aston Wesley, he's downsizing his house and he found uh that somebody at the company had Had found all the all of their internal files about the art of computer programming from the 1960s. And they gave it to him. Uh and then uh, you know, before throwing throwing in the garbage. And then so he said, Oh yeah, he planned to keep it for posterity, but now he realized that posterity is a bit too much for him to handle. So he sent it to me. Uh, and so and so I just received this big, big stack of, of letters, uh some of which I had written to them, but many of which they had written to early guinea pigs who were telling them whether they should publish or not, you know? And and one of the things I was uh in the in the comments to volume one, uh uh the major the major reader was, was bob Floyd, uh who is my great uh co worker in the sixties, um died early unfortunately. But uh and and he he commented about the humor in it. And so we had, you know, he ran it by me, you know, says, keep this joke in or not, you know, uh you know, they also send it out to focus group, what do you think about humor in a in a book about computer program? And I stated my philosophy is it said, you know, the ideal thing is uh that it's something where the reader knows that there's probably a joke or if you only understood it and this is a motivation to understand, to think about it a little bit. But anyway, it's a very delicate humor. I mean, it's really uh each each century invents a different kind of humor too. I mean, different, different cultures have different, different kind of humor.

Lex Fridman: Um Yeah, like we talked about Russia a little bit offline, you know, there's dark humor, you know, when a country goes to something different

Donald Knuth: that I live and stuff like this and you and Jack Benny, I mean, steve Allen wrote this book about humor and it was the most boring book, but he was one of my idols, but but uh it's called the Funny men or something like that. But yeah, okay, so anyway, I think it's important to know that that this is part of life and and and it should be fun and not. And so, you know, I wrote this this organ composition which uh based on the bible, but I didn't refrain from putting little jokes and also in the music

Lex Fridman: getting in the music.

Donald Knuth: It's it's it's there. Yeah,

Lex Fridman: a little humor is okay.

Donald Knuth: Yeah. I mean, not Egregious. Um So in this correspondence, you know, there were there were things I said, yeah, I really shouldn't, I really shouldn't have done that. But other ones I yo who insisted on and I've got jokes in there that that nobody has figured out you. In fact in volume two, I've got a cryptogram, a message in Seaford. And in order to decipher it, you're going to have to have to break in our s a key which is larger than people know how to break. Uh So, you know, if computers keep getting faster and faster than, you know, might be 100 years, but somebody will figure out what this message is and they will laugh. I mean, I've got a joke in there.

Donald Knuth: Uh

Lex Fridman: So that one you really have to work for. Uh I don't know if you've heard about this. Let me explain it. Maybe you'll find it interesting. So, open Ai is a company that does a. I work and they have this language model, it's a neural network that can generate language pretty well. But they also on top of that developed something called Open Ai codex. And together with GIT hub, they developed a system called Open Ai co pilot. Let me explain what it does. There's echoes of literate programming in it. So what you do is you start writing code and it completes the code for you. So for example, you start let's go to your factoring program, you start you write in javascript and python in any language that are trained on uh you start you write the first line and some comments like what this code does and it generates the function for you and it doesn't incredibly good job, like it's not probably right, but often does a really good job of completing the code for you

Donald Knuth: to see whether, but how do you know whether it did a good job or not?

Lex Fridman: You can see a lot of examples where it did a good job. And so it's not a thing that generates the code for you, It starts it gives you uh so it puts the human in the seat of fixing issues versus writing from scratch. Do you find that kind of idea at all interesting

Donald Knuth: every year we're going to be losing more and more control over what machines are doing and people are saying, Well, it seems like when I was a professor at caltech uh in the in the 60s, we had this this guy who who talked a good game, he could give inspiring lectures and you'd think, well uh throwing things, he was talking about an hour later, you said, well, what did he say? Um uh but he really felt that it didn't matter whether computers got the right answer or not, it's just a matter whether it made you happy or not. In other words, if you know, if your boss paid for uh, you know, then you had a job, you could you could you could take care of your

Lex Fridman: wife. Happiness is more important than truth.

Donald Knuth: Exactly. He didn't believe in truth, but he was a philosopher,

Lex Fridman: I like it. Uh, and somehow you see,

Donald Knuth: uh, we're going that way. I mean, so many more things are taken over by saying, well, this seems to work. And when there's, when there is a competing interests involved, neither side understands why the decision is being made. Uh, you know, we realize now that it's that it's bad, but, but consider what happens five years, 10 years down the line when things get even more further detached. Each thing is based on something from the previous year.

Lex Fridman: So you start to lose, the more you automate, the more you start to lose track of some deep human essentially exponentially. But so that's the dark side. The positive side is, the more you automate, the more you let humans do what humans do best. So maybe programming this, you know, maybe humans should focus on a small part of programming that requires that genius the magic of the human mind and the mess you let the machine generate. Yeah, I mean, that's the, that's the positive, but of course it does come with the darkness like automation. What's better correct? I'm

Donald Knuth: never going to try to write a book about that. Uh, I'm never going to recommend to any of my students to work for them.

Lex Fridman: You're on the side, I'm on the side,

Donald Knuth: I'm on the side of understanding understanding, I understand. Uh, and I think these things are really marvelous if they if if what they do is, you know, all of a sudden we have a better medical diagnosis or or or help guide some scientific experiment or something like this. Uh, you know, curing diseases or what whatever. But when it when when it affects people's lives in a serious way. Uh So if you're writing, if you're writing code, oh yeah, here this is great. Uh this will make a slaughter. But okay,

Lex Fridman: so I see. So you have to be very careful. Like right now it seems like fun and games. It's useful to write a little javascript program that helps you with the website. But like you said, one year passes two years passes five years and you forget you start building on top of it and then all of a sudden you have autonomous weapons systems based on

Donald Knuth: what we're all dead. Doesn't matter. And that's it.

Lex Fridman: Well, in the end, this whole thing ends anyway. So, um, but there is

Donald Knuth: a heat death of the universe a predicted. But I'm trying to postpone that for for a little bit,

Lex Fridman: we'll be nice that at the end as we approached the heat death of the universe. There's still some kind of consciousness there to to to to appreciate it. Hopefully human consciousness,

Donald Knuth: I'll settle for 10 to the 10 to the 10 to the 10th year. There's some finite number. But things like this might be the reason we don't pick up any signals from extraterrestrial.

Lex Fridman: They don't want anything to do with us. Oh because they because they

Donald Knuth: invented it to and

Lex Fridman: so you you do have a little bit of worry on the existential threats of ai and automation. So like, like removing the human from the picture.

Donald Knuth: Yeah. People have more potential to do harm now than by far than they did 100 years ago.

Lex Fridman: But are you optimistic about the humans are good at creating destructive things, but also humans are good at solving problems. Yeah.

Donald Knuth: I mean, there's half empty and half full, you know? So

Lex Fridman: so how would we have full? I can go.

Donald Knuth: Yeah. So let me let me put it this way, because because it's the only way I can be optimistic, but think of uh things that have changed because of civilization, you know, they don't occur just in nature. So just uh just imagine the room we're in, for example. Uh Okay, um you know, we've got pencils, we've got books, we've got tables, we've got microphones, clothing, food, all these things were added. Somebody invented them one by one, millions of of things uh that we inherit. Okay. Um And uh it's inconceivable that that so many millions of billions of things wouldn't have problems and we get it all right. Um And and each one would have no negative uh effects and so on. So it's very amazing that much works as does work it.

Lex Fridman: it's incredibly amazing and actually that's the source of my optimism as well, including for artificial intelligence? So we we drive over bridges, we uh, we use all kinds of technology. We don't know how it works. And there's millions of brilliant people involved in building a small part of that and it doesn't go wrong and it works and I mean that it works, it doesn't go wrong often enough to suffer.

Donald Knuth: And we can identify things that aren't working and try to improve on them

Lex Fridman: in a sub often suboptimal way. Absolutely. But

Donald Knuth: the the kind of things that I know how to improve require human beings to be rational and I'm losing my confidence that human beings are rational.

Lex Fridman: Yeah, yeah. Now here you go again with the worst case uh worst case analysis. Uh they may not be rational, but there um they're they're clever and uh beautiful in their own kind of way.

Lex Fridman: I tend to think that most people um have the desire and the capacity to be good to each other and love will ultimately went out like if if they're given the opportunity, that's where they lean in the art of computer programming, you wrote The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times premature optimization is the root of all evil in parentheses? Or at least most of it in programming. Can you explain this idea? What's the wrong time? What is the wrong place for optimization.

Donald Knuth: So first of all the word optimization, I started out writing software uh and optimization was I was a compiler writer. Seo optimization meant uh making the uh making a better translation so that it would run faster on a on a machine. So an optimized program is just like you know, you you want a program and you set the optimization level. Uh the compiler. So that's one word for optimization. Um And at that time I happened to be looking at an unabridged dictionary uh for some reason or other and I came toward optimizes what's the meaning of the word optimized and it says to view with optimism. And and you you look in Webster's Dictionary of English language in 1960s or the 1960s, that's what optimized me meant. Okay. Um now, so people started doing cost optimization are the kinds of things uh you know, whole sub fields of of uh algorithms and economics and whatever are based on what they call optimization now. But to me, optimization when I was saying that was saying uh changing a program to make it more attuned to the machine. And I found out that uh when a person writes a program uh he or she tends to think that the parts that were hardest to write are going to be hardest for the computer to execute. So maybe have 10 pages of color but I had to work a week writing this page. I mentally think that when they computer gets to that page is going to slow down. Uh, Oh, I don't understand what I'm doing better be more anyway. This is of course silly. But it's something that we, that we, that we don't know when we got a piece of code, we don't know what whether the computer is actually going to be executing that code. Very much so. People have had a very poor understanding of, of what the computer was actually doing. I made one test where we studied a FORTRAN compiler And it was spending more than 80% of its time reading the comments card. Um, but as a programmer, we were really concerned about how fast it could take a complicated expression that had lots of good levels of parenthesis and convert that into something, But that was just, you know, less than 1% of the uh, so if we optimize that, Uh, we didn't know what we were doing, but if we knew that it was spending 80% of his time on the comment card, you know, in 10 minutes, we could, we could make the compiler run more than twice as fast

Lex Fridman: and you can only do that once you've completed the program and then you empirically study where

Donald Knuth: I had some kind of profiling that I knew what was important.

Lex Fridman: So you don't think this applies generally. I mean, there's something that rings true to this across. I'm glad

Donald Knuth: that it applied generally, but it was it was only my good luck I said it but you know, but I did but I said it in a limited context or not and I'm glad if it makes people think about stuff because I'm but it applies in another sense to that is um sometimes I will do optimization in a way that does help the the actual running time but makes the program impossible to change next week because I've changed my data structure is something that made it less adaptable. So one of the great uh principles of computer sciences is it his laziness or whatever you call it? Uh late binding uh you know, don't hold hold off decisions when you can um and you know, and we understand now uh quantitatively how valuable that is.

Lex Fridman: What do you mean? We understand. So you mean

Donald Knuth: People people have written thesis about how you can how late binding will improve the I mean, you know, just in time manufacturing or whatever you can make, you can defer a decision instead of doing an advanced planning and say I'm going to allocate 30% to this in 50 percent.

Lex Fridman: So in all kinds of domains there's an optimal itty to laziness in many cases the

Donald Knuth: decision is not made in advance. So instead you design in order to be flexible uh to change with the uh with the way the wind is blowing.

Lex Fridman: Yeah, but so the reason that line resonated with a lot of people is because uh there's something about the programmer's mind that wants, that enjoys optimization. So it's a constant struggle, two balanced laziness and late binding with the desire to optimize the the elegance of a well optimized code is something that's compelling to programming.

Lex Fridman: Yeah,

Donald Knuth: it's uh another concept of beauty.

Lex Fridman: Let me ask you a weird question. So, Roger Penrose has talked about computation computers and he proposed that the way the human mind discovers mathematical ideas is something more than a computer that that a universal turing machine cannot uh do everything that a human mind can do. Now. This includes discovering mathematical ideas. And it also includes he's written a book about it, consciousness. So I don't know if you know Roger, but

Donald Knuth: do you think my uh my daughter's kids played with his kids? And

Lex Fridman: so do you think there is such a limit to the computer? Do you think consciousness is more than a computation? Do you think the human mind the way it thinks is more than a computation?

Donald Knuth: I mean, I can say yes or no, but I don't think I have no reason. I

Lex Fridman: mean, so you don't find it useful to have an intuition in one way or the other, Like when you think about algorithms, isn't it? I think it's ananda limits

Donald Knuth: unanswerable question in my opinion is is no better than anybody else, You

Lex Fridman: think it's unanswerable. So you don't think eventually signed

Donald Knuth: angels can dance on the head of it? I mean, I don't know,

Lex Fridman: but angels

Donald Knuth: uh anyway, there are lots of things that are beyond that we can speculate about, but I don't want somebody to say, oh yeah, can you said this? And and so he's smart. So that must be, I mean, I say it's something that we'll never know. Uh

Lex Fridman: interesting. Okay, that's a strong statement. I don't I personally think is something we will know eventually. Like there's no reason to me why the workings of the human mind are not within the reach of science.

Donald Knuth: That's absolutely possible. And I'm not denying it.

Lex Fridman: Uh But right now you don't have a good

Donald Knuth: I mean, that's also possible, you know, that ai you know, created the universe. Uh intelligent design is all has all been done by an ai uh this is I mean, all of these things are but but but but you're asking me to pronounce on it and I don't have any expertise. I'm a teacher that passes on knowledge, but I don't but I don't know the fact that I that I vote yes or no on.

Lex Fridman: Well, you do have expertise as a human, not as a not as a teacher or a scholar of computer science. I mean, that's ultimately the realm of where the discussion of human thought. Yeah, Well, I know we're in consciousness.

Donald Knuth: I know where Penrose is coming from. He, I'm sure he has no uh he might even thought he proved it, but

Lex Fridman: you know, he doesn't he doesn't prove he is following intuition,

Donald Knuth: but I mean, you have to ask john McCarthy, john McCarthy uh I think uh we're totally unimpressed by these statements.

Lex Fridman: Uh you don't think so, even like the touring paper on on the touring tests that, you know, starts by asking kIM machines, think uh you don't think these kind of uh he touring doesn't like that question.

Donald Knuth: I don't consider it important, let's let's put it that way because it's in the category of things that it would be nice to know, but I think it's beyond knowledge. And so I don't, I'm more interested in knowing about the remind hypothesis or something.

Lex Fridman: So when you say it's an interesting statement beyond knowledge, I think what you mean is it's not sufficiently, well, it's not even known well enough to be able to formalize it in order to ask a clear question. So that's why it's beyond knowledge, but that doesn't mean it's not eventually going to be formalized.

Donald Knuth: Maybe consciousness will be understood someday. Uh the last time I checked, Uh it was still 200 years away. I haven't been specializing in this by any means, but but I went to lectures about it 20 years ago when I was uh there was, there was a symposium at the american Academy in in Cambridge and it started out by saying essentially everything that's been written about consciousness is is hogwash. Er

Lex Fridman: I tend to I tend to disagree with that a little bit so well, so consciousness for the longest time still is in the realm of philosophy. So it's just conversations without any basis and understanding still, I think once you start creating artificial intelligence systems that interact with humans and they have personality, have identity, you start flirting with the question of consciousness not from a philosophical perspective, but from an engineering perspective and then starts becoming much more like I feel like

Donald Knuth: you don't misunderstand me, I I certainly don't disagree with that at all. Um and I even at these lectures that we had, you know, 20 years ago, there were neurologists pointing out that that human beings had actually decided to do something before they were conscious of making that decision. Uh I mean they could tell that, you know, that signals were being sent to their arms before they before they knew that they were uh things like this are true and and uh my less valiant has architecture for the brain and more recently, uh christmas puppet Dimitriou in the Academy Science Proceedings a year ago with with two other people, but I know Crystal very well. Uh and and he's got this uh this model of uh this architecture by which you could create a things that correlate well with uh with experiments that are done unconsciousness. Uh and any, he actually has a a machine language that in which you can you can write code and test hypothesis. Uh, and so it it might, you know, we might have a big breakthrough. My personal feeling is that consciousness, the best model I I've heard of, uh, to explain the miracle of consciousness, is that, uh, that somehow inside of our brains, we're having a uh, continual survival for the fittest competition. I'm speaking to you all the possible things I might be wanting to say. Are

Lex Fridman: you going?

Donald Knuth: Yeah. Right. Yeah. And one of them is winning, and and that's affecting, you know, the next sentence and so long. Uh, there was this book, Machine Intelligence on Intelligence on Intelligence. Yeah. Bill Atkinson was was was a total devotee of that book.

Lex Fridman: I like whether it's consciousness or something else. I like the storytelling part that we it feels like, uh, first humans, it feels like there's a concrete, it's almost like literally programming. I don't know what the programming going on on the inside, but I'm getting a nice story here about what happened, and it feels like I'm in control and I'm getting a nice clear story, but it's also possible there's a computation going on that's really messy. There's a bunch of different competing ideas, and in the end, it's just kind of generates a story for you to uh, a consistent story for you to believe, and that makes it all nice.

Donald Knuth: Yeah. And so I prefer to talk about things that I have some expertise and then then things which which I'm only a uh on the sideline.

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

Donald Knuth: I think the Game of Life is his wonderful. And I uh and and shows all kinds of stuff about how things can evolve without the creator understanding anything more than the power of learning in a way. But to me, the most of important thing about the Game of Life is, is how it focus for me, what what it meant to have free will or not, because the Game of Life is obviously totally deterministic. I find it hard to believe that anybody who's ever had Children cannot believe in free will. All right, on the other hand, this makes it crystal clear. Uh john Conway said, uh he wondered whether it was immoral to shut the computer off after he got into a particularly interesting play of the Game of Life.

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

Donald Knuth: if the universe is finite, we're all living in the game of life to slow down. I mean, it's sped up a lot. Uh

Lex Fridman: But do you think technically some of the ideas that you used for analysis of algorithms can be used to analyze the game of life? Can we make sense of it? Or is it too weird of?

Donald Knuth: You know, I mean, I've got I've got a dozen exercises in volume for fast. Ical six. Uh that actually worked rather well for that purpose. Bill Gosper is came up with the algorithm that allows allowed Golly too uh you know, to run thousands and thousands of times faster.

Donald Knuth: You know? The website called Golly T. O. L. L. Y. Just

Lex Fridman: it simulates the sell your item in a game of life.

Donald Knuth: Yeah. You got you got to check it out.

Lex Fridman: Can I ask you about john Conway?

Donald Knuth: Yes. In fact, I'm just reading now the the issue of mathematical intelligence or that came in last last week and the whole issue devoted to uh remember remembrance of him.

Lex Fridman: Did you know him?

Donald Knuth: I slept overnight in his house several times. I

Lex Fridman: yeah, he recently passed away.

Donald Knuth: You know, he he died a year ago. May I think it was of Covid,

Lex Fridman: what are you, what are some memories of him of his work that stand out for? You did uh on a technical level that any of his work inspire you on a personal level that did he himself inspire you in some way.

Donald Knuth: And you know, absolutely all of those things. But let's see, when did I first meet him? I guess I first met him at Oxford in 1967 when I was

Lex Fridman: Okay. That's a long time ago.

Donald Knuth: Yeah.

Donald Knuth: You were minus 20 years old or something, I don't know, 1967, but but uh, there was a conference where uh, I think I've spoken, I was speaking about something that no one has the canoes. Bendix algorithm now, but but he he gave a famous talk about knots and and at the, and I didn't know at the time, but anyway, that talk now uh the stories of thousands and thousands of papers since since then, uh and it was he was reported on something that he had done in high school, uh you know, almost 10 years earlier, uh, before this conference, but he never published it. And anti climax to stalk by building some Not so you have these little, these little plastic things that you that you can stick together. Uh it's something like lego but easier. Uh so he made a whole bunch of knots in front of the audience and so on. And then disassembled. It was a dramatic lecture before he had learned how to give even more dramatic lectures later. So all right. And

Lex Fridman: were you at that lecture? And

Donald Knuth: I was there, Yeah, because I had, you know, I was at the same conference um for some reason I was I happened to be in in Calgary uh at the same day that he was visiting Calgary. And it was the spring of 72, I'm pretty sure. And and we had lunch together and he wrote down during the lunch on a napkin, all of the facts about what he called numbers. Uh and I and uh and he covered the napkin with the theorems about his his idea of numbers. And I thought it was incredibly beautiful. Um and and later in 1972, my sabbatical year began and I went to Norway and in december of that year, uh in the middle of the night, the thought came to me, you know, Conway's theory about numbers would be a great think, teach students how to invent research and what the joys are of research. And and and so I said, and I had also read a book and dialogue. Bye bye. Alfred renew. Uh We're kind of a Socratic thing where they're two characters were talking to each other about mathematics. And so I and so at the end in the morning, I woke up my wife and said, Jill, I think I want to write a book about Conway's theory. And um, you know, you know, I'm supposed to be right in the art of computer programming, doing all this other stuff. But I got, but I really want to write this other book. And so we made this plan, but I said I thought I could write it in a week and we made the plan then. So in january, I rented a room in a hotel in downtown Oslo were on sabbatical in Norway. Uh and I ran at the hotel in downtown Oslo and did nothing else except right up Conway's theory. And I changed the name to surreal numbers. That so this book is now published a surreal number. And and you know, we figured out, we always wondered what would you like to have a fair enough hotel rooms. So, so we figured out that she would visit me twice during the week. Things like this. You know, we would, you know, try to sneak in. This was hotel was run by a mission organization. These ladies were probably very strict. But anyway, so, so uh in the wild week

Lex Fridman: in every way. But

Donald Knuth: the thing is I had lost that I had lost that napkin in which he wrote the theory, but I looked for it, but I couldn't, so I tried to recreate from memory what he told me. He had that lunch uh in Calgary. And and as I, as I wrote the book, I was going through exactly what I what the characters in the book we're supposed to be doing. So I start with the with the two axioms that start out the whole thing and everything is defined flows from that, but you have to discover why and and as every mistake that I make, as I'm trying to discover it, uh my characters make to, you know, and and and and so it was just a long, long story, but I work through this week uh and it was it was one of the most exciting uh intense weeks of my life and uh I described it in other places. But anyway, uh after six days I I finished it and on the seventh day I rested and and I sent uh my secretary to type it. It was flowing as I was writing it uh faster than I could think almost. Uh but after I finished uh and try to write a letter to my secretary, telling her how to type it. I couldn't write anymore uh to give it ever the muse had left me completely. Uh

Lex Fridman: can you explain how that we could have happened? Like why that seems like such a magical week.

Donald Knuth: I have no idea. But anyway, there was something, it was almost as if I was channeling. So, so the book, it was type, they sent it to Conway and and he said, well done, You got the accident, one accident wrong. Uh there's a difference between um less than or equal and not greater than, I don't know the opposite of being greater than and less than or equal. But anyway, technically it can make a difference when you're developing a logical theory and the way I had chosen was harder to to do than john's original. So um and we visited him at his house in Cambridge in april, we took a boat actually from Norway over to across the channel. And and so I didn't stay with him for some days. And and uh he told, he talked, we talked about all kinds of of things. He has he had puzzles that I'd never heard of before. He had a great way to to solve the game of solitaire, many of the common interest that we, you know, he had never written up. But anyway, uh then in the summertime I took another week off and went to a place in in the mountains of Norway and rewrote the book using the correct accent. And so that was the most intensive connection with with with with Conway after that

Lex Fridman: started with a napkin

Donald Knuth: and started with a napkin. But but but we would run into each other. Yeah, the next really, and I was giving lectures in Montreal. Uh giving a series of Of of seven lectures about the topic called stable marriages. And and and he arrived in Montreal uh between my 6th and 7th lecture and and we met at a party and I started telling him about the topic I was doing. And uh he sat and thought about it. He came up with a beautiful theory to show that the uh I mean in technical terms it's it's that the that the set of all stable marriages, it forms a lattice. And and there was a simple way to find the greatest floor bound and of two stable pairings and least upper bound to stable marriage. And so I could use it in my lecture the next day. And he came up with this theme, you know, during the party. Uh it's a distributed last, I mean it's uh you know uh it added greatly to the theory of of stable magic.

Lex Fridman: So you mentioned your wife Jill much a stable marriage, Can you tell the story of how you two met?

Donald Knuth: So we celebrated 60 years of wedded bliss uh last month. And and we met because uh I was dating her roommate. This this was my sophomore year, her freshman year, I was dating her roommate and I wanted her advice on strategy or something like this. And anyway, I found I enjoyed her advice better than enjoyed a roommate.

Lex Fridman: You guys were made during the same thing. No, no, no, because because I read something about working on a computer in grad school on a difficult computer science topic.

Donald Knuth: So so she's an artist and I'm okay and I'm uh geek and what

Lex Fridman: was she doing with a computer science book?

Lex Fridman: Alright. I read was that the manual that she was reading, What was she

Donald Knuth: wrote? The manual that she had had, she had to take a class in computer science. Okay. And uh you're the tutor. No, no. Yeah. No we yeah, we there were terrible times. Uh you know, trying to learn certain concept, but I learned our premiere and so we worked together uh you know occasionally in design projects. But every year we we write a christmas card and and we each have to compromise our own notions of beauty. Uh

Lex Fridman: When did you fall in love with her

Donald Knuth: that day that I asked her about her roommate? I mean, no. Okay. So you I don't mind telling these things depending on how you how far you go. But let me but let me tell you this that I I never really enjoyed kissing uh until I found how she did it,

Lex Fridman: Wow! In 60 years, is there a secret you can uh you can say in terms of stable marriages of how you stayed together so long.

Donald Knuth: The topic, stable marriage, by the way is not is a technical term. Uh

Lex Fridman: It's a joke done, but uh

Donald Knuth: to different people will have to learn how to compromise and work together and and you're gonna have ups and downs and crises and so on. And so as long as you don't Set your expectation on having 24 hours of bliss uh then there's a lot of hope for stability. But if you, if you decide that it's that, that there's gonna be no frustration. Uh,

Lex Fridman: so you're gonna have to compromise on your notions of beauty when you write christmas cards.

Donald Knuth: That's it.

Lex Fridman: Uh, you, uh, you mentioned that Richard Feynman with someone you looked up to? Yeah, uh, probably you've met him in caltech.

Donald Knuth: Well, we knew each other. Yeah. At caltech for sure. Yeah.

Lex Fridman: Uh, you are one of the seminal personalities of computer science. He's one for physics. Have you, is there specific things you picked up from him by way of inspiration or?

Donald Knuth: So we used to go to each other's lectures and, but but if I saw him sitting in the front row, I would throw me for a loop. Actually, I I would would miss a few, a few sentences. What unique story do I have about? I mean, I, I often referred to his, his time in brazil, uh, where he uh, essentially said they were teaching all the physics students the wrong way. They were just, they were just learning how to pass exams and not learning any physics. And he said, you know, if you want to prove it, you know, here, I'll turn to any page of this textbook, and, and I'll tell you what's wrong with this page and he did so, and and the text book had been written by his host. And, and, and it was a big embarrassing incident, but he had previously ISIS host if if he was supposed to tell the truth. Um but but anyway, it epitomizes the way uh education goes wrong uh in all kinds of fields uh and has to periodically be brought back from from from a process of giving credentials to a process of giving knowledge.

Lex Fridman: That's probably a story that continues to this day in a bunch of places where it's too easy for ah educational institutions to fall into credential is um versus uh inspirational is um I don't know if those are words, but sort of uh understanding versus just giving a little um it's black

Donald Knuth: and you know, it's it's very much like what we're talking about, if you want the computer to If you want to be able to believe the answer. Computer is doing? One of the things Bob Floyd showed me in the 60s, there was a uh he loved this cartoon, there was there were two guys standing in front of in those days, a computer was a big thing, you know? And and the first guy says to the other guy, he said, this machine can do in one second what it would take a million people to do in 100 years? And the other guy says, oh, so how do you know, it's right,

Lex Fridman: it's a good line. Uh is there some interesting distinction between physics and math to you, have you looked at physics much to like speaking of Richard Feynman. So the difference between the physics community, the physics way of thinking, the physics intuition versus the computer science, the theoretical computer science, the mathematical sciences. Do you see that as a gap? Are they strongly overlapping?

Donald Knuth: It's quite different in my opinion. Uh I started as a physics major and I switched in the math uh and probably the reason was that I could I could get a plus on the physics exam, but I I never had any idea why I would have been able to come up with the problems that were on those exams, but but in math I knew, you know, why the teachers set those problems and I thought of other problems that I could set to and I believe it's it's quite a different mentality.

Lex Fridman: It has to do with your philosophy of geekdom

Donald Knuth: gigs. I mean, some of my computer scientists friends are really good at physics and others are not, and I'm uh you know, I'm really good at algebra, but not a geometry. Talk about different parts of mathematics, you know? So there are different kinds of physical, but physics just think of things in terms of waves and I can think of things in terms of waves, but it's like a dog walking on hind legs, if I'm thinking about.

Lex Fridman: So you basically you like to see the world in uh in discreet ways and then more continuous.

Donald Knuth: Yeah, I'm not sure if turing had been a great physicist. I think it was a pretty good chemist. I don't know. But anyway I see things I believe that computer science is largely driven by uh people who have brains, who are who are good at resonating with a certain kind of of of concepts and like quantum computers, it takes a different kind of brain. Yeah,

Lex Fridman: that's interesting. Yeah, it's well quantum computers is almost like at the intersection in terms of brain between computer science and physics because they involve both at least at this time. Uh but there is like the physicists have known they have incredibly powerful intuition

Donald Knuth: and there I mean statistical mechanics. So I studied statistical mechanics and and you know I mean random processes uh are related to algorithms and a lot of, a lot of ways, but there's lots of different flavors of flavors of physics as there are different layers of mathematics as well. Um But the thing is that I don't see well actually when they talk to physicists use a completely different language and when they're talking to, when they're writing expository papers, so I didn't understand quantum mechanics at all from reading about it in scientific american. But when I read, you know how they described it to each other, talking about Eigen Eigen values and and various mathematical terms that that made sense. Then it made sense to me. But Hawking said that every formula you put in a book you lose half of your readers. And so he didn't put any formulas in the book. So I couldn't understand his book at all, you could say you understood it, but I really I really didn't.

Lex Fridman: Uh well the fireman also spoke in this way. So Feynman, I think prided himself on a really strong intuition, but at the same time he was hiding all the really good the deep computation he was doing.

Donald Knuth: So there was one thing that that uh I was never able to uh I wish I'd had more time to work out with him, but I guess I could describe it for you.

Donald Knuth: There, There's something that got my name attached to it called arrow notation, but it's a notation for very large numbers. And so uh I find out that that somebody invented it in in 1830s, uh it's fairly easy to uh to understand anyway. So you start with X plus X plus X plus X. End times and you can call that xN so X and his multiplication, then you take X times X times X times X and end time. That gives you exponentially ation X to the nth power. So that's one arrow X. So X n with no arrows, this multiplication, X arrow and is X to the Nth power

Lex Fridman: just to clarify for the uh so X times X times X and times is obviously X and X plus

Donald Knuth: X plus X and time. Uh Oh

Lex Fridman: yeah, okay. And then uh Xn multiplication is X to the end. Uh And then and then here the arrow is when you're doing the same kind of repetitive operation for the exponential.

Donald Knuth: So I put in one arrow and I get extra manpower. Now I put in two arrows and that makes it takes X to the X to the X to the X to the X. N. Times priority. So in other words, if it's to uh double arrow three, that would be that would be two to the two to the two. So that would be two to the fourth power. That be 16. Okay, okay, so so so that's the double arrow and now you can do triple arrow. Uh of course. Uh and and so on. And and I had this this paper called uh well, essentially big numbers. Uh you know, you try to impress your friends, but by saying a number they never thought of before. And and and I gave a special name for it. Uh designed a font for it that has script K and so on. But it really is 10, I think like 10 Quadruple Arrow three or anything like that. And I claim that that number if it is. So mind boggling that you can't comprehend how large it is. But anyway, fine. I talked to feynman about this and he said, oh, let's just let's just use double arrow. But instead of taking editors, let's consider complex numbers. So, you know, you have I mean, okay, X x arrow arrow to, that means X X. Uh X. But what about x X double arrow to 2.5. Well, that's not too hard to figure out. That's interplay between the but what X double arrow, I or one plus I or some complex number. Uh And and uh so he claimed that that there was no analytic function that would that would that would do the job. But I I didn't know how he could claim that that was that wasn't true.

Donald Knuth: Absolutely. And his next question was then have a complex number of arrows. Yeah. Okay.

Lex Fridman: Okay. Okay.

Donald Knuth: So that's that's fine. And uh violence. Yeah.

Lex Fridman: Can you describe what the uh ruth Morris pratt algorithm does and how did you come to develop it? One of the many things that you're known for and has your name attached to it?

Donald Knuth: Yeah. All right. So it should be actually Morris pratt can youth, but we decided to use alphabetical order when we published the paper. The problem is uh something that everybody knows now if there if they're using a search engine, uh uh you have a a large collection of text and you want to know if if the word canoe with appears anywhere in the text to say or or some some other word that's less interesting than kind of. Okay.

Lex Fridman: But anyway, that's the most interesting or something.

Donald Knuth: Right?

Donald Knuth: We have we have a large piece of text and it's all one long one dimensional thing, you know the 1st and 2nd letter etcetera etcetera etcetera. And so uh the question you'd like to be able to do this quickly. Um And the obvious way is uh let's say we're looking for Morris with okay so we would we would go through and wait till we get to a letter M. Then we look at the next word and sure enough it's an O. And then they are but then what too bad? Um the next letter is E. So we missed we missed out on Morris. And so uh we go back and start looking for another. Okay so that's the obvious way to do it. All right. Um And jim Morris noticed there was a more clever way to do it. The obvious way would have started, let's say We found that that are are mad character position 1000. It was started next step character position 1001. But but he but he said no look we are we already read the A. And R. And we know that they aren't ems so we can we can start uh we don't have to read those over again. Uh So uh and this gets pretty tricky when when the word isn't Morris but it's more like abracadabra where you have patterns that are occurring uh

Lex Fridman: like repeating patterns in at the beginning at the middle right.

Donald Knuth: Right?

Donald Knuth: So uh he worked it out and he put it into the system software at Berkeley, I think it was where he was uh he was writing some Berkeley UNIX, I think it was like some routine, I was supposed to find occurrences of patterns in texas and yeah, and yeah, we didn't explain it. And and and so he found out that several months later, somebody had had looked at, it didn't look right, and so they ripped it out. So he had this this algorithm, but it didn't make it through. Uh because what wasn't understood, nobody knew about this, particularly Vaughan. Pratt also had independently discovered a year or two later. Uh I forget why I think Vaughn was studying some technical problem about palindromes or something like that. He wasn't really wan wasn't working on on text searching, but he was working on on an abstract problem that that was related. Well, at that time, steve Cook was a professor at Berkeley. Uh uh it was the greatest mistake that Berkeley CS department made was not to give them tenure. So steve went to went to Toronto, but uh but but I knew steve well, he was at Berkeley and he had come up with a with a very peculiar theory uh by the technical concept called a stack of tom martin and a stack of tom martin. It is a machine that can do everything. A turing machine could do, but it can only look at something at the top of the stack or it can put more things on the stack or it can take things off the stack, like it can't remember a long string of symbols, but I can remember them in reverse order. So if you tell a stack of thomas on a B C D E, it can, it can tell you afterwards. E D C B A uh you know, it doesn't have any other memory except except this one thing that it can see. And steve cook proved this amazing thing that says, if a stack of time of time can recognize a language where the strings of the language or length and in any amount of time whatsoever to the stack of Tommy time might use a zillion steps. Regular computer can recognize that same language in time and log in. So steve had a way of transforming a computation that goes on and on and on and on into using different data structures into something that you can do on a regular computer. Uh fast. The stack of Thompson goes slow, but somehow the fact that it can do it at all means that there has to be a fast way. So I thought this was a pretty you know, cool theory. Uh And so I tried it out on on the problem where I knew a stack of tom martin could do it, but I couldn't figure out a fast way to do it on a regular computer, I thought it was a pretty good programmer, but by golly, I couldn't think of any way to recognize this language uh efficiently. So I went through steve cooks construction, I filled my blackboard with all the everything that stack, thomason dot, did you know, I wrote down, and and then I tried to see patterns in that, and and how did he convert that into a computer program on a regular machine? Um and finally I psyched it out. What was what was the thing I was missing, so that I could say, oh yeah, this is what I should do in my program. Uh And now I have an official program. And and so I uh I would never have thought about that if I hadn't had his theorem, which was purely abstract thing. Well then

Lex Fridman: I used to try to intuit how to use the stack of Hamilton for the string matching problem.

Donald Knuth: Yeah. So, so the problem I had started with was not the string matching problem, but then I realized that the string matching problem was another thing, which would also be, could be done by a stack of Hamilton. And and so when when I looked at what that told me, then I had a nice algorithm for this string matching problem, uh and it told me exactly what I should remember, as as I'm going through the string and I worked it out and and I wrote this little paper called automata theory can be useful And and the reason was that it was the first, I mean I had been reading all kinds of papers about automata theory. Uh but it never taught me, it never improved my programming for everyday problems. Uh It was something that you published in journals and and you know, it was it was interesting stuff, but but here was a case where I couldn't figure out how to write the program. I had a theory from atomic theory, then I knew how to write the program. So this was uh for me uh a change in life. I started to say maybe I should learn more about thomas. And and I showed this note to Bond prayer and he said he that's similar to something I was working on. Um and then uh and Jim Morris was at Berkeley to at the time anyway, he's had an illustrious career, but I haven't kept track of Jim, but one is my colleague at stanford and and my student um later, but this was before Von one was still a graduate student and hadn't come to stanford you. So we found out that we had all been working on the same thing. So it was our algorithm we each discovered independently, but each of us had discovered a different, a different part of the elephant uh you know, different aspect of it. And so we could put our things together. It was my job to write the paper,

Lex Fridman: how did the elephants bring to life

Donald Knuth: spring to life was because I I had drafted this paper, Atomic theory can be useful, which was seen by Von and then by Jim and then then then we combined because maybe they had also I've been thinking of writing something up about it

Lex Fridman: about specific

Donald Knuth: problem in a period.

Lex Fridman: Let me ask a ridiculous question. Uh last time we talked, you told me what the most beautiful algorithm is actually. Uh for strongly connected graphs. What is the hardest problem puzzle idea in computer science for you personally that you had to work through? Just something that was just a

Donald Knuth: the hardest thing that I've ever been involved with. Okay, well yeah, that's I don't know how to answer questions like that, but in this case uh it's pretty clear because it's uh called the birth of the giant component. Okay, so now let me explain that because this actually gets gets into physics too and it gets into something called Bose Einstein statistics. But anyway, it's got some interesting stories and it connected with Berkeley again, um So start with the idea of a random graph. Now this is did here we just say we have endpoints that are totally unconnected and and there's no geometry involved, there's no saying some points are further apart than others. All points are exactly are exactly alike. And Let's say we have 100 points. And uh and we number them from 00-9 nine. All right now, let's let's take pi uh the digits of pi so two at a time. So we had 31 41 59 26. We can go through pi and so uh so we take the 1st 2 31 41 let's let's put a connection between 410.31 point 41. Uh That's an edge in the graph. So then we take 5926. Make another edge. Uh The graph gets bigger, gets more and more connected as we add these things one at a time. Okay. We started out with endpoints and we add uh m edges. Okay, each edge is completely, we forgot about it and we had before we might get edge twice, we might get edge from a point to itself. But um you know, maybe Pie is going to have a run of four digits in there. So we're gonna but anyway, we're evolving a graph at random. Um And Uh a magical thing happens when the number of edges is like .49. And uh so maybe it is a million and I have uh you know, 490,000 edges. Uh then almost all the time it consists of isolated trees, not even any loops. Uh

Lex Fridman: It's a very small number of veggies so Far,

Donald Knuth: a little less than half in. And but if I had .51 edges, so a little more than half in. So it's you know a million points. 510,000 edges. Now it probably has uh a one component that's much bigger than the others. Mhm. Um and we call that the giant component.

Lex Fridman: Can you so can you clarify? So I thought is there a name for this kind of random? Super cool pie. Random graph.

Donald Knuth: Well I call it pot pie graph. No no I want the pie graph is actually my pie graph is based on binary representation of pi. Not the decimal representation of pi but anyway let's suppose I was rolling dice instead so I

Lex Fridman: might have so it doesn't doesn't have to be part of

Donald Knuth: any source of the point. Is every step choose totally at random. One of those endpoints choose totally at random another one of the endpoints make that an edge. That's the process. Yeah,

Lex Fridman: so there's there's nothing magical about pie, they, you

Donald Knuth: know, I was using pi to sort of saying pie is sort of random that nobody knows a pattern in exactly. Uh but it's not yeah, I could have just as well drawn straws or something. Um This was a concept invented by edition rainy and they called evolution of random graphs and if you start out with with a large number and and you repeat this process all of a sudden a big bang happens at one half end, there will be two points together then maybe we'll have three. Uh you know the then they maybe branch out a little bit, but but I'll be separate until we get to one half end and we passed one half end and all of a sudden there's substance to it that there are, there's a big clump of stuff that's all joined together.

Lex Fridman: So it's almost like a phase transition of some kind. It's

Donald Knuth: exactly it it's a phase transition, but it's a double phase transition. It turns out it happens. I mean there's actually two things going on at once at this phase transition, which is uh which is very remarkable about Okay, so, so a lot of the most important algorithms are based on random processes. And so I wanted to, you know, I want to understand random processes now. So there are data structures that sort of grow this way. Okay, so so so Dick Car, one of the leading experts on random randomized algorithms. Had his students working looking at this at Berkeley and we heard a rumor that the students have found something interesting happening that the students are generating this, are simulating this random evolution of graphs and undertaking snapshots. Uh it was so often take a look at what the graph is. And the rumor was that every time they looked there was only one component that had loops in it. Almost always they do a million experiencing uh only three or four times did they ever happen to see a loop at at this point. Uh no more than one component with the loop. So they watch it till the graph gets completely full. Uh so it starts out totally empty and gets more and more more and more edges all the time. Uh And and so Ok, certainly a loop comes along once, but now all the loops stay somehow joined to that one. There never there never were two guys with loops

Lex Fridman: uh

Donald Knuth: in these experiments. Okay, So anyway, this almost always. Not always, but but with very high probability that seemed to be true. So so we heard about this rumor at stanford and we said well if that's true then must, you know, a lot more must also be true. So there's a whole bunch, there's a whole theory out there waiting to be discovered that we have ever thought about. So let's take a look at that. And so we looked closer and we found out no, actually it's not true, but but in fact it's almost true, namely there's a very short interval of time, what is true? And if you don't happen to look at during that short interval of time then you miss it. So in other words, there will be a period where there two or three components have loops but they joined together pretty soon.

Lex Fridman: So

Donald Knuth: if you don't have a real fast shutter speed, you're gonna miss, you're gonna miss that instant.

Lex Fridman: So separate loops don't exist for long,

Donald Knuth: that's it. Yeah, I started looking at this to make it quantitative. And uh the basic problem was to slow down the big banks so that I could watch it happening. I think I can explain it actually in fairly elementary terms, even without writing a formula, like talking would do uh and and so uh that's a let's watch the evolution.

Donald Knuth: And at first uh these edges are coming along and they're just making things without loops, which we call trees. Okay? So then all of a sudden the loop first appears. So at that point I have one component that has a loop. All right now. Now I say that the complexity of a component is the number of edges minus the number of vertex is so if I have a loop, I have like a loop of length. Five has five edges. And five vertex is uh um or I could put a tail on that and that would be another edge. Another Vertex

Lex Fridman: is 0, 1, 2 complexity kind of thing.

Donald Knuth: So if the if the complexity is zero, we have 11 loop. I call it a cycle. Or I call the cyclic components. So cyclic component looks like a wheel to which you attach fibers. Or trees they go branching. But there's no more loops. There's only one loop. And everything else feeds into that loop. Okay. And that has complexity zero. But the tree itself has complexity minus one because it has uh like like like it might have 10 versus season and nine edges to tie the time together. So nine minus 10 is minus one. So complexity -1 is a tree. It's got to be connected. That's what I mean by a compound. That's got to be connected. So, so if I have 10 things connected, I have to have nine edges.

Lex Fridman: Can you clarify why when complexity goes? Uh can go about zero? I'm a little

Donald Knuth: Yes. What? Right. So, the complexity plus one is the number of loops. So, if complexity is zero, I have one loop. If if complexity is one, that means I have one more edge than I have heard it. So, I might have like 11 edges and 10 vortices. So it turns we call that a bicycle because it's got two loops and it's gonna have two loops. And if well, why

Lex Fridman: can't you be trees just going out for the loop,

Donald Knuth: that I would need more edges than? All right,

Lex Fridman: okay,

Donald Knuth: so every time I get another loop I get another excessive edges over ver to see. Okay, so in other words, uh we start out and after I have one loop, I have one component to ask a cycle in it. Now, the next step, uh according to the rumor, would be at the next step, I would have a bicycle uh in the evolution of almost all graphs, it would go from cycle to bicycle, but in fact there's a certain probability it goes from cycle to to, you know, 2, 2 different cycles.

Donald Knuth: Alright. Um and I worked out the probability was something like five out of 24, there wasn't, it was substantial. Uh but still uh soon they're going to merge together almost. Okay. So but then it splits again after you have either Either two or 1 one. Uh The next step is you either have three or you have to one or you have 111. Okay. And so I worked out the probability for those transitions and I worked it out up to up to the first five transitions and I had these, I had these strange numbers 5, 24 I stayed up all night and about three a.m. I had the numbers computed and I looked at him and here we're the denominator was something like 22, 3, 0 - three. So the probability was something over two, I don't

Lex Fridman: know how you work that out, but I had

Donald Knuth: a formula that, you know, I could calculate the probability and I could find the limiting probability as n goes to infinity. And it turned out to be this number. But the denominator was too thrilled. And I looked at the denominator, I said, wait a minute. This number of factors because 1000 and one is equal to seven times 11 times 13. I had learned that my first computer program. So, so, so so 23 0 23 is seven times 11 times 13 times 23. That's not a random number. There has to be a reason why those small crimes appear in the denominator. But my thing. So all of a sudden that suggested, um, another way of looking at the problem where small prime factors would occur. So what

Lex Fridman: would that be? So

Donald Knuth: that said, oh yeah, let me take the law algorithm of this formula. And sure enough, it's going to simplify and it happened. So, and I wouldn't have noticed it except for this factory ization. Okay. So I go to bed and I said, oh, okay, this, this looks like I'm flowing down the big bang. I can figure out what's going on here. And the next day it turned out Bill Gates comes to stanford to visit. Uh, they're trying to sell him on donating money for a new computer science building. And, and, and uh, they gave me an appointment to talk to Bill and I, and I wrote down on the blackboard, this, this evolutionary diagram, you're going from 1 to 25 24th and all this business. And I wrote it down. And anyway, at the end of the day, the uh, he, he was discussing people with the development office and he said, boy, I was really impressed with what Professor, can you said about this giant component. And uh, and so, you know, I, I love this story because it shows that theoretic computer science is really worthwhile. You know,

Lex Fridman: does Bill, have you ever talked to Bill Gates about it? Uh Since then Yeah, that's a cool, that's a cool in a moment in

Donald Knuth: history. But anyway he happened to visit, I'm exactly the day after I had I found this pattern and and that allowed me to crack the problem so that I could develop the uh theories are more and understand what's happening in the big but uh because I could I could now write down explicit formulas for stuff. So it would you work not only the first few steps but also though study the whole process and and I worked further and further and I with two authors co authors and we finally figured out That the probability that the rumor is true in other words look at the evolution of uh of a random graph going from 00 to to complete and say what's the probability that at every point in time there was only one component with the cycle. Mhm. We started with this rumor is saying there's only ones like there's only one component with the cycle and

Lex Fridman: uh 100 Percent

Donald Knuth: Rumor was that 100%. And it turned out the actual numbers like 87%. I should remember the number but I don't but I don't have a with me but anyway but but the number, it turned out to be like 12 over pi squared or anyway, so eight over anyway. It it was a nice, it related to pi um and we could never have done that with. So that's the hardest problem I ever saw in my life was to prove that this probability is

Lex Fridman: it was proven, the probability was proven.

Donald Knuth: Yeah, I was able to prove this, that this and this should shed light on a whole bunch of other things about random graphs. That was sort of the the major thing we were after after.

Lex Fridman: That's super cool. I what was the connection to physics that you mentioned? Well

Donald Knuth: Bose Einstein statistics is the study of how molecules uh bond together uh without geometry.

Donald Knuth: Without this x.

Lex Fridman: You created the tech typesetting system and released it as open source. Just on that little aspect. Why did you release it as open source? What is your vision for? Open source?

Donald Knuth: Okay, well that the word open source didn't exist at that time, but but I didn't want proprietary rights over Because I saw how proprietary rights for holding things back in the late 50s, people at IBM developed the language called FORTRAN, they could have kept it proprietary, they could have said on the IBM can use this language. Everybody else has to but they didn't, they said anybody who can write, who can translate for training into the, into the language of their machines is allowed to make FORTRAN compilers to um on the other hand, in the topography industry I had seen a lot of languages that were developed for composing pages. And each manufacturer had his own language for composing pages and that was holding everything back because people were tied to a particular manufacturer and then a new equipment has invented a year later. But printing printing machines, they have to Expect to advertise the cost over 2030 years.

Lex Fridman: So you didn't want that for tech?

Donald Knuth: I didn't need the income. I already I already had a good job. And you know, uh my books were uh people were buying enough books that I that that it would bring me plenty of supplemental income for everything my kids needed for education or whatever. So there was no reason for me to try to maximize income. Any further income is sort of a threshold function. If you don't have, if you don't have enough, you're starving. But if if you get over the threshold, then you start thinking about philanthropy or else you're trying to take it with you. But uh but anyway, there's a I my income was over the threshold, so I didn't need to keep it. And so I specifically could see the advantage of uh making it open for everybody.

Lex Fridman: Do you think most software should be open?

Donald Knuth: So I think that uh people should charge for nontrivial software, but not for trivial software.

Lex Fridman: You give an example of, I think adobe Photoshop versus gimp on Lenox as Photoshop has value,

Donald Knuth: which so it's definitely worth paying paying for all this stuff. I mean, I mean, well they keep adding adding stuff. That's that my wife and I don't care about but somebody, but I mean, but they have built in a fantastic uh a new feature, for example, in Photoshop where where you you can go through a sequence of 1000 complicated steps on graphics and it can take you back anywhere in that sequence uh with really beautiful algorithm. I mean, yeah, it's

Lex Fridman: Oh, that's interesting. I didn't think about what algorithm it must be some kind of efficient representation really.

Donald Knuth: Yeah, no, I mean there's a lot of really subtle Nobel prize class creation of intellectual property in in there. Um and uh and with patents you've got a limited time to uh I mean, eventually the idea of patent is that you publish so that it's not secret, is not a trade secret

Lex Fridman: that said you you said that I currently use a bond to Lenox on a standalone laptop. It has no internet connection. I occasionally carry flash memory drives between the machine and the max that I use for network surfing and graphics. But I trust my family jewels only to Lennox. Why do you love Lennox?

Donald Knuth: The version of lyrics that I use is stable. I actually, I'm gonna have to upgrade one of these days, but

Lex Fridman: to a newer version of a bond to

Donald Knuth: Yeah, I'll stick with you want to, but right now I'm running something that doesn't support a lot of the new Software. It's the last stable re I don't remember the number, we're like 14 anyway. It's quite and I'm going to get a new computer. I'm getting new solid state memory instead of instead of a hard disk.

Lex Fridman: Well let me ask you uh sticking on the topic of tech um when thinking about beautiful typography, What is your favorite letter number or symbol?

Lex Fridman: Mhm. I know, I know, ridiculous question. But is there some

Donald Knuth: or? Uh huh. Look at the last page. Mhm. At the very end of the index. Mhm. Uh huh. What is that? There's a book by dr Seuss called on Beyond zebra and he gave a name to that.

Lex Fridman: Did you see Dr Seuss give a name to that.

Donald Knuth: Dr Seuss, this is S. E. U. S. S. He he wrote Children's books In the 50s, 40s and 50s.

Lex Fridman: You're talking about cat in the hat

Donald Knuth: and the hat. Yeah that's it. Yeah. I like how you have on on beyond zebra. Did you get to the soviet union?

Lex Fridman: Yeah. I know.

Lex Fridman: Dr Seuss did not come to the soviet union but since you oh actually I think it did actually a little bit when we're um that that was a book his maybe cat in the hat or or green eggs and ham I think was used to learn english. So I think it made it in that

Donald Knuth: way my okay I didn't like those as much as Bartholomew cabins. But I used to know Bartholomew covers my heart when I was young.

Lex Fridman: So what the heck is this symbol we're looking at? There's so much going on.

Donald Knuth: He has a name for it at the end of his book on Beyond Zebra

Lex Fridman: who made it.

Donald Knuth: He did, he did.

Lex Fridman: So there's it looks like a bunch of vines. Well, is that simple existence,

Donald Knuth: By the way, he made a movie in the early 50s. I don't remember the name of the movie now, you can probably find it easily enough. It features uh dozens and dozens of pianos all playing together at the same time. And but but all the scenery is sort of based on the kind of artwork that was in his books and uh the fantasy, you know, based of Seuss Land or uh and I saw the movie only once or twice, but it's but it's quite, I'd like to see it again. That's that's

Lex Fridman: really fascinating that you gave them. They gave him a shout out here. Okay, is there some elegant basic symbol that you're attracted to? Some uh give something that gives you pleasure. Something used a lot pi

Donald Knuth: pi of course. Uh try to use pi as often as I can when I need a random example because it doesn't have any uh known characters. So for for instance, I don't have a care to show you, but uh do you know the uh the game called Mass? Um a s y You it's it's a great recreation. I mean Sudoku is easier to understand what Matthew is. It is more addictive. Uh You have black and white stones like a like on a go board. Uh and you have to draw a path that goes straight through a white stone and makes a right angle turn out to Blackstone. Um And it turns out to be really really nice puzzle because It doesn't involve numbers, what visual, but it's three D. Pleasant to play with. So I wanted to use it as example in art of computer programming and I have um I have exercise on how to design cool Masu puzzles. You can find out on Wikipedia certainly uh as an example M.

Donald Knuth: A. S. Y. U.

Donald Knuth: Um And and so I and so I decided I would take pi the actual image of it and you had pixels and I would put a stone wherever it belongs in the letter pie in the greek letter pi. And but the problem was find a way to make some of the stones white some of the stones black. So that there's a unique solution to the Matsu puzzle. That was a good test case for my algorithm on how to design a mosque you puzzles because I insisted in advance that the stones had to be placed in exactly the positions that make a letter pi make a letter. All right. And and I saw, you know, and it turned out there was a unique way to do that. Um And so so pie is a source of of examples where I can, where I can prove that I'm starting with something that isn't can uh And and most most recently I was writing about something called graceful graphs. Yeah, uh graceful grass is the following. You have a graph that has uh m edges to it. And you attach numbers to every vertex in the following way. So every time you have an edge between vertex is you take the difference between those numbers. And and that difference is he's got to be tell you what edge it is. So that one edge, two numbers will be one apart. There'll be another edge where the numbers are two apart. And so uh great computer problem. Can you find a graceful way to label a graph? Uh So I started with it. So I started with a graph that I use for organic graph. Not not a Mathematically symmetric graph or anything. And I take this take a 49 states of the United States. Uh The edges that go from one state to the next state. So for example, California be next to Oregon, Nevada Arizona. Okay. And and and I include district, District of Columbia. Uh so I have 49, I can't get Alaska and Hawaii in there because they don't touch. You have to be able to drive from one to the other. So is there a graceful labeling of of the United States? Each state gets a number and then if California is number 30 and Oregon is number 11, that edge is going to be number 19. The difference between those. Okay, so is there a way to do this for other states? And uh and so I was I was thinking of having a contest uh for people to get it as graceful as they could. Uh But my friend tom rookie actually solve the problem by proving that, I mean, I was able I was able to get it down Within seven or something like that. He was able to get a perfect solution,

Lex Fridman: the actual solution or to prove that a solution exists

Donald Knuth: more precisely. I had figured out a way to put labels on so that All the all the all the edges were labeled somewhere between one and 217. But but there were some some some gaps in there because I should really have gone from 1 to 105 or what whatever the number is. So I gave myself too much, you know, a lot of slack. He did it without any slack whatsoever. Perfect, graceful labeling. And and so I call out the contest because the problem is already solved and too easy in a sense because tom was able to do it in the afternoon. Um

Lex Fridman: he's sorry, he gave the algorithm or for this particular uh

Donald Knuth: for the United States, the United States. This problem is this problem is incredibly hard. I mean for the general general is

Lex Fridman: uh but

Donald Knuth: It was very lucky that we worked for the United States I think. But the theory is still very incomplete. But anyway, then tom came back a couple days later and he had been able to not only find a graceful labeling, but but the label of Washington was 31. The label of Of Idaho was 41. Following the digits of pi going across the topic of the United States. He has the digits of pi perfectly

Lex Fridman: on purpose. He

Donald Knuth: was able to still get a graceful labeling with that with that extra thing. Uh wow, it's a miracle. Okay. But I like to use pie in my book, you see. And this is the uh

Lex Fridman: all roads lead to pi somehow, somehow often hidden in the middle of like the most difficult problems. Can I ask you about productivity? Productivity? Yeah. You said that quote my scheduling principle is to do the thing I hate most uh on my to do list by weeks and I'm very happy. Can you explain this process to a productive life?

Donald Knuth: Oh, I see. Well, but all the time I'm working out on what I want, what I don't want to do, but still I'm glad to have all those unpleasant task finished.

Lex Fridman: Yes. Is that something you would advise to others.

Donald Knuth: Well, I yeah, I don't know how to sit well during the pandemic. I feel my productivity actually went down by half because I have to um I have to communicate by writing which is slow. I have to I mean I don't like to send out a bad sentence so I, you know, I go through and re read what I've written and read it and fix it. So everything takes a long longer when I'm when I'm communicating by my text messages uh instead of just, you know, together with somebody in the room. And it's also slower because the libraries are closed and stuff. But there's another thing about scheduling that I learned from my mother that I should probably tell you and that is um it's different from what people in robotics field do, which is called planning. So she had this principle that was see something that needs to be done and do it. I would just instead of saying I'm gonna do this person do this first, just you know, uh just do it, pick this up, but you're

Lex Fridman: at any one moment there's a set of tasks that you can do. And you're saying a good heuristic is to do the one you want to do least.

Donald Knuth: Right. The one I haven't got any good reasons. I will never be able to do it any better than I am now. Uh I mean there are some things that I know if I do something else first I'll be able to do that one better. But there's some that are going to be harder because, you know, uh I've forgotten some of the ground work that went into it or something like that. So I just finished a pretty tough part of the book, and uh and so now I'm, you know, doing the parts that are more fun, but but but the other thing is, as I'm writing the book, of course, I went the reader to think that I'm happy all the time. I'm writing the book. I'm, you know, that it's upbeat. I I can have humor. I can, you know, I can I can say this is cool, you know? Well, this uh I have to I have to disguise the fact that it was painful in any way. The road to

Lex Fridman: that excitement is painful. Yeah, it's laden with pain. Okay, is there? You've given some advice to people before, but can you, uh

Donald Knuth: can you give me too much credit? But anyway, this is my this is my turn to just uh to say things that that I believe. But but I want to preface it by saying, I also believe that other people do. How did these things much better than I do? So I can only tell you my side of it.

Lex Fridman: So, can I ask you to give advice to young people today to high school students, to college students, whether they're geeks or the other kind about how to live a life there, it can be proud of how to have a successful career, how to have a successful life.

Donald Knuth: That's it's always the same as I've said before. I guess that not too do something because because it's trendy, but it's something that you personally feel that you were called to do rather than somebody else expects you to do.

Lex Fridman: How do you know, you're called to do something

Donald Knuth: you tried and it works, or or or it doesn't work. I mean, you learn about yourself, life is a binary search. You try something and you find out, oh yeah, I have a background that helped me with this, or maybe I'm maybe I could do this if I worked a little bit harder, but you try something else and you say I have really no intuition for this, and it looks like uh, you know, it looks like it doesn't have my name on it.

Lex Fridman: Was there advice along the way that you got about what you should and shouldn't work on or do you just try to listen to yourself?

Donald Knuth: Yeah, I probably overreact another way when, when something, when I see everybody else going some way, I probably, I probably say that too much competition. Uh, but but but uh but mostly I I played with things that were interesting to me and then later on I found, oh, actually the most important thing I learned was how to be interested in almost anything. I mean, not to be born her. It makes me very sad when I, when I see kids talking to each other and they say that was boring. And to me, a person should feel upset if he would help if he had to admit that he wasn't able to find something interesting.

Lex Fridman: Uh,

Donald Knuth: you know, the skill they saying I haven't learned how to uh, how to enjoy life. I have to have somebody entertain me instead of.

Lex Fridman: That's really interesting. It is a skill. Uh, David Foster Wallace. I really like the thing he says about this, which is the key to life is to be unbearable. And I do really like you saying that it's a skill because I think that's a really good, that's really good advice, which is, if you find something boring, that's not, I don't believe it's because it's boring. It's because you haven't developed how to find the beauty and how to find the fun in it. That's a that's a really good point.

Donald Knuth: Sometimes it's more difficult than others. I have to do this. But I mean, during the covid lots of days when I never saw another human being, uh, but I still find other ways to,

Lex Fridman: it still was a pretty fun time.

Donald Knuth: Yeah, I came earlier. I came a few minutes early today and I walked around. Foster said I didn't want, you know, I didn't know what's going on in foster city. I saw a beautiful, some beautiful flowers at the nursery at home depot for a few blocks away.

Lex Fridman: Life is amazing. It's full of amazing things like this. Yeah. I just, sometimes I'll sit there and just stare at a tree. Nature is

Donald Knuth: beautiful.

Lex Fridman: Uh, let me ask you the big, ridiculous question. I don't think I asked you last time I have to ask this time in case you have a good answer. What is the meaning of life? Our existence here on earth? The whole thing. Yeah. Uh, no, no, you can't. You can't, I will not allow you to, uh, to try to escape answering this question. You have to answer definitively because there surely surely don canoe. There must be an answer.

Donald Knuth: What is the answer? Is it 42 or I

Lex Fridman: don't think it's a numerical. That's, that was

Donald Knuth: that was in Shannon. Okay. But all right. So talk to anyway. It's only for me. And, but I, but I personally think of my belief that that God exists, although I have no idea what that means. But I believe that there is, uh, some something beyond human uh, capabilities. Um, it might be, uh, might be some ai uh, but, but, but whatever it is, but what, whatever I, but I do believe that that there is, uh, something that goes beyond the realm of human understanding. But, but that, that I can try to learn more about how to resonate with whatever that being would like me to do.

Lex Fridman: So you think you can have occasional glimpses of that being.

Donald Knuth: I strive for that. Not that I ever think I'm going to get close to it, but it's not, it's not for me, it's saying what should I do that that being wants me to do. That's that's you know, I'm trying to ask what that mean. Does that being want me to to be talking to lex Friedman right now? You know? And I said yes, okay, but thank you. Well, thank you. But what I'm trying to say is I'm not trying to say what of all this Strategies I could choose or something. Which one I try to do it. Not, not strategically, but I try to to imagine that I'm following somebody's wishes

Lex Fridman: even though you're not smart enough to know what they are.

Donald Knuth: Yeah, but

Lex Fridman: that funny little dance.

Donald Knuth: Well, I mean, there's A I or whatever is probably is smart enough to help to give me clues. Uh,

Lex Fridman: And uh, you make the whole journey from clue to clue a fun one.

Donald Knuth: Yeah. I mean, it's as so many people have said, it's the journey, not the destination. And people live live through crises. Help each other. I think things come up. Uh, history repeats itself. Uh, you try to say in the world today, Is there any government that's working? I read history. I know that things were, oh,

Lex Fridman: they were, there were there were a lot worse in many ways.

Donald Knuth: There's a lot of bad things all the time? And I read about, uh, you know, I look at things that people have good ideas and they were working on great projects. And then I know that it didn't succeed though in the end. But the new inside have gotten him actually in that way. Was I was reading, what book was I reading recently? It was it was by ken Follett and it was called The Man from ST Petersburg. But but it was talking about the prequel to World War and Winston Churchill according to this book, uh, seems that that Germany has been spending all its gold reserves, building up a huge military. And there's no question that if Germany would attack England, that England would be wiped out. Um, so, he wants Russia to help, uh, to attack Germany from the other side because Germany doesn't have enough of an army to be fighting two wars at one. Okay, now, then there's an anarchist in Russia who sees that wars are uh, something that leaders start, but actually people get killed. And so he wants to stop any alliance between England and Russia because that would mean that thousands and thousands of people of Russia would would, would be killed. That wouldn't be otherwise killed. All right. And so his life's goal is to assassinate a Russian prince who is visiting England because that will make you mean the zero will not form the alliance? All right. So, we have this year question about what should the government do? Should it actually do something that will lead to, you know, is the war inevitable or is there a way to have people? And it struck me that if I were in a position of responsibility for people's lives in most cases I wouldn't have I wouldn't have any confidence that any of my decisions were good. That that that that these these questions are too hard probably for any human being, but certainly for me.

Lex Fridman: Well, I think I think coupling the not being sure that the decisions are right. So that that's actually a really good thing coupled with the fact that you do have to make a decision and carry the burden of that. And ultimately I have faith in human beings and the great leaders to arise uh and help build a better world. I mean that's the hope of democracy. That's the

Donald Knuth: Ben. Let's hope that we can enhance their abilities with uh with algorithms

Lex Fridman: uh we'll put done it's such a huge honor. You've been an inspiration to me and to millions for such a long time. Um thank you for spending your really valuable time with me once again, it's a huge honor. I really enjoyed this conversation. Thanks for listening to this conversation with Donald Knuth to support this podcast. Please check out our sponsors in the description and now let me leave you with some words from Don Canute himself. Science is what we understand well enough to explain to a computer art. Is everything else we do. Thank you for listening. I hope to see you next time.