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

Donald Knuth is a computer scientist, Turing Award winner, father of algorithm analysis, author of The Art of Computer Programming, and creator of TeX. Please support this podcast by checking out our sponsors: – Coinbase: https://coinbase.com/lex to get $5 in free Bitcoin – InsideTracker: https://insidetracker.com/lex and use code Lex25 to get 25% off – NetSuite: http://netsuite.com/lex to get free product tour – ExpressVPN: https://expressvpn.com/lexpod and use code LexPod to get 3 months free – BetterHelp: https://betterhelp.com/lex to get 10% off EPISODE LINKS: Donald’s Stanford Page: https://profiles.stanford.edu/donald-knuth Donald’s Books: https://amzn.to/3heyBsC PODCAST INFO: Podcast website: https://lexfridman.com/podcast Apple Podcasts: https://apple.co/2lwqZIr Spotify: https://spoti.fi/2nEwCF8 RSS: https://lexfridman.com/feed/podcast/ YouTube Full Episodes: https://youtube.com/lexfridman YouTube Clips: https://youtube.com/lexclips SUPPORT & CONNECT: – Check out the sponsors above, it’s the best way to support this podcast – Support on Patreon: https://www.patreon.com/lexfridman – Twitter: https://twitter.com/lexfridman – Instagram: https://www.instagram.com/lexfridman – LinkedIn: https://www.linkedin.com/in/lexfridman – Facebook: https://www.facebook.com/lexfridman – Medium: https://medium.com/@lexfridman OUTLINE: Here’s the timestamps for the episode. On some podcast players you should be able to click the timestamp to jump to that time. (00:00) – Introduction (07:02) – First programs (30:26) – Literate programming (33:35) – Beauty in programming (39:30) – OpenAI (48:41) – Optimization (54:46) – Consciousness (1:03:29) – Conway’s game of life (1:16:16) – Stable marriage (1:19:35) – Richard Feynman (1:30:29) – Knuth-Morris-Pratt Algorithm (1:40:02) – Hardest problem (1:57:41) – Open source (2:02:54) – Favorite symbols (2:12:27) – Productivity (2:20:08) – Meaning of life

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

• 0:00Lex Fridman?

  The following is a conversation with Donald Knuth, his second time on this podcast. Don is a legendary computer scientist, Turing Award winner, father of algorithm analysis, author of The Art of Computer Programming, creator of tech that led to late 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.

• 0:42Lex Fridman?

  As usual, I'll do a few minutes of as now, no ads in the middle. I try to make this interesting, so hopefully you don't 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 Coinbase, which is a trusted and easy-to-use platform to buy, sell, and spend cryptocurrency. I use it. I love it. You can buy Bitcoin, Ethereum, Cardano, Dogecoin, and all the most popular digital currencies. Ever since I did a bunch of podcasts on cryptocurrency, there will be people that come up to me kind of curious about cryptocurrency and ask for advice of how they can get started

• 1:28Lex Fridman?

  with it. And I always recommend Coinbase. I think it's the easiest way to 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 Coinbase CEO Brian Armstrong on this podcast. He's a fascinating guy. That's unrelated to the sponsorship, but I very much look forward to that because I like the way he looks at the digital currency, but even just the technology world. Anyway, go to Coinbase.com/lex. For a limited time, new users can get $5 and free Bitcoin when you sign up today at Coinbase.com/lex. That's Coinbase.com/lex.

• 2:15Lex Fridman?

  This show is also brought to you by InsideTracker, a service I use 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.

• 2:46Lex Fridman?

  The great, the powerful Andrew Huberman talks a lot about InsideTracker. David Sinclair also talks a lot about InsideTracker, 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 InsideTracker store if you go to insidetracker.com/lex. That's insidetracker.com/lex.

• 3:20Lex Fridman?

  This show is also brought to you by NetSuite. NetSuite 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-grade 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.

• 4:03Lex Fridman?

  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 NetSuite. Head to netsuite.com/lex to get their one-of-a-kind financing program. That's netsuite.com/lex. netsuite.com/lex.

• 4:30Lex Fridman?

  This show is also brought to you by ExpressVPN. I use them to protect my privacy on the internet. ISPs are able to collect your data if you don't use a 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 ISPs and use a great tool for the job of preserving your privacy, you should definitely use a VPN. And ExpressVPN is my favorite VPN. Another useful reason to use ExpressVPN is 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.

• 5:15Lex Fridman?

  It does one job and it does it really well. It works on basically any operating system, including Linux, my favorite operating system. But anyway, if you go to expressvpn.com/lexpod, you'll get extra three months free. That's expressvpn.com/lexpod. This episode is also brought to you by BetterHelp, 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

• 5:56Lex Fridman?

  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 Jeff Hinton, from which emerged the BRAG propagation paper. Anyway, I mention all that because I had a conversation with him about psychiatry. He also wanted to be a psychiatrist, he's 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 BetterHelp is worth trying. It's easy, private, affordable, available worldwide. Check them out at betterhelp.com/lex. That's betterhelp.com/lex.

• 6:37Lex Fridman?

  This is the Lex Fridman Podcast, and here is my conversation with Donald Knuth.

• 7:03Lex Fridman?

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

• 7:09Speaker 01

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

• 7:14Lex Fridman?

  But the year 1957?

• 7:17Speaker 01

  The year.

• 7:17Lex Fridman?

  And the program is tic-tac-toe?

• 7:19Speaker 01

  Yeah, I might have learned about assembler later that summary. I probably did. In 1957, hardly anybody had heard of Assemblers. You looked at the user manuals. How did you write a program for this machine? It 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. Yesterday, my friend Doug Spicer at the Computer History Museum sent me a link to something that just went on YouTube. It was IBM's progress report from 1956, which is very contemporary with 1957.

• 7:59Speaker 01

  And in 1956, IBM had donated to Stanford University an IBM 650, one of the first ones. When they showed a picture of the assembly line for IBM 650s and they said, you know, this is number 500 or something coming off the assembly line. And I had never seen so many IBM 650s. I did in this movie that was on YouTube now. And it showed the picture from Stanford. They said, look, you know, we donated one of these to Stanford, one to MIT, and they mentioned one other college. And in December of 56, they donated to my university, Case Tech.

• 8:44Speaker 01

  But anyway, they showed a picture then of a class session.

• 8:50Speaker 01

  Where a guy was teaching programming and on the blackboard it said sixty nine, eight thousand, I mean, he, it, it was, he was teaching them how to write code for this IBM six fifty, which was in decimal numbers. So, so the instructions were ten, ten decimal digits. You had, you had two digits that said what, what to do, four digits to say what to do it to, and four more digits to say where to get your next instruction.

• 9:22Lex Fridman?

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

• 9:26Speaker 01

  And the manual was actually one, 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. And

• 9:42Lex Fridman?

  That's what he did.

• 9:43Speaker 01

  And so I, I, I started working at the computer center. Um, uh, and, and wrote some manuals then, but, but, yeah, but, but this was, uh, but this is the way we did it. And, and my first program then was June of nineteen fifty-seven.

• 10:01Lex Fridman?

  The tic-tac-toe.

• 10:03Speaker 01

  No, that was the second program. The first, that's the third program. The, the first program was factoring a, a number.

• 10:10Lex Fridman?

  Okay.

• 10:10Speaker 01

  So you dial a number on the, on the, um, uh, there's switches, I mean, you, you sat at this big main, mainframe. And, and, and you turn the dials, set, set a number, and, and then it would punch out the factors of that number on, on cards.

• 10:28Lex Fridman?

  So that's the input is the number?

• 10:30Speaker 01

  The input was, yeah, the input was, what was a number.

• 10:34Lex Fridman?

  Yeah.

• 10:34Speaker 01

  Attended a number. And, and, uh, and the output was, uh, its factors. And, and, and I wrote that program. Uh, it's, I still have a copy of it somewhere. And, um,

• 10:49Lex Fridman?

  How many lines of code do you remember?

• 10:50Speaker 01

  Well, yeah, it started out as about Twenty, but then I kept having me debug it and I I I discovered debugging, of course, when I wrote my first program and.

• 11:00Lex Fridman?

  What does a debugging look like on a program with just all numbers?

• 11:05Speaker 01

  Well, you sit there and you uh I don't remember how I got it into the machine, but I but I think there was a way to punch punch it on card. So each each instruction would would be one one one card.

• 11:15Lex Fridman?

  Yeah.

• 11:16Speaker 01

  Maybe I could get seven instructions on a card, eight instructions. I don't know. But anyway, so I'm sitting there at the at console of the machine. I mean, I'm doing this at night when nobody else is around.

• 11:25Lex Fridman?

  Of course.

• 11:25Speaker 01

  Um, and and so you have one set of switches where you dial the number I'm inputting, but there's another switch that's that, you know, that says, okay, now execute one instruction and show me what you did, what you did. Or or you or you you there was another four switches. I'd say, stop if you get to those if if you get to that instruction.

• 11:45Lex Fridman?

  Mm hmm.

• 11:46Speaker 01

  So so I I could say, now go until you get there again, and watch. Okay, so I could watch, you know, it it would take that number and it would divide it by two. And if it's, you know, there's no remainder, then, okay, two is a factor. So so so then I work on it. But if if if not divisible by two, divide by three. Okay, keep trying and, you know,

• 12:08Speaker 01

  until you know you're you're at the end.

• 12:10Lex Fridman?

  And you would find a bug if if you were just surprised that something weird happened?

• 12:17Speaker 01

  Well, certainly. I mean, first of all, I might have, you you know, tried to divide by one instead of two. You off by one errors that people people make all the time.

• 12:26Lex Fridman?

  Yeah.

• 12:27Speaker 01

  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 have done. But the first bugs were pretty, you know, I I probably I on on the first night I was able to I was able to get the factors of thirty, you know, as equal to two, three and five. Okay.

• 12:46Lex Fridman?

  So you're sorry to interrupt. You were so you're sitting there late at night.

• 12:50Speaker 01

  Yeah.

• 12:51Lex Fridman?

  So all. It feels like you spent many years late at night working on a computer.

• 12:57Speaker 01

  Oh, yeah.

• 12:58Lex Fridman?

  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.

• 13:06Speaker 01

  Between my freshman sophomore year, I didn't need sleep. I used to do all nighters. When I was in high school, I used to. I used to do the. The whole student newspaper every Monday night. You know, I would just stay up all night and it would be done on Tuesday morning.

• 13:25Speaker 01

  That was because I didn't get ulcers and stuff like that until later, you know, but. But.

• 13:31Lex Fridman?

  Well, the, I don't know if you know Rodney Brooks.

• 13:34Speaker 01

  Rod Brooks, of course.

• 13:35Lex Fridman?

  Yeah, he told, he told me a story that. He really, you're, you know, he really looked up to you. He was actually afraid of you.

• 13:44Speaker 01

  Well, vice versa, I must say.

• 13:47Lex Fridman?

  But he tells a story when you were working on tech. That they screwed up something with a machine. I think this might have been MIT. I don't know. And you were waiting for them to fix the machine so you can get back to work late at night.

• 14:00Speaker 01

  Oh, that happened all the time.

• 14:03Lex Fridman?

  He was really intimidated. He's like, Dr. Knuth is not happy with us.

• 14:07Speaker 01

  Oh, that's interesting. But no, no, the, the, the machine at Stanford AI Lab was.

• 14:16Speaker 01

  Was down an awful lot because we, they had. They had many talented programmers changing the operating system every day. And so the operating system was getting better every day, but. It was also crashing. So, so, so I, I wrote. Almost the entire manual for tech during downtime. Of that machine, but that's another story.

• 14:39Lex Fridman?

  Well, he was saying they, it's a hardware problem. They. They tried to fix it and they reinserted something and smoke was everywhere. He was.

• 14:48Speaker 01

  Well, that didn't happen as often as the operating system. But yeah, there were.

• 14:52Lex Fridman?

  Anyway, it's a funny story because he was saying there's this tall. Don Knuth that I look up to and. There was pressure to fix the computer.

• 15:03Speaker 01

  Well.

• 15:04Lex Fridman?

  It's funny.

• 15:06Speaker 01

  Okay.

• 15:06Lex Fridman?

  The kind of things we remember that stick in our memory.

• 15:08Speaker 01

  Well, okay, yeah, well, I could tell you a bunch of Rod Brooks stories too, but let's, let's go back to the 650. So, um, uh, so I'm debugging this, my first program and, and I, I, I had more bugs in it than number of lines of code. I, I mean, the number of lines of code kept growing and let me explain. So, so I had to punch the answers on cards. All right. So, so suppose that I'm, suppose I'm factoring the number 30, then I got, then it, I gotta, I gotta put two somewhere on the card. I gotta put a three somewhere on the card. I gotta put a five somewhere on the card. Right. And, and you know what, my, it was my first program.

• 15:50Speaker 01

  I, I, I probably screwed up and you know, it, it, it fell off the edge of the card or something like that. But, but I didn't realize that there are some tentative numbers that have, that have more than eight factors.

• 16:06Speaker 01

  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 lined the stuff up in memory and then punched the card. But, but after, you know, so by the time I finished, I had to, I had to deal with lots of, lots of things. Also, I, uh, if, if you, if you put a large prime number in there, my program might have sat there for 10 minutes. The 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.

• 16:40Lex Fridman?

  You said 10 digit?

• 16:42Speaker 01

  10 digits, yeah. So I think largest is sort of 9999999997 or something like that. And that would, you know, that, that would take me a while for that first. Anyway, that was my first program.

• 16:55Lex Fridman?

  Well, what, what was your goal with that program? Was there something you were hoping to, to find a large prime maybe?

• 17:02Speaker 01

  No.

• 17:03Lex Fridman?

  The opposite?

• 17:04Speaker 01

  No, my goal was to see the lights flashing and, and understand how, how this magical machine would be able to do something that took so long by hand.

• 17:13Lex Fridman?

  So what was your second program?

• 17:14Speaker 01

  My second program was, uh, was, uh, A converted number from from binary to decimal or something like that. It was much, much simpler. It didn't have that many bugs in it. My third program was tic tac toe.

• 17:29Lex Fridman?

  Yeah. And it had some, so the tic tac toe program is interesting on many levels. But one of them is that it had some, you can call machine learning in it.

• 17:40Speaker 01

  That's, yeah, that's right.

• 17:44Speaker 01

  I don't know how long it's going to be before the name of our field is changed from computer science to machine learning. But, but anyway, it was my first experience with machine learning. Okay, so here we had.

• 17:59Lex Fridman?

  Yeah, how does the program? Well, first of all, what is the problem you are solving? What is tic tac toe? What are we talking about? And then what, how was it designed?

• 18:11Speaker 01

  Right, so you've got a three by three grid and each, each, each can be in three states. It can be empty or it can have an X or an O. All right. So three to the ninth is a, well, what is, how big is it? I should know. But it's eighty, eighty one times eighty one times three. So, um, anyway, eight, eight is like two to the third. And so that would be, that would be like two to the sixth.

• 18:48Speaker 01

  And then, but that'd be sixty four, then you have, anyway.

• 18:51Lex Fridman?

  I love how you're doing the calculation.

• 18:53Speaker 01

  It's a lot of, anyway.

• 18:56Lex Fridman?

  The three comes from the fact that it's either empty, an X or an O.

• 19:00Speaker 01

  Right. And the six fifty, what was it? Was a machine that had only two thousand.

• 19:11Speaker 01

  Ten digit words. You go from zero, zero, zero, zero to one, nine, nine, nine, and that's it. And, and, and each word, you have a ten digit number. So that's not many bits. I mean, I, I gotta have, in order to have a memory of every position I've seen, I need three to the ninth bits. Uh, okay, but it was a decimal machine too. It didn't have bits, but, but, but it did have, it, it, it did have strange instruction. Where if, if you had a ten digit number that, but all the digits were either eight or nine. Uh, you, you'd be eight, nine, nine, eight, eight, eight, or something like that would, uh, you, you, you could make a test whether it was eight or nine.

• 19:54Speaker 01

  That was one of the strange things IBM engineers put into, to, to the machine. I have no idea why. Well, um, hardly ever used, but anyway, I, I, I needed one digit for every, every position I'd seen. Uh, zero meant, it was a bad position. Nine meant it was good position. I, 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, for, for your opponent. Uh, uh, so, but, but I, I, I could, I had that much total memory for every, every possible position was one digit.

• 20:36Speaker 01

  And I had a total of 20,000 digits, uh, which had to, 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. You get, get every, every position in tic-tac-toe. It is equivalent to, to roughly eight others because you, you, you, you can rotate the board, um, which gives you a factor four, and you can also flip it over. And that's another factor two. So, so I might, you know, so I might've needed only three to the ninth over eight positions of, you know, plus, plus a little bit.

• 21:15Speaker 01

  Uh, so I had, but anyway, that was, that was a, a, a part of the program to, to squeeze it into this tiny.

• 21:22Lex Fridman?

  So you tried to find an efficient representation that took account for that kind of rotation?

• 21:27Speaker 01

  I had to, otherwise I couldn't do the learning.

• 21:30Lex Fridman?

  Wow.

• 21:31Speaker 01

  So, so, but, but I had three parts to my tic-tac-toe program. And I called it Brain One, Brain Two, and Brain Three. So, Brain One just played a, um, um, let's see, at random.

• 21:51Lex Fridman?

  Okay.

• 21:52Speaker 01

  It's your turn. Okay, you gotta put an X somewhere. It has to go in an empty space, but that's, that's it. Okay, choose, choose one and, and play it. Brain Two, uh, had a canned routine, and I think it was, it also, maybe it had, maybe it assumed you were the first player, or maybe it allowed you to be first. I think you were allowed to be either first or second, but had a canned, built-in strategy known to be optimum for tic-tac-toe.

• 22:24Speaker 01

  Before I forget, by the way, I, I learned many years later that Charles Babbage had, had planned to,

• 22:32Speaker 01

  had thought about programming tic-tac-toe for his, for his dream machine that he, that he was never able to finish.

• 22:38Lex Fridman?

  Wow, so that was the program he thought about?

• 22:41Speaker 01

  More than a hundred years ago.

• 22:42Lex Fridman?

  Yeah, wow.

• 22:43Speaker 01

  He had, he, he did that, okay. And I had, but, and, and I had, however, been influenced by a demonstration at the, 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 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, 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 it. Okay, so, so anyway, I, I, Brain One, random, you know.

• 23:27Speaker 01

  Knowing nothing, Brain 2, knowing everything. Then Brain 3 was the learning one. And I could, I could play Brain 1 against Brain 1, Brain 1 against Brain 2, and so on. And so you could also play against the user, against a live user. But, but, but, so I started going, the learning thing, and I said, okay, you know, take two random, random people, just playing tic-tac-toe, knowing nothing. And after about, I forget the number now, but it converged after about 600 games to a safe draw.

• 24:09Speaker 01

  The way my program learned was actually, it learned how not to make mistakes. Because, you know, it didn't try to do anything for winning. It just tried to say not losing.

• 24:21Lex Fridman?

  Yeah, not lose.

• 24:22Speaker 01

  So that was probably because of the way I designed the learning thing. I could have, you know, had a different reinforcement function that would reward brilliant play. But anyway, it didn't. And, and if I took a novice against, you know, a skilled player, it was able to learn how to play a good game. So that was, and that was really my, but after I finished that, I felt I understood programming.

• 24:54Lex 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?

• 25:09Speaker 01

  Yeah, I think naturally, it's, we're talking about Rod Brooks.

• 25:15Speaker 01

  He was teaching all kinds of very small devices to learn stuff. If a leaf drops off of a tree, you know, well, he was saying something, well, it learns if there's wind or not. But, but, I mean, 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 financial support. I don't know.

• 25:43Lex Fridman?

  Can I, can I ask you about that?

• 25:47Lex Fridman?

  He also mentioned that during those years, there was discussion about, inspired by Turing, about computation. You know, of what is computation?

• 26:01Speaker 01

  Yeah.

• 26:02Lex Fridman?

  And?

• 26:03Speaker 01

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

• 26:21Lex Fridman?

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

• 26:28Speaker 01

  It was just exciting to me to be able to control something, but not, but not, but not to say, hmm, am I solving a big problem? Or something like that? Or is this a step for humankind or anything? No, no.

• 26:43Lex Fridman?

  When did you first start thinking about computation in the big sense? You know, like the universal Turing machine sense?

• 26:51Speaker 01

  I mean, I had to pass an, I had to take, I had to take classes on computability 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, you know, I needed to pass the exams. But I didn't, I didn't invent any of that forward stuff. But I had great fun playing with the machine. You know, I, I wrote programs because it was fun to write programs and, and, and get this. I mean, it was like watching miracles happen.

• 27:30Lex Fridman?

  You mentioned in, in an interview that when reading a program, you can tell when the author of the program changed.

• 27:38Speaker 01

  Oh, okay.

• 27:41Lex Fridman?

  How the heck can you do that? Like, what makes a distinct style for a programmer, do you think? You know, there's different, Hemingway has a style of writing versus James Joyce or something.

• 27:54Speaker 01

  Well, those are pretty, yeah, those are pretty easy to imitate, but it's the same with music and whatever you can. I found, during the pandemic, I spent a lot more time playing the piano and I, and I found something that I'd had. I had it when I was taking lessons, you know, before I was a teenager and it was Yankee Doodle.

• 28:22Speaker 01

  Played in the style of, you know, and you had, you had Beethoven and you had Debussy 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, this author, Mario somebody or other had, had been able to reverse engineer the, the styles of, of those computers. So, but now specifically, to your question, I mean, there would be, there, it was, it was pretty obvious in this program I was reading.

• 29:04Speaker 01

  It was, it was a compiler and it had been written by a team at Carnegie Mellon. And I have no idea which program was responsible for, but, 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 could be done in one instruction would take three or something like that. That would be a pretty obvious change in style. But there were, but there were also flashes of brilliance where you could do in one instruction. Normally I used two because, because you knew enough about the way the machine worked that you could, that, that you could accomplish two, two goals in one step.

• 29:50Speaker 01

  So it was mostly the brilliance of the concept more than the semicolons or the use of short sentences versus long sentences or something like that.

• 30:01Lex Fridman?

  So you would see the idea in the code and you could see the different style of thinking expressed in the code.

• 30:07Speaker 01

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

• 30:23Lex Fridman?

  So if you think about Mozart, Beethoven, Bach, if somebody looked at Don Knuth code, would they be able to tell that this is a distinct style of thinking going on here? What do you think? And what would be the defining characteristic of the style?

• 30:45Speaker 01

  Well, my code now is literate programming, so it's a combination of English and C mostly. But if you just looked at the C 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 inline more than, instead of calling. Anyway, I have different subset of C that I use.

• 31:14Lex Fridman?

  Okay, but that's a little bit stylistic.

• 31:17Speaker 01

  Yeah, but with literate programming, you alternate between English and C or whatever.

• 31:23Lex Fridman?

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

• 31:35Speaker 01

  Yeah, yeah, that's the most.

• 31:42Speaker 01

  Significant thing I think to come out of the tech project is that I I realized that my programs were to be read by people and not just by computers and that typography could massively enhance that. And so, I mean, they're just wonderful. If they're going to look it up, they should also look up this book by called Physically Based Rendering by Matt Farr and gosh, anyway, it got an Academy Award, but it's but all the

• 32:23Speaker 01

  all the graphic effects you see in movies are accomplished by algorithms. And this book, the whole book is a literate program. It tells you not only how you do all the shading and bringing images in that you need for animation and textures and so on, but it also, you can run the code. And so I find it an extension of the way I of how to teach programming is by telling a story as part of the program.

• 33:02Lex Fridman?

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

• 33:08Speaker 01

  Yes, and especially by me. A week later or a year later.

• 33:13Lex Fridman?

  That's a good test. You yourself understand the code easily a week or a month or a year later.

• 33:21Speaker 01

  Yeah, so it's, it's the greatest thing since sliced bread.

• 33:27Lex Fridman?

  Programming or literate?

• 33:29Speaker 01

  Literate program.

• 33:30Lex Fridman?

  Okay. You heard it here first. Okay, you dodged this question in an interview I listened to. So let me ask you again here. What makes for a beautiful program?

• 33:45Speaker 01

  What makes for a beautiful program?

• 33:46Lex Fridman?

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

• 33:58Speaker 01

  Well, the reason I didn't answer is because there are dozens and dozens of answers to that. Because you can define beauty, the same person will define beauty a different way from hour to hour. I mean, it depends 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 can be understood easily. It's beautiful if it's a literate programming, it's beautiful, it makes you laugh.

• 34:35Lex Fridman?

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

• 34:41Speaker 01

  Readable, yeah.

• 34:42Lex Fridman?

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

• 35:05Speaker 01

  Whether humor is good in comments.

• 35:07Lex Fridman?

  Like when you add comments in the code.

• 35:10Speaker 01

  Yeah.

• 35:11Lex Fridman?

  I always thought a little bit of humor is good. It shows personality, it shows character, it shows wit and fun and all those kinds of things of the personality of the programmer.

• 35:23Speaker 01

  Yeah, okay, so a couple of days ago, I received a wonderful present from my former editor at Aston Wesley. He's downsizing his house and he found that somebody at the company had found all of their internal files about the art of computer programming from the 1960s. And they gave it to him. And then, you know, before throwing it in the garbage. And then, so he said, oh yeah, he planned to keep it for posterity, but now he realized that posterity is too much for him to handle, so he sent it to me. And so, and so I just received this big, big stack of letters.

• 36:12Speaker 01

  Some of which I had written to them, but but many of which they had written to early guinea pigs who were telling them whether they they should publish or not, you know. And and one of the things was in the in the comments to to volume one, the the major the major reader was was Bob Floyd, who is my great coworker in the sixties, died early, unfortunately, but but and and he he commented about the humor in it. And so so we had, you know, we ran it by me, you know, says, you know, keep this joke in or not, you know.

• 36:57Speaker 01

  They also sent it out to focus groups. What do you think about humor in it in a book about computer program?

• 37:05Lex Fridman?

  What's the conclusion?

• 37:06Speaker 01

  And I stated my philosophy is it said, you know, the ideal thing is that it's it's it's something where the reader knows that there's probably a joke here if he only understood it. And this is a motivation to understand, to to to think about it a little bit. But but anyway, it it it's a very delicate humor. I mean, it's it's it's really, each each century invents a different kind of humor, too. I mean, and and different different cultures have different different kind of humor.

• 37:39Lex Fridman?

  Yeah, like we met, we talked about Russia a little bit offline, you know, there's dark humor. And there's, you know, when when a country goes to something difficult.

• 37:50Speaker 01

  Right, battery life and stuff like this. And, you know, 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, yeah, it's it's called The Funny Men or something like that. But, yeah, okay. So anyway, I I think it's important to know that that this is part of life and and it should be fun and not.

• 38:15Lex Fridman?

  Yeah.

• 38:16Speaker 01

  And and so, you know, I wrote this this organ composition, which is based on the Bible, but I didn't refrain from putting little jokes in it also in the music.

• 38:28Lex Fridman?

  It's hidden in the music.

• 38:30Speaker 01

  It's it's it's there, yeah.

• 38:32Lex Fridman?

  A little humor is okay?

• 38:34Speaker 01

  Yeah, I mean, not egregious humor. So in in this correspondence, you know, there were. There were things I said, yeah, I really shouldn't have, I really shouldn't have done that. But, but other ones I, you know, I insisted on. And I've got jokes in there that, that nobody has figured out yet. In fact, in volume two, I've got a cryptogram, a message enciphered. And in order to decipher it, you're going to have to, have to break an RSA key, which is larger than people know how to break.

• 39:12Speaker 01

  And so, you know, if computers keep getting faster and faster, then, you know, it might be a hundred years, but somebody will figure out what this message is and they will laugh. I mean, I've got a joke in there.

• 39:24Lex Fridman?

  So that one you really have to work for. I, I don't know if you've heard about this. Let me explain it. Maybe you'll find it interesting. So OpenAI is a company that does AI 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 OpenAI Codex. And together with GitHub, they developed a system called OpenAI Copilot. Let me explain what it does.

• 40:01Lex Fridman?

  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 and any language that it trained on. You start, you write the first line and some comments, like what this code does. And it generates the function for you. And it does an incredibly good job. Like, it's not provably right, but it often does a really good job of completing the code for you.

• 40:38Speaker 01

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

• 40:42Lex Fridman?

  You could see a lot of examples where it did a good job. And so it's not a thing that generates a code for you. It starts, it gives you a, 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?

• 41:03Speaker 01

  Every year, we're going to be losing more and more control over what machines are doing. And people are saying, well, it seems to, like, when I was a professor at Caltech of the, in the, in the sixties, we had this, this guy who, who talked a good game.

• 41:23Speaker 01

  He could give inspiring lectures and you'd think, well,

• 41:28Speaker 01

  thrilling things he was talking about, an hour later, you say, well, what did he say?

• 41:33Speaker 01

  But, but, but he really felt that it didn't matter whether computers got the right answer or not. It just mattered whether it made you happy or not. In other words, if, you know, if, if, if your boss paid for it,

• 41:45Speaker 01

  you know, then you had a job, you could, you know, you could, you could take care of your wife.

• 41:50Lex Fridman?

  Happiness is more important than truth?

• 41:52Speaker 01

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

• 41:56Lex Fridman?

  I like it.

• 41:59Lex Fridman?

  And somehow you, you see.

• 42:01Speaker 01

  We're going that way. I mean, so many more things are taken over by saying, well, this seems to work. And so, and when there's, when, when there is a competing interest involved, neither side understands why the decision is being made.

• 42:19Speaker 01

  You know, we realize now that it's, that is bad, but, but consider what happens five, five year, 10 year, you down the line, when, when, when things get even more further detached and each thing is based on something from the previous year.

• 42:34Lex Fridman?

  Yeah. So you start to lose, the more you automate, the more you start to lose track of some deep human thing. Exponentially, but so that's the dark side. The positive side is.

• 42:49Lex Fridman?

  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.

• 43:08Speaker 01

  Yeah.

• 43:09Lex Fridman?

  I mean, that's the positive, but of course it does come with the darkness like of automation. What's better?

• 43:17Speaker 01

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

• 43:24Lex Fridman?

  Sure. So you're on the side of correctness, not beauty.

• 43:29Speaker 01

  I'm on the side of understanding.

• 43:31Lex Fridman?

  Understanding.

• 43:32Speaker 01

  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, you know, help guide some scientific experiment or something like this, you know, curing diseases or whatever. But, but when it, when it affects people's lives in a serious way, so if you're writing, if you're writing code, oh yeah, here, this is great. This will make a slaughter bot. Okay.

• 44:06Lex 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 a 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 weapon systems based.

• 44:30Speaker 01

  Well, we're all dead. Doesn't matter in that sense.

• 44:35Lex Fridman?

  Well, in the end, the, this whole thing ends anyway. So, but it pays.

• 44:43Speaker 01

  There is a heat death of the universe predicted, but I, but I'm trying to postpone that for.

• 44:50Lex Fridman?

  For a little bit. Well, it'd be nice that at the end, as we approach the heat death of the universe, there's still some kind of consciousness there to, to, to, to appreciate it. Hopefully human consciousness.

• 45:06Speaker 01

  I'll settle for 10 to the 10 to the 10 to the 10th year, some finite number, but, but things like this might be the reason we don't pick up any signals from.

• 45:18Speaker 01

  Extraterrestrial.

• 45:19Lex Fridman?

  They don't want anything to do with us. Oh, because they.

• 45:22Speaker 01

  Because they.

• 45:23Lex Fridman?

  They destroyed themselves.

• 45:24Speaker 01

  They invented it too.

• 45:29Lex 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.

• 45:40Speaker 01

  Et cetera, yeah. People have more more potential to to do harm now than by far than they did a hundred years ago.

• 45:50Lex Fridman?

  But are you optimistic about so the humans are good at creating destructive things, but also humans are good at solving problems?

• 45:59Speaker 01

  Yeah, I mean, there's half empty and half full, you know, that so.

• 46:03Lex Fridman?

  So how are we half full?

• 46:05Speaker 01

  I can go, yeah, so let me let me put it this way, because because it's the only way I can be optimistic, but but but but. Think of um.

• 46:17Speaker 01

  Of of of things that have changed because of civilization. That, you know, they don't occur just in nature. So so just uh just imagine the room we're in, for example. Okay, some, you know, we've got pencils, we've got books, we've got tables, we've got microphones. You know, clothing, food, all these things were added. Somebody invented them one by one and. Millions of of things uh that that we inherit, okay? And uh it's inconceivable that that so many millions of billions of things uh wouldn't have problems and. And we we get it all right.

• 47:02Speaker 01

  And and each one would have no negative.

• 47:07Speaker 01

  Uh effects and so on. So it it's very amazing that much works as does work.

• 47:13Lex Fridman?

  It's it's 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 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 it works. It doesn't go go wrong often enough for us to suffer.

• 47:46Speaker 01

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

• 47:53Lex Fridman?

  In a sub often suboptimal way.

• 47:55Speaker 01

  Oh, absolutely.

• 47:57Lex Fridman?

  But it's.

• 47:58Speaker 01

  But the but the the kind of things that I know how to i i improve require human beings to be rational. And I I'm losing my confidence that human beings are rational.

• 48:10Lex Fridman?

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

• 48:26Speaker 01

  Yeah.

• 48:26Lex 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 win 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? Uh, what's the wrong time? What is the wrong place for optimization?

• 49:09Speaker 01

  So first of all, the word optimization. I I I started out writing software and optimization was I was a compiler writer. So optimization meant making the uh making a better translation it it so that it would run faster on a on a machine. So an optimized program is just like, you know, you you you run a program and you set the optimization level for uh for uh to the compiler. So that's one word for optimization. Um, and at that time, I I happened to be looking in an unabridged dictionary. For some reason or other, and I came to word optimize. I said, what's the meaning of the word optimize?

• 49:54Speaker 01

  And it says, to view with optimism.

• 49:59Speaker 01

  And you look in Webster's dictionary of English language in nineteen six, early nineteen sixties, that's what optimize me meant, okay.

• 50:09Speaker 01

  Now, so people started doing cost optimization, other kinds of things, you know, whole subfields of, of algorithms and economics and whatever are based on what they call optimization now. But, but to me, optimization, when I was saying that, was saying, changing a program to make it more tuned to the machine. And I found out that when a person writes a program, he or she tends to think that the parts that were hardest to write are going to be hardest for the computer to execute.

• 50:52Speaker 01

  So, maybe I have ten pages of code, but I had to work a week writing this page. I mentally think that when the computer gets to that page, it's going to slow down.

• 51:06Lex Fridman?

  Right.

• 51:07Speaker 01

  It's gonna say, oh, I don't understand what I'm doing, I better, I better be more careful. Anyway, this is, of course, silly, but it's, it's something that we, that we, that we don't know, when we write a piece of code, we don't know what, whether the computer is actually going to be executing that code very much. So, so people had, had a very poor understanding of, of what the computer was actually doing. I made one test where, where we studied a Fortran compiler, and it was spending more than eighty percent of its time reading the comments card.

• 51:45Speaker 01

  But as a programmer, we were really concerned about how fast it could take a complicated expression that had lots of levels of parentheses and, and, and convert that into something. But that was just, you know, less than one percent of the, so if we optimize that. Uh, we didn't know what we were doing, but, but, but if, if we knew that it was spending eighty percent of his time on the comments card, you know, in ten minutes, we could, we could make the, the compiler run more than twice as fast.

• 52:15Lex Fridman?

  And you can only do that once you've completed the program and then you empirically study where.

• 52:20Speaker 01

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

• 52:24Lex Fridman?

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

• 52:30Speaker 01

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

• 53:05Lex Fridman?

  Right.

• 53:05Speaker 01

  Because I've changed my data structure or something that, that made it less adaptable. So one of the great, uh, principles of computer science is, is, is laziness or whatever you call it, uh, uh, late binding, uh, you know, don't, you hold, hold off decisions when you can. Um, and, and, and, you know, and we understand now, uh, quantitatively how valuable that is.

• 53:34Lex Fridman?

  What, what do you mean? We understand. So you mean from a.

• 53:37Speaker 01

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

• 53:56Lex Fridman?

  So in all kinds of domains, there's an optimality to laziness in many cases.

• 54:00Speaker 01

  Decision is not made in advance. So instead you, you, you, you design in order to be flexible, uh, uh, to, to change with the, uh, with the way the wind is blowing.

• 54:11Lex Fridman?

  Yeah. But so the reason that line resonated with a lot of people is because.

• 54:18Lex Fridman?

  There's something about the programmer's mind that wants, that enjoys optimization. So it's a constant struggle to balance laziness and lay binding with the desire to optimize. The elegance of a well-optimized code is something that's compelling to programming.

• 54:41Speaker 01

  Yeah, it's another concept of beauty.

• 54:46Lex 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 a universal Turing machine cannot 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.

• 55:23Speaker 01

  Yes, my daughter's kids played with his kids in Oxford.

• 55:29Lex Fridman?

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

• 55:43Speaker 01

  I mean, I can say yes or no, but I have no reason.

• 55:50Speaker 01

  I mean.

• 55:50Lex Fridman?

  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 useful to think about the limits?

• 56:00Speaker 01

  Unanswerable question, in my opinion, is no better than anybody else.

• 56:04Lex Fridman?

  You think it's unanswerable? So you don't think eventually science will be able to.

• 56:07Speaker 01

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

• 56:10Lex Fridman?

  But angels aren't.

• 56:13Speaker 01

  Anyway, there are lots of things that are beyond, that we can speculate about. But I don't want somebody to say, oh, yeah, Canoe said this, and so he's smart. And so that must be, I mean, I say it's something that we'll never know.

• 56:30Lex Fridman?

  Interesting. Okay, that's a strong statement. I don't.

• 56:35Lex Fridman?

  I personally think it's 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.

• 56:46Speaker 01

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

• 56:48Lex Fridman?

  Yeah. But right now, you don't have a good intuition.

• 56:52Speaker 01

  I mean, that's also possible, you know, that AI, you know, created the universe. Intelligent design has all been done by an AI.

• 57:01Lex Fridman?

  Yes.

• 57:02Speaker 01

  This is, I mean, all of these things are, but, but, but, but you're asking me to, 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.

• 57:21Lex 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.

• 57:33Speaker 01

  Yeah, well, I know where.

• 57:34Lex Fridman?

  And consciousness is.

• 57:35Speaker 01

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

• 57:43Lex Fridman?

  No, he doesn't. He doesn't prove it. He is following intuition.

• 57:47Speaker 01

  But, but, I mean, you have to ask John McCarthy, John McCarthy, I think, were totally unimpressed by these statements.

• 57:58Lex Fridman?

  So you, you don't think, so even like the Turing paper on, on the Turing test that, you know, starts by asking, can machines think?

• 58:08Speaker 01

  Oh.

• 58:09Lex Fridman?

  You don't think these kind of, Turing doesn't like that question.

• 58:14Speaker 01

  Yeah. I don't consider it important, let's just 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 Remat hypothesis or something.

• 58:35Lex Fridman?

  So when you say, it's an interesting statement, beyond knowledge.

• 58:39Speaker 01

  Yeah.

• 58:39Lex Fridman?

  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.

• 58:50Speaker 01

  Yeah.

• 58:51Lex Fridman?

  And so that's why it's beyond knowledge, but that doesn't mean it's not eventually going to be formalized.

• 58:56Speaker 01

  Yeah, yeah, maybe consciousness will be understood someday, but the last time I checked, it was still 200 years away. I haven't been specializing in this by any means, but, but, but I went to lectures about it 20 years ago when I was, there was, there was a symposium at the American Academy in, in Cambridge. And it started out by, by saying essentially, everything that's been written about consciousness is, is hogwash.

• 59:27Lex Fridman?

  I tend to,

• 59:31Lex Fridman?

  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

• 59:41Speaker 01

  Yeah.

• 59:42Lex Fridman?

  understanding. Still, I think, once you start creating artificial intelligence systems that interact with humans,

• 59:53Lex Fridman?

  and they have personality, they have identity, you start flirting with the question of consciousness, not from a philosophical perspective, but from an engineering perspective.

• 1:00:04Speaker 01

  Yeah.

• 1:00:05Lex Fridman?

  And then it starts becoming much more, like, I feel like

• 1:00:08Speaker 01

  Yeah, yeah, don't misunderstand me. I, I, I certainly don't disagree with that at all. And even at these lectures that we had, you know, 20 years ago, there, there were neurologists pointing out that That human beings had actually decided to do something before they were conscious of making that decision.

• 1:00:30Lex Fridman?

  Yeah.

• 1:00:31Speaker 01

  I mean, they could tell that, you know, that signals were being sent to their arms before they, before they, they knew that they were, and things like this are true. And, and my, you know, Les Valiant has an architecture for the brain and more recently, Christus Papadometrio, in the Academy of Science Proceedings a year ago, with, with two other people, but I know Christus very well. And, and he's got this, this model of, this architecture by which you could create a,

• 1:01:12Speaker 01

  things that, that correlate well with, with experiments that are done on consciousness. And, and, and he, he actually, you know, has a, a machine language that, in which you can, you can write code and, and test hypotheses. 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 to explain the miracle of consciousness is that, that, that somehow inside of our brains, we're

• 1:01:57Speaker 01

  having a continual survival for the fittest competition. And I'm speaking to you, all the possible things I might be wanting to say.

• 1:02:09Lex Fridman?

  Are all in there. And there's like a voting going on.

• 1:02:12Speaker 01

  Yeah, right. And, and one of them is, is winning. And, and that's affecting, you know, the next sentence and so on.

• 1:02:21Lex Fridman?

  Yeah.

• 1:02:22Speaker 01

  And there was this book, Machine Intelligence or something.

• 1:02:26Lex Fridman?

  On Intelligence.

• 1:02:27Speaker 01

  On Intelligence, yeah. Bill Atkinson was, was, was a total devotee of that book.

• 1:02:36Lex Fridman?

  Well, I like, whether it's consciousness or something else, I like the storytelling part that we, it feels like, for us.

• 1:02:46Lex Fridman?

  Humans, it feels like there's a concrete, it's almost like literary 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 just kind of generates a story for you to, a consistent story for you to believe. And that makes it all nice.

• 1:03:16Speaker 01

  Yeah. And so I prefer to talk about things that I have some expertise in than things which I'm only

• 1:03:27Speaker 01

  on the sideline.

• 1:03:29Lex 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. It'd 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?

• 1:03:43Speaker 01

  I think the game of life is wonderful and

• 1:03:51Speaker 01

  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 important thing about the game of life is how it focused for me what it meant to have free will or not.

• 1:04:20Speaker 01

  Because the game of life is obviously totally deterministic.

• 1:04:24Lex Fridman?

  Yes.

• 1:04:24Speaker 01

  And I find it hard to believe that anybody who's ever had children cannot believe in free will. On the other hand, this makes it crystal clear.

• 1:04:37Speaker 01

  John Conway said.

• 1:04:42Speaker 01

  He wondered whether it was immoral to shut the computer off after he got into a particularly interesting play of the game of life.

• 1:04:51Lex Fridman?

  Wow. Yeah, so there is, to me, the reason I love the game of life is exactly as you said, a clear illustration that from simple initial conditions with simple rules, you know exactly how the system is operating, is deterministic, and yet, if you let yourself, 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.

• 1:05:25Speaker 01

  If the universe is finite, we're all living in the game of life, just slowed down, I mean, it sped up a lot.

• 1:05:35Lex 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?

• 1:05:47Speaker 01

  Yeah, I mean, I've got, I've got a dozen exercises in volume for fascicle six that actually work rather well for that purpose.

• 1:06:00Lex Fridman?

  But.

• 1:06:01Speaker 01

  Bill Gosper's came up with the, with the algorithm that allows, that allowed Golly to, you know, to run thousands and thousands of times faster. You know the website called Golly? G O L L Y?

• 1:06:19Lex Fridman?

  It simulates the cellular automata, like game of life?

• 1:06:22Speaker 01

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

• 1:06:25Lex Fridman?

  Can I ask you about John Conway?

• 1:06:27Speaker 01

  Yes. In fact, I'm just reading now the, the issue of mathematical intelligence that came in last, last week. It's a whole issue devoted to, to, you know, remembrance of, of him.

• 1:06:43Lex Fridman?

  Did you know him?

• 1:06:45Speaker 01

  I, I slept overnight in his house several times. Yeah.

• 1:06:51Lex Fridman?

  He recently passed away.

• 1:06:53Speaker 01

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

• 1:07:03Lex Fridman?

  What are some memories of him, of his work that stand out for you? Did, on a technical level, did any of his work inspire you? On a personal level, did he himself inspire you in some way?

• 1:07:20Speaker 01

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

• 1:07:29Lex Fridman?

  Wow, okay, that's a long time ago.

• 1:07:31Speaker 01

  Yeah, you were minus 20 years old or something, I don't know, 1967. But there was a conference where...

• 1:07:43Speaker 01

  I think I spoke, I was speaking about something that's known as the Knuth Bendix algorithm now. But he gave a famous talk about knots. And I didn't know at the time, but anyway, that talk had now... It was the source of thousands and thousands of papers since then. And he was reported on something that he had done in high school,

• 1:08:13Speaker 01

  you know, almost 10 years earlier, before this conference, but he never published it. And he climaxed his talk by building some knots. You have these little plastic things that you can stick together. It's something like Lego, but easier.

• 1:08:36Speaker 01

  And so he made a whole bunch of knots in front of the audience and so on, and then disassembled. So it was a dramatic lecture before he had learned how to give even more dramatic lectures later.

• 1:08:50Speaker 01

  All right.

• 1:08:51Lex Fridman?

  Were you at that lecture?

• 1:08:52Speaker 01

  And I was there, yeah, because I had to, you know, I was at the same conference.

• 1:08:58Speaker 01

  For some reason, I was, I happened to be in Calgary

• 1:09:03Speaker 01

  the same day that he was visiting Calgary.

• 1:09:07Speaker 01

  And it was the spring of 72, I'm pretty sure. And we had lunch together.

• 1:09:15Speaker 01

  And he wrote down during the lunch on a napkin all of the facts about what he called numbers. And I, and, and he covered the napkin with, with the theorems about his, his idea of numbers. And I thought this was incredibly beautiful. And, and later in 1972, my sabbatical year began and I went to Norway. And, and in December of that year, in the middle of the night, the thought came to me,

• 1:09:55Speaker 01

  you know, Conway's theory about numbers would be a great thing to 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 in dialogue by, by Alfred Renier, where he, kind of a Socratic thing where the two characters were talking to each other about mathematics. And so I, and so at the end, in the morning, I, I woke up my wife and said, Jill, I think I want to write a book about Conway's theory.

• 1:10:36Speaker 01

  And, you know, you know, I'm supposed to be writing the art of computer program and 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. We were in sabbatical in Norway. And I rented the hotel in, in downtown Oslo and did nothing else except write Conway's theory. And I, I changed the name to Surreal Numbers. So this book is now published as Surreal Numbers. And

• 1:11:22Speaker 01

  And you know, we figured out, we'd always wonder what would he like to have an affair in a hotel room. 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 was run by a mission organization. These ladies were probably very strict. But anyway, so.

• 1:11:45Lex Fridman?

  Yeah.

• 1:11:46Speaker 01

  So.

• 1:11:47Lex Fridman?

  It's a wild week in every way.

• 1:11:50Speaker 01

  But the thing is, I had lost that, I had lost that napkin in which he wrote the theory. But, but I, I, I looked for it, but I couldn't find it. So I tried to recreate from memory what he had told me at that luncheon in Calgary. And, and as I, as I wrote the book, I, I was going through exactly what I, what the characters in the book were supposed to be doing. So I start with the, with the two axioms and start out the whole thing. 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, I, my characters make too, you know. And,

• 1:12:29Speaker 01

  and, and so it was, it's a long, long story. And I, but I worked through this week. And it was, it was one of the most intense weeks of my life. And, and I, I, I described it in other places. But, but, but anyway, after six days, I, I finished it. And on the seventh day, I rested and, and I sent my secretary to type it. It was flowing as I was writing it faster than I could think almost. But, but, but after I finished it, and tried to write a letter to my secretary telling her how to type it, I couldn't write anymore.

• 1:13:12Lex Fridman?

  He gave it everything.

• 1:13:14Speaker 01

  The muse had left me completely.

• 1:13:15Lex Fridman?

  Can you explain how that week could have happened? Like, why? That seems like such a magical week of productivity.

• 1:13:22Speaker 01

  I have no idea. But anyway, there was some, it was almost as if I was channeling. So, so, so the book was typed, I sent it to Conway. And, and he said, well done, you got the axiom, the one axiom wrong. Is there a difference between less than or equal and not greater than? I don't know, the opposite of being greater than.

• 1:13:48Lex Fridman?

  Yeah.

• 1:13:48Speaker 01

  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 do than John's original. So, and we visited him at his house in Cambridge in April. We took a boat actually from Norway over to across the channel and so on and stayed with him for some days. And he told, he talked, we talked about all kinds of things he has. He had puzzles that I'd never heard of before. He had a great way to solve the game of Solitaire. Many of the common interests that we'd, you know, he'd never written up.

• 1:14:33Speaker 01

  And but anyway, 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 axiom. And so that was the most intensive connection with Conway. After that.

• 1:14:54Lex Fridman?

  It started with a napkin.

• 1:14:56Speaker 01

  It started with a napkin. But, but, but we would run into each other. Yeah, the next really, I was giving lectures in Montreal.

• 1:15:11Speaker 01

  I was giving a series of, of seven lectures about a topic called stable marriages. And, and he arrived in Montreal between my sixth and seventh lecture. And, and we met at a party. And I started telling him about the topic I was doing. And he sat and thought about it and he came up with a beautiful theory to show that the, I mean, in technical terms, 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 lower bound of two stable pairings and least upper bound of two stable marriage.

• 1:15:57Speaker 01

  And so I could use it in my lecture the next day. And he came up with this theorem during the party.

• 1:16:04Speaker 01

  And it

• 1:16:04Lex Fridman?

  It's a brilliant

• 1:16:06Speaker 01

  It's a distributive last, I mean, it's, it's, you know, it added greatly to the theory of of stable managing.

• 1:16:16Lex Fridman?

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

• 1:16:23Speaker 01

  So we celebrated sixty years of wedded bliss last month. And and we met because I was dating her roommate. 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 than her. I enjoyed her roommate.

• 1:16:51Lex Fridman?

  You guys are majoring the same thing?

• 1:16:54Speaker 01

  No, no, no.

• 1:16:55Lex Fridman?

  Because I read something about working on a computer in grad school on a difficult computer science topic.

• 1:17:04Speaker 01

  So so she's an artist and I'm

• 1:17:07Lex Fridman?

  Okay.

• 1:17:07Speaker 01

  And I'm a geek and

• 1:17:10Lex Fridman?

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

• 1:17:17Speaker 01

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

• 1:17:21Lex Fridman?

  Okay.

• 1:17:22Speaker 01

  And and

• 1:17:24Lex Fridman?

  You're the tutor?

• 1:17:25Speaker 01

  No, no, yeah, no, we, yeah, we, there were terrible times, you know, trying to learn certain concept, but I learned art from her. And so we worked together, you know, occasionally in design projects. But but every year we write a Christmas card and and we each have to

• 1:17:50Speaker 01

  compromise our our own notions of beauty.

• 1:17:54Lex Fridman?

  Yes. When did you fall in love with her?

• 1:17:59Speaker 01

  That day that I asked her about her roommate.

• 1:18:04Lex Fridman?

  Okay.

• 1:18:05Speaker 01

  I mean, no, I, I, I, okay, so you're, I, I don't mind telling these things, depending on how you far, how far you go, but.

• 1:18:17Lex Fridman?

  I promise, I promise not to go too far.

• 1:18:20Speaker 01

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

• 1:18:30Lex Fridman?

  Wow. And 60 years.

• 1:18:32Speaker 01

  Yeah.

• 1:18:34Lex Fridman?

  Is there a secret you can, you can say in terms of stable marriages of how you stayed together so long?

• 1:18:42Speaker 01

  The topic, stable marriage, by the way, is not, is, is a technical term.

• 1:18:48Lex Fridman?

  Yes, it's, it's, it's a joke, Don.

• 1:18:52Speaker 01

  But two different people will have to learn how to compromise and, and, and work together and, and, and you're gonna have ups and downs and, 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, if you decide that it's, that, that there's gonna be no frustration, then.

• 1:19:28Lex Fridman?

  So you, you're gonna have to compromise on your notions of beauty when you write Christmas cards?

• 1:19:32Speaker 01

  That's it.

• 1:19:35Lex Fridman?

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

• 1:19:40Speaker 01

  Yep.

• 1:19:41Lex Fridman?

  Probably you've met him in Caltech.

• 1:19:44Speaker 01

  Well, we knew each other, yeah, at Caltech for sure, yeah.

• 1:19:50Lex Fridman?

  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?

• 1:20:04Speaker 01

  So we used to go to each other's lectures and, and, but, but if I saw him sitting in the front row, it would throw me for a loop, actually, and I, I would, I would miss a few.

• 1:20:19Speaker 01

  A few sentences. What unique story do I have about, I mean, I, I, I often refer to his, his time in Brazil,

• 1:20:31Speaker 01

  where he 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 me 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 the textbook had been written by his host and, and it was a big embarrassing incident, but he had previously asked his host if, if he was supposed to tell the truth. But, but anyway, it epitomizes the way education goes wrong in all kinds of fields and has

• 1:21:14Speaker 01

  to periodically be brought back from, from, from a process of, of giving credentials to a process of giving knowledge.

• 1:21:25Lex Fridman?

  That's probably a story that continues to this day in a bunch of places where it's too easy for educational institutions to fall into credentialism versus inspirationalism. I don't know if those are words, but sort of

• 1:21:45Speaker 01

  Yeah.

• 1:21:46Lex Fridman?

  understanding versus just giving a little

• 1:21:49Speaker 01

  It, it, it

• 1:21:50Lex Fridman?

  plaque.

• 1:21:51Speaker 01

  And, you know, it's, it's very much like what we were talking about. If you want the computer to, if you want to be able to believe the answer, a computer is

• 1:22:01Lex Fridman?

  Sure.

• 1:22:02Speaker 01

  is doing that. One of the things Bob Floyd showed me in the sixties, there was a, he loved this cartoon. There was a, 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 a hundred years. And the other guy says, oh, so how do you know it's right?

• 1:22:32Lex Fridman?

  That's a good line.

• 1:22:36Lex Fridman?

  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 or are they strongly overlapping?

• 1:23:00Speaker 01

  It's quite different, in my opinion. I started as a physics major and I switched into math. And probably the reason was that I could, I could get A plus on the physics exam, but I, but 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, I, I knew, you know, why the teacher set those problems and I thought of other problems that I could set too. And I believe it's, it's quite a different mentality.

• 1:23:36Lex Fridman?

  Is it, has it to do with your philosophy of geekdom?

• 1:23:41Speaker 01

  No, it's, I mean, some of my computer scientist friends are really good at physics and others are not. And, and I'm, you know, I'm really good at algebra, but not at geometry. Talk about different parts of mathematics, you know, it's, it's, so, so the different kind of physical, but physicists 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.

• 1:24:09Lex Fridman?

  So you, you basically, you like to see the world in, in, in discreet ways and then physics is more continuous?

• 1:24:17Speaker 01

  Yeah, I, I, I'm not sure if Turing would have been a great physicist. I think it was a pretty good chemist, but, but I don't know. But, but, but anyway, I see things, I, I, I believe that computer science is largely.

• 1:24:36Speaker 01

  Driven by people who have brains who are good at resonating with certain kind of of of concepts and like quantum computers, it takes a different kind of brain.

• 1:24:52Lex Fridman?

  Yeah, that's interesting. Yeah, it's it's well, quantum computers is almost like at the intersection in terms of brain between computer science and physics is they involves both, at least at this at this time. But there is like the physicists I've known, they have incredibly powerful intuition.

• 1:25:14Speaker 01

  And and they're like, I mean, statistical mechanics. So I I study statistical mechanics and and, you know, I mean, random processes are are related to algorithms in a lot of a lot of ways. And but there's lots of different flavors of flavors of physics, as there are different flavors of mathematics as well. But but the thing is that I I don't see, well, actually, when they talk to physicists, use completely different language than when they're talking to when they're writing expository papers. And so I didn't understand quantum mechanics at all from reading about it in Scientific American. But but when I read,

• 1:25:57Speaker 01

  you know, how they described it to each other, talking about eigen eigenvalues and and various mathematical terms that that made sense, then it made sense to me. But 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 it I really, I really didn't.

• 1:26:25Lex Fridman?

  Well, Feynman also spoke in this way. So Feynman, I think, prided himself on really strong intuition. But at the same time, he was hiding all the the really good, the deep computation he was doing.

• 1:26:38Speaker 01

  So so there was one thing that that. I was never able to, I wish I'd had more time to work out with him, but I guess I could describe it for you. There's, there's something that got my name attached to it called Knuth arrow notation, but it's a notation for very large numbers. And so it, I find out that, somebody invented it in, in 1830s. It's fairly easy to, to understand anyway. So you start with X plus X plus X plus X N times, and you can call that X N. So X N is multiplication.

• 1:27:23Speaker 01

  Then you take X times X, times X times X N times, that gives you exponentiation, X to the Nth power. So that's one arrow, X. So X N with no arrows is multiplication. X arrow N is X to the Nth power.

• 1:27:40Lex Fridman?

  Yeah, just to clarify for the, so X times X times X N times is obviously X N.

• 1:27:49Speaker 01

  X plus X plus X N times.

• 1:27:54Lex Fridman?

  Oh, yeah. Okay. And then.

• 1:27:55Speaker 01

  X N.

• 1:27:56Lex Fridman?

  And then multiplication is X to the N. And then, and then here the arrow is when you're doing the same kind of repetitive operation for the exponential.

• 1:28:06Speaker 01

  So I, so I put in one arrow and I get X to the Nth power. Now I put in two arrows and that makes, takes X to the X to the X to the X to the X N times power. So in other words, if, if, if it's two, 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'd be 16. Okay.

• 1:28:31Lex Fridman?

  Okay.

• 1:28:31Speaker 01

  So, so, so that's the double arrow. And now you can do a triple arrow, of course, and, and so on. And, and I, I had this, this paper called, well, essentially big numbers. You know, you, you try to impress your friend, but by saying a number they've never thought of before.

• 1:28:56Lex Fridman?

  Yeah.

• 1:28:56Speaker 01

  And, and, and I, I gave a special name for it. We designed a font for it that has script K and so on, but it, but it really is 10. I think like 10 quadruple arrow 3 or something like that. And I claim that that number is so mind boggling that you can't comprehend how large it is. But anyway, Feynman, I talked to Feynman about this and he said, oh,

• 1:29:24Speaker 01

  let's just, let's just use double arrow. But instead of taking integers, let's consider complex numbers. So you have, I mean, okay, X, X arrow arrow 2, that means X, X,

• 1:29:40Speaker 01

  but what about X, X double arrow 2, 2.5? Well, that's not too hard to figure out. That's interpolate between those. But what, what, what X double arrow I or 1 plus I or some complex number? And, and so he claimed that, that, that there was no analytic function that would, that would, that would do the job.

• 1:30:09Speaker 01

  But I, I, I didn't know how he could claim that that was, that wasn't true.

• 1:30:17Speaker 01

  And his next question was, did then have a complex number of arrows?

• 1:30:24Speaker 01

  Yeah, okay.

• 1:30:25Lex Fridman?

  Wow, okay.

• 1:30:26Speaker 01

  Okay, so, so that's, that's Feynman.

• 1:30:28Lex Fridman?

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

• 1:30:44Speaker 01

  Yeah, all right. So it should be actually Morris-Pratt-Knuth. But we decided to use alphabetical order when we published the paper. The problem is something that everybody knows now if they're, if they're using a search engine.

• 1:31:02Speaker 01

  You have a, a large collection of text and you want to know if, if the word Knuth appears anywhere in the text, let's say, or, or some. Some other word that's less interesting than

• 1:31:18Lex Fridman?

  That's the most interesting word. Like Morris, right?

• 1:31:22Speaker 01

  So, yeah, we have, we have a, a large piece of text and it's all one long, one dimensional thing. You know, first letter, second letter, et cetera, et cetera, et cetera. And so, uh, the question, you'd like to be able to do this quickly.

• 1:31:41Speaker 01

  And the obvious way is, uh, let's say we're looking for Morris. Then, okay, so we would, we would go through and wait till we get to letter M. Then we look at the next word and sure enough, it's an O and then an R. But then, oh, too bad.

• 1:31:59Speaker 01

  Yeah, the next letter is, is E. So we missed, we missed out on Morris. And so, uh, we go back and start looking for another.

• 1:32:10Lex Fridman?

  All over again.

• 1:32:10Speaker 01

  So that's the obvious way to do it. All right.

• 1:32:15Speaker 01

  And, and Jim Morris noticed there was a more clever way to do it. The obvious way would have started, let's say, you know, we found that letter M at character position 1,000. So it would have started next at character position 1,001. But, but he, but he said, no, look, we, we already read the O and the R. And we know that they aren't M's. So we can, we can start, we don't have to read those over again. All right. 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.

• 1:33:00Lex Fridman?

  Like repeating patterns in the, at the beginning, at the middle.

• 1:33:04Speaker 01

  Right, right. So, so, um, he, 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 some routine. I was supposed to find occurrences of patterns in text and. And um, but he didn't explain it. 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, you know, because it wasn't understood. Nobody knew about this particularly.

• 1:33:45Speaker 01

  Vaughn Pratt also had independently discovered it a year or two later.

• 1:33:53Speaker 01

  I forget why. I think Vaughn was studying some technical problem about palindromes or something like that. He wasn't really, Vaughn wasn't working on on text searching, but he was working on on an abstract problem that had that that was related. Well, at that time, Steve Cook was professor at Berkeley. And it was the greatest mistake that Berkeley CS department made was not to give him tenure. And so Steve went to Toronto. But but I but I knew Steve while he was at Berkeley.

• 1:34:35Speaker 01

  And he had come up with a with a very peculiar theorem about a technical concept called a stack automaton. And a stack automaton, it is a machine that that it can't do everything a Turing machine could do, but it it can only look at something on at the top of a stack, or it can put more things on the stack, or or it can take things off the stack. Like, it can't remember a long string of symbols, but but it can remember them in reverse order. So so if you tell a stack automaton, A, B, C, D, E, it can it can tell you afterward, E, D, C, B, A.

• 1:35:16Speaker 01

  You know, it doesn't have any other memory except except this one thing that it can see. And and Steve Cook proved this amazing thing that says, if a stack automaton can recognize a language.

• 1:35:31Speaker 01

  Where the strings of the language are length n, in any amount of time whatsoever, for the stack automaton, Mike uses a zillion steps, a regular computer can recognize that same language in time n log n. 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 fast. The stack automaton 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 cool theorem.

• 1:36:14Speaker 01

  And so I tried it out on a problem where I knew a stack automaton could do it, but I couldn't figure out a fast way to do it on a regular computer. I thought I was a pretty good programmer, but by golly, I couldn't think of any way to recognize this language efficiently. So I went through Steve Cook's construction. I filled my blackboard with all the, everything that stack automaton did, you know, I wrote down, and then I tried to see patterns in that, and how did he convert that into a computer program on a regular machine?

• 1:36:59Speaker 01

  And finally, I psyched it out. What was the thing I was missing so that I could say, oh yeah, this is what I should do in my program. And now I have a efficient program. And so I would never have thought about that if I hadn't had his theorem, which was purely abstract thing.

• 1:37:25Lex Fridman?

  So you used this theorem to try to intuit how to use the stack automaton for the string matching problem?

• 1:37:31Speaker 01

  Yeah, so the problem I had...

• 1:37:36Speaker 01

  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 automaton. And so when I looked at what that told me, then I had a nice algorithm for this string matching problem. And it told me exactly what I should remember as I'm going through the string. And I worked it out and I wrote this little paper called automata theory can be useful. And the reason was that it was first, I mean, I had been reading all kinds of papers about automata theory. But it never taught me, it never improved my programming for everyday problems.

• 1:38:19Speaker 01

  It was something that you published in journals and, you know, it was, it was interesting stuff. But it, but here was a case where I couldn't figure out how to write the program. I had a theorem from automata theory, then I knew how to write the program. So this was for me, a change in life. I started to say, maybe I should learn more about automata. And, and, and I showed this note to Vaughn Pratt and he said, he, that's similar to something I was working on. And then, and Jim Morris was at Berkeley too at the time. Anyway, he, he had, he's had an illustrious career, but I haven't kept track of Jim.

• 1:39:03Speaker 01

  But Vaughn is my colleague at Stanford and my student later. But, but this was before Vaughn, Vaughn was still a graduate student and hadn't come to Stanford yet. 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, you know, a different aspect of it. And so we could put our, our, our things together. It was my job to write the paper.

• 1:39:35Lex Fridman?

  How did the elephant spring to life?

• 1:39:37Speaker 01

  Spring to life was because I, I had drafted this paper, automata theory.

• 1:39:44Lex Fridman?

  Oh.

• 1:39:45Speaker 01

  Can be useful, which was seen by Vaughn and then by Jim. And then, then, then we combined because maybe they had also been thinking of writing something up about it.

• 1:39:55Lex Fridman?

  About specifically the string matching.

• 1:39:57Speaker 01

  Specifically the string matching problem, period.

• 1:40:03Lex Fridman?

  Let me ask a ridiculous question. Last time we talked, you told me what the most beautiful algorithm is, actually, 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...

• 1:40:24Speaker 01

  The hardest thing that I've ever been involved with?

• 1:40:27Lex Fridman?

  Yeah.

• 1:40:28Speaker 01

  Okay, well, yeah, that's...I don't know how to answer questions like that, but in this case, it's pretty clear.

• 1:40:36Lex Fridman?

  Okay.

• 1:40:37Speaker 01

  Because it's called the birth of the giant component. Okay, so now let me explain that, because this actually 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. So, start with the idea of a random graph. Now, this is...here, we just say we have n points that are totally unconnected, and there's no geometry involved. There's no saying some points are further apart than others.

• 1:41:21Speaker 01

  All points are exactly alike, and let's say we have 100 points, and we number them from 0 to 99. All right? Now, let's take pi, the digits of pi, so two at a time. So we had 31, 41, 59, 26. We can go through pi. And so, we take the first two, 31, 41, and let's put a connection between point 31 and point 41. That's an edge in the graph.

• 1:42:02Speaker 01

  Then we take 5, 9, 2, 6, and make another edge. And 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...

• 1:42:21Speaker 01

  M edges, okay. Each edge is completely, we forgot about e- edges we had before. We might can edge twice, we might can edge from a point to itself even. Um, you know, maybe pi is gonna have a run of four digits in there. So we're gonna, but anyway, we're evolving a graph at random. Um, and a magical thing happens when the number of edges is like point four nine and uh, to maybe N is a million and I have, you know, four hundred and ninety thousand edges.

• 1:43:04Speaker 01

  Uh, then it almost all the time, it it consists of isolated trees.

• 1:43:13Speaker 01

  Not even any loops.

• 1:43:16Lex Fridman?

  It's a very small number of edges so far.

• 1:43:19Speaker 01

  A little less than half N.

• 1:43:21Lex Fridman?

  N, right.

• 1:43:22Speaker 01

  But if I had point five one edges, so a little more than half N. So, you know, million points, five hundred and ten thousand edges. Now it probably has a, a, a, one component that's much bigger than the others.

• 1:43:43Speaker 01

  Um, and we call that the giant component.

• 1:43:47Lex Fridman?

  So can you clarify, so can you clarify, first of all, is there a name for this kind of random, super cool pi random graph?

• 1:43:55Speaker 01

  Well, I I call it the pi graph. No, no, I, the pi graph is actually, my my pi graph is based on, on binary representation of pi, not the decimal representation of pi. But, but, but, but anyway, let's suppose I was rolling dice instead.

• 1:44:16Lex Fridman?

  Okay.

• 1:44:16Speaker 01

  So, so I might have.

• 1:44:17Lex Fridman?

  So it doesn't, doesn't have to be pi?

• 1:44:19Speaker 01

  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.

• 1:44:34Speaker 01

  That's the process.

• 1:44:35Lex Fridman?

  Yeah. So there's, there's nothing magical about pi that you're giving us an example.

• 1:44:39Speaker 01

  I was using pi to, to, I was sort of saying, pi is sort of random that nobody knows a pattern in.

• 1:44:44Lex Fridman?

  Exactly. Got it. Got it, got it.

• 1:44:46Speaker 01

  But it's not, yeah, I could have just as well drawn straws or something. This was a concept invented by Erdem and Rainey, and they called it the evolution of random graphs. And if you start out with, with a large number n, and you, and you repeat this process, all of a sudden a big bang happens at one half n. There'll be two points together, then maybe we'll have, have, have three.

• 1:45:13Speaker 01

  And then, you know, and then they maybe branch out a little bit, but, but they'll all be separate until we get to one half n. And, and we pass one half n and all of a sudden, there's substance to it. There are, there's a big clump of stuff that's all joined together.

• 1:45:31Lex Fridman?

  So it's almost like a phase transition of some kind?

• 1:45:33Speaker 01

  It's exactly, it, it, it's a phase transition, but it's actually, it's a double phase transition. It turns out it, it, it, it happens, I mean, there's actually two things going on at once at this, at this phase transition, which is, uh, which is very remarkable about it. Okay. So, so, um, a lot of the most important algorithms are, are based on random processes. And so I wanted to, you know, I want to understand random processes and how. So there are data structures that sort of grow this way. Okay. So, so, so Dick Karp, one of the leading experts on, on random randomized algorithms, had his students working, looking at this at Berkeley.

• 1:46:14Speaker 01

  And we heard a rumor that the students had found something interesting happening. That, that, you know, the, the students are, are generating this, are simulating this random evolution of, of graphs. And, and they're taking stat snapshots that, uh, every so often to 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 experiments and only three or four times did they ever happen to see a loop at this point. Uh, I, I, I'm no, more than one component with a loop.

• 1:46:55Speaker 01

  So, so, so they watch until 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, and so, okay, certainly a loop comes along once, but, but now all the loops stay somehow joined to that one. They, they, they, they're never, there never were two guys with loops.

• 1:47:20Lex Fridman?

  Wow, interesting.

• 1:47:22Speaker 01

  In, in these experiments, okay. So anyway, this was almost always, certainly not always.

• 1:47:28Lex Fridman?

  Yeah.

• 1:47:28Speaker 01

  Uh, but, but, but with high, very high probability, this seemed to be true. So, so, so we heard about this rumor at Stanford and we said, hmm, if, 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 haven't ever thought about. So, so let's take a look at it. And so we looked closer and we found out, no, actually it, it's not true. But, but in fact, it, it's almost true. Namely, there's a very short interval of time when it's true. And, and if you don't happen to look at it during that short interval of time, then you miss it.

• 1:48:09Speaker 01

  So the, in other words, there'll be a period where there are two or three components have loops, but they join together pretty soon.

• 1:48:20Lex Fridman?

  Okay.

• 1:48:21Speaker 01

  So, so. So if, if you don't have a, a real fast shutter speed, you're gonna miss, you're gonna miss that instant.

• 1:48:30Lex Fridman?

  So separate loops don't exist for long?

• 1:48:33Speaker 01

  That's, that's it, yeah. You know, I started looking at this to make it quantitative and. Basic problem was to slow down the big bang so that I could watch it happening.

• 1:48:43Lex Fridman?

  Yeah.

• 1:48:44Speaker 01

  I, I think I can explain it actually in, in fairly elementary terms, even, even without writing a formula.

• 1:48:52Lex Fridman?

  Let's try.

• 1:48:52Speaker 01

  Like Hawking would do. And, and, and so, uh, let's, let's watch the evolution and, and at first, these edges are coming along and they're just making things without loops, which we call trees, okay? So then, all of a sudden, a 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 vertices. So if I have a loop, I have like a loop of length five, has five edges and five vertices. Um, or, or I could put a tail on that and that would be another edge, another vertex.

• 1:49:37Lex Fridman?

  It's like a zero, one, two complexity kind of thing.

• 1:49:40Speaker 01

  So, so if the, if the complexity is zero, we have one, one loop, I call it a cycle, or, or I call a cyclic component. So, so a cyclic component looks like a, a, a wheel to which you attach fibers, or trees. They go branching, but there's no more loops. There's only one loop and, and everything else feeds into that loop, okay? And that has complexity zero. But, but a tree itself has complexity minus one because it has, uh, you know, it, like, like, like it might have ten vertices and nine edges to tie the, tie them together. So nine minus ten is minus one. So, so, so complexity minus one is a tree.

• 1:50:26Speaker 01

  It's got to be connected. That's what I mean by a component. It's got to be connected. So, so, so if, if I have ten things connected, I have to have nine edges.

• 1:50:36Lex Fridman?

  Can you clarify why when complexity goes, uh, it can go above zero? I'm a little confused why.

• 1:50:43Speaker 01

  Yes, right. So the complexity plus one is the number of loops. So if complexity is zero, I have one loop. If, if, if complexity is one, that means I have one more edge than I have vertex. So I might have like 11 edges and 10 vertices. So it turns, we call that a bicycle because it, it, it's got two loops and it's got to have two loops in it.

• 1:51:09Lex Fridman?

  Well, but why can't it be trees just going off of the loop?

• 1:51:15Speaker 01

  That I would need more edges than I.

• 1:51:19Lex Fridman?

  Oh, right. Right. Okay, I got.

• 1:51:22Speaker 01

  So, so every time I get another loop, I get another excess of edges over vertices.

• 1:51:26Lex Fridman?

  I got you.

• 1:51:27Speaker 01

  Okay. So in other words, uh, we start out and after I have one loop, I have one component that has a cycle in it. Now, the, the next step, uh, according to the rumor would be that at the next step, I would have a bicycle. In, 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 two, you know, two, two different cycles. All right. Um, and I worked out the probability was something like five out of 24.

• 1:52:06Lex Fridman?

  That's pretty high.

• 1:52:08Speaker 01

  It was substantial.

• 1:52:10Lex Fridman?

  Yeah.

• 1:52:11Speaker 01

  Uh, but still, uh, soon they're going to merge together almost. Okay. So.

• 1:52:17Lex Fridman?

  That's so cool.

• 1:52:18Speaker 01

  But, but then it splits again after you have either, either two or one, one. The next step is you either have three or you have two, one, or you have one, one, one. Okay. And so I worked out the probability for, 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, five 24s. And I stayed up all night and about 3:00 AM, I, I had the numbers computed and I looked at them and here were, the denominator was something like.

• 1:52:58Speaker 01

  Twenty two, three, zero, two, three.

• 1:53:01Lex Fridman?

  Mm hmm.

• 1:53:02Speaker 01

  So, so, so the probability was something over two, three, oh, two, three.

• 1:53:06Lex Fridman?

  I don't know how you work that out, but.

• 1:53:08Speaker 01

  I had a formula of that, you know, I could calculate the probability.

• 1:53:11Lex Fridman?

  Yeah.

• 1:53:11Speaker 01

  And, and I could find the limiting probability, it then goes to infinity and, and it, and it turned out to be this number, but the denominator was two, three, and I, and I looked at the denominator. I said, wait a minute. This number factors because one thousand and one is equal to seven times eleven times thirteen. I had learned that in my first computer program. So, so, so, so, so twenty three, oh, twenty three.

• 1:53:37Lex Fridman?

  Yeah.

• 1:53:37Speaker 01

  Is seven times eleven times thirteen times twenty three.

• 1:53:42Lex Fridman?

  Mm hmm.

• 1:53:43Speaker 01

  That's not a random number. There has to be a reason why those small primes appear in the denominator.

• 1:53:50Lex Fridman?

  Mm hmm.

• 1:53:50Speaker 01

  But my, so all of a sudden that suggested, um, another way of looking at the problem where small prime factors would, uh, would occur.

• 1:54:01Lex Fridman?

  Mm hmm.

• 1:54:01Speaker 01

  So.

• 1:54:02Lex Fridman?

  So what would that be?

• 1:54:03Speaker 01

  So that said, oh yeah, and let me take the logarithm of this formula and, and sure enough, this is going to simplify and, and it happened. So, and, and I wouldn't have noticed it except for this factorization. Okay. So I go to bed and I, I say, oh, okay, this is, 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, they're trying to sell him on donating money to, uh, for, for a new computer science building.

• 1:54:35Lex Fridman?

  Sure.

• 1:54:36Speaker 01

  And, and, and I, I said, so they gave me an appointment to talk to Bill and I, and I wrote down on the blackboard this, this evolutionary diagram, you know, going from one to two, five, twenty fourths and all this business.

• 1:54:49Lex Fridman?

  Yeah.

• 1:54:50Speaker 01

  And, and I wrote it down. And anyway, at the end of the day, the, uh, he, he was discussing people with the, with the, uh, uh, development office and, and he said, boy, I was really impressed with the, what Professor Knuth said, uh, uh, about this giant component. And, and, and so, uh, you know, I, I, I love this story because it shows that theoretical computer science is, is really worthwhile, you know.

• 1:55:16Lex Fridman?

  Does Bill, have you ever talked to Bill Gates about it, uh, since then?

• 1:55:21Speaker 01

  Yeah.

• 1:55:22Lex Fridman?

  That's a cool, that's a cool little moment in history.

• 1:55:24Speaker 01

  Yeah, but, but, but anyway, he happened to visit on, on exactly the day after I had, I had found this pattern and, and that allowed me to, to crack the problem. So, you know, so that I, I could develop the theory, uh, the, the theory some more and, and understand what's happening in the big, but, uh, because I could, I could now write down explicit formulas for stuff. And, and so it would, you know, you would work not only the first few steps, but also the, study the whole process. And, and I worked further and further and I, with, with two authors, co-authors, and we finally figured out that the probability that the rumor

• 1:56:07Speaker 01

  was true. In other words, look at the evolution of, of, of a random graph going from zero, zero to, to complete and say, what's the probability that at every point in time, there was only one component with a cycle? We started with this rumor saying there's only one cycle, there's only one component with a cycle and, uh,

• 1:56:30Lex Fridman?

  So the rumor was, it's a hundred percent.

• 1:56:33Speaker 01

  Rumor was that was a hundred percent. It turned out the actual numbers is like eighty seven percent. I, I don't, I, I should remember the number, but I don't, but I don't have it with me. But, but anyway, but, but the, but the number, it, it turned out to be like twelve over pi squared or, or, or, sorry, eight over pi. Anyway, it, it, it was a nice, it related to pi.

• 1:56:57Lex Fridman?

  Yeah.

• 1:56:57Speaker 01

  Um, and we could never have done that with, but, so that's the hardest problem I ever solved in my life was to prove that this probability is.

• 1:57:06Lex Fridman?

  So it was proven. The probability was proven.

• 1:57:10Speaker 01

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

• 1:57:22Lex Fridman?

  That's super cool. I, what was the connection to physics that you mentioned?

• 1:57:26Speaker 01

  Well, Bayesian statistics is, is a study of how molecules, uh, uh, bond together, uh, uh, without geometry, without this.

• 1:57:41Lex 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?

• 1:57:56Speaker 01

  Okay, well, the word open source didn't exist at that time, but I didn't want proprietary rights over it. Because I saw how proprietary rights were holding things back. In the late 50s, people at IBM developed a language called Fortran. They could have kept it proprietary. They could have said, only IBM can use this language. Everybody else has to, but they didn't. They said, anybody who can write, who can translate Fortran into the language of their machines is allowed to make Fortran compilers, too.

• 1:58:39Speaker 01

  On the other hand, in the typography 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 is invented a year later. But printing machines, they have to expect to amortize the cost over 20, 30 years.

• 1:59:11Lex Fridman?

  So you didn't want that for tech?

• 1:59:13Speaker 01

  I didn't need the income.

• 1:59:17Speaker 01

  I already had a good job. And my books were,

• 1:59:29Speaker 01

  people were buying enough books that it would bring me plenty of supplemental income for everything my kids needed for education, 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 you get over the threshold, then you start thinking about philanthropy or else you're trying to take it with you. But, 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

• 2:00:12Speaker 01

  the advantage of, of, of making it open for everybody.

• 2:00:17Lex Fridman?

  Do you think most software should be open?

• 2:00:20Speaker 01

  So I think that people should charge for non-trivial software, but not for trivial software.

• 2:00:27Lex Fridman?

  Yeah, you give an example of, I think, Adobe Photoshop versus GIMP on Linux as Photoshop has value, which...

• 2:00:37Speaker 01

  So it's definitely worth paying, paying for all this stuff. I mean, and, I mean, well, they keep adding, adding stuff that's, that my wife and I don't care about, but somebody obviously does. But I mean, but they have built in a fantastic, uh, undo feature, for example, in Photoshop, where, where you, you, you can go through a sequence of a thousand complicated steps on graphics and it can take you back anywhere in that sequence.

• 2:01:13Lex Fridman?

  Yeah.

• 2:01:13Speaker 01

  With really beautiful algorithm. I mean, yeah, it's, it's...

• 2:01:18Lex Fridman?

  Oh, that's interesting. I didn't think about what algorithm. It must be some kind of efficient representation.

• 2:01:23Speaker 01

  It's really, yeah, no, I mean, there's a lot of really subtle Nobel Prize class creation of intellectual property in, in there. And...

• 2:01:38Speaker 01

  And with patents, you get a limited time to,

• 2:01:43Speaker 01

  I mean, eventually, the idea of patents is that you publish so that it's not a trade secret.

• 2:01:51Lex Fridman?

  That said, you've said that I currently use Ubuntu Linux on a standalone laptop. It has no internet connection. I occasionally carry flash memory drives between the machine and the Macs that I use for network surfing and graphics. But I trust my family jewels only to Linux. Why do you love Linux?

• 2:02:15Speaker 01

  The version of Linux that I use is stable.

• 2:02:20Speaker 01

  Actually, I'm gonna have to upgrade one of these days, but.

• 2:02:23Lex Fridman?

  To a newer version of Ubuntu?

• 2:02:25Speaker 01

  Yeah, I'll stick with Ubuntu, but right now I'm running something that doesn't support a lot of the new software. The last stable, I don't remember the number, like 14. Anyway, it's quite, and I'm gonna get a new computer.

• 2:02:47Speaker 01

  I'm getting new solid state memory instead of a hard disk.

• 2:02:51Lex Fridman?

  Yeah, the basics. Well, let me ask you.

• 2:02:56Lex Fridman?

  Sticking on the topic of tech.

• 2:03:01Lex Fridman?

  When thinking about beautiful typography, what is your favorite letter, number, or symbol?

• 2:03:09Lex Fridman?

  I know, I know, ridiculous question, but is there some?

• 2:03:20Speaker 01

  Look at the last page.

• 2:03:25Speaker 01

  The very end of the index.

• 2:03:29Lex Fridman?

  What is that?

• 2:03:31Speaker 01

  There's a book by Dr. Seuss called On Beyond Zebra, and he gave a name to that.

• 2:03:37Lex Fridman?

  Did you say Dr. Seuss gave a name to that?

• 2:03:39Speaker 01

  Dr. Seuss, this is S.E.U.S.S. He wrote children's books in the 50s, 40s and 50s.

• 2:03:49Lex Fridman?

  Wait, you're talking about Cat in the Hat?

• 2:03:51Speaker 01

  Cat in the Hat, yeah. That's it, yeah.

• 2:03:54Lex Fridman?

  I like how you hit the spot there.

• 2:03:55Speaker 01

  On Beyond Zebra, did it get to Soviet Union?

• 2:04:04Lex Fridman?

  Yeah, Dr. Seuss did not come to the Soviet Union, but since you... Oh, actually, I think he did actually a little bit when we're...

• 2:04:15Lex Fridman?

  That was a book, his, maybe Cat in the Hat or Green Eggs and Ham, I think was used to learn English.

• 2:04:25Speaker 01

  Oh, okay.

• 2:04:26Lex Fridman?

  So I think it made it in that way.

• 2:04:27Speaker 01

  Well, my... Okay, I didn't like those as much as Bartholomew Cubbins, but I used to know Bartholomew Cubbins by heart when I was young.

• 2:04:39Lex Fridman?

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

• 2:04:43Speaker 01

  He has a name for it at the end of his book On Beyond Zebra.

• 2:04:47Lex Fridman?

  Who made it?

• 2:04:48Speaker 01

  He did.

• 2:04:49Lex Fridman?

  He did. So there's, it looks like a bunch of vines. Is that symbol exist in fact?

• 2:04:58Speaker 01

  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 dozens and dozens of pianos all playing together at the same time. But all the scenery is sort of based on the kind of artwork that was in his books and the fantasy, you know,

• 2:05:26Speaker 01

  based of Seuss land or something. And I saw the movie only once or twice, but it's quite, I'd like to see it again.

• 2:05:37Lex Fridman?

  That's that's really fascinating that you gave him. They gave him a shout out here. Okay. Is there some elegant basic symbol that you're attracted to some? Give something that gives you pleasure, something you use a lot?

• 2:05:53Lex Fridman?

  Pi?

• 2:05:54Speaker 01

  Pi, of course. I try to use pi

• 2:05:59Speaker 01

  as often as I can when I need a random example.

• 2:06:05Speaker 01

  Because it doesn't have any

• 2:06:08Speaker 01

  known characters. So for for instance, I don't have here to show you, but do you know the

• 2:06:18Speaker 01

  the game called Masyu? M A S Y U?

• 2:06:22Lex Fridman?

  No.

• 2:06:22Speaker 01

  It's it. It's a great recreation. I mean, pseudoco is easier to understand, but Masyu is it is more addictive. You have black and white stones like a like on a go board. And you have to draw a path that goes straight through a white stone and makes a right angle turn at the black stone. And it turns out to be really really nice puzzle because it doesn't involve numbers. But it's visual, but it's 3D pleasant to to play with. So so I wanted to

• 2:07:02Speaker 01

  use it as example in art of computer programming and I have I have exercise on how to design cool Masyu puzzles. You can find it on Wikipedia, certainly. As an example, M A S Y U. And and so I and so I decided I would take pi, the actual image of it. And it had pixels. And I would put a stone wherever it belongs in the letter pi, in the Greek letter pi. And 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 Masyu puzzle.

• 2:07:44Speaker 01

  That was a good test case for my algorithm on how to design Matri puzzles, because I insisted in advance that the stones had to be placed in exactly the positions that make the letter pi, make a huge letter.

• 2:07:58Lex Fridman?

  Okay.

• 2:07:59Speaker 01

  All right.

• 2:08:00Lex Fridman?

  That's cool.

• 2:08:00Speaker 01

  And, and so, you know, and it turned out there was a, a, a unique way to do that. Um, and so, so pi is a source of, of examples where I can, where I can prove that I'm starting with something that isn't canned.

• 2:08:18Lex Fridman?

  Yeah.

• 2:08:18Speaker 01

  Um, and, and most, most recently, I was writing about something called graceful graphs. Um, graceful graphs is the following. You have a graph that has m edges to it. All right. And you attach numbers to every vertex in the following way. So every time you have an edge between vertices, you, you take the difference between those numbers. And, and that difference is, is got to be, it'll tell you what edge it is. So, so the one edge, two numbers will be one apart. There'll be another edge where the numbers are two apart. And so, uh, it's a great computer problem.

• 2:09:02Speaker 01

  Can you find a graceful way to label a graph?

• 2:09:05Lex Fridman?

  Mm hmm.

• 2:09:06Speaker 01

  So I started with a, so I started with a graph that I use for an organic graph, not, not a mathematically symmetric graph or anything. And I take this, I take the 49 states of the United States. Uh, the, uh, the edges go from one state to a next state. So, 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, 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?

• 2:09:51Speaker 01

  Each state gets a number. And then if California is number thirty and Oregon is number eleven, that edge is going to be number nineteen. The difference between those, okay? So is there a way to do this for all the states? And so I was thinking of having a contest for people to get as graceful as they could. But my friend Tom Rukiki actually solved the problem by proving that, I mean, I was able to get it done within seven or something like that. He was able to get a perfect solution.

• 2:10:29Lex Fridman?

  The actual solution or to prove that a solution exists?

• 2:10:32Speaker 01

  More precisely, I had figured a way to put labels on so that all the edges were labeled somewhere between one and one hundred and seventeen. But there were some gaps in there. Because I should really have gone from one to one hundred and five or whatever the number is. So I gave myself too much, you know, a lot of slack. He did it without any slack whatsoever, a perfect graceful labeling. 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 an afternoon.

• 2:11:10Lex Fridman?

  He, sorry, he gave the algorithm or for this particular?

• 2:11:13Speaker 01

  For the United States.

• 2:11:15Lex Fridman?

  For the United States.

• 2:11:16Speaker 01

  This problem is incredibly hard. I mean.

• 2:11:19Lex Fridman?

  For the general.

• 2:11:20Speaker 01

  Generally.

• 2:11:21Lex Fridman?

  It's like coloring.

• 2:11:23Speaker 01

  But it was very lucky that it worked for the United States.

• 2:11:25Lex Fridman?

  Sure.

• 2:11:26Speaker 01

  I think, but the theory is still very incomplete. But anyway, then Tom came back a couple of days later and he had been able to not only find a graceful labeling, but the label of Washington was thirty-one. The label of Idaho was forty-one, following the digits of pi.

• 2:11:50Lex Fridman?

  Yeah.

• 2:11:50Speaker 01

  Going across the top edge of the United States, he has the digits of pi perfectly.

• 2:11:56Lex Fridman?

  Did he do it on purpose?

• 2:11:57Speaker 01

  He was able to still get a graceful labeling with that.

• 2:12:00Lex Fridman?

  With that.

• 2:12:01Speaker 01

  With that extra thing.

• 2:12:02Lex Fridman?

  What? Wow. Wow.

• 2:12:06Speaker 01

  And it's a miracle, okay? But I like to use pi in my book, you see? And this is the.

• 2:12:17Lex Fridman?

  All roads lead to pie.

• 2:12:19Speaker 01

  Yeah.

• 2:12:19Lex Fridman?

  Somehow, somehow often hidden in the middle of like the most difficult problems. Can I ask you about productivity?

• 2:12:31Speaker 01

  Productivity.

• 2:12:32Lex Fridman?

  Yeah, you said that, quote, "My scheduling principle is to do the thing I hate most on my to-do list. By week's end, I'm very happy." Can you explain this process to a productive life?

• 2:12:48Speaker 01

  Oh, I see. Well, but all the time I'm working on what I want, what I don't want to do. But still, I'm glad to have all those unpleasant tasks finished.

• 2:12:57Lex Fridman?

  Yes. Is that something you would advise to others?

• 2:13:00Speaker 01

  Well, I, yeah, I, I, I don't know how to say it. During the pandemic, I feel my productivity actually went down by half. Because I have to, 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 reread what I've written and edit and fix it. So, so everything takes a long, longer when I'm, when I'm communicating by, by text messages. Instead of just, you know, together with somebody in a room.

• 2:13:41Speaker 01

  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 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. You know, we're just, instead of saying, I'm going to do this first and do this first, just, you know.

• 2:14:17Lex Fridman?

  Just do it.

• 2:14:17Speaker 01

  Oh, yeah, pick this up, you know.

• 2:14:19Lex Fridman?

  But you're 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 the one you want to do least.

• 2:14:30Speaker 01

  Right, the one I haven't got any good reason. I I I that I'll never be able to do any better than than I am now. Uh, I mean, there are some things that that I know. If I do something else first, then I'll be able to do that one better.

• 2:14:47Lex Fridman?

  Yeah.

• 2:14:48Speaker 01

  But but but there's some that are going to be harder because, you know, I I I I've forgotten some of the groundwork that went into it or something like that. So so I just finished a pretty tough part of the book and uh, and so and so now I'm, you know, doing the parts that are more fun. But but but the the other thing is, as I'm writing the book, of course, I want

• 2:15:14Speaker 01

  the reader to think that I'm happy all the time I'm writing the book. I I I'm, you know, that it's upbeat. I I I can have humor. I can, you know, I can, I can say this is cool, you know, well, and this. Uh, I have to, I have to disguise the fact that it it was painful in any way to come up with.

• 2:15:33Lex Fridman?

  The road to that excitement is painful. Yeah, it's laden with pain. Okay, is is there, um, you've given some advice to people before. But can you, um, can you?

• 2:15:45Speaker 01

  You give me too too much credit, but anyway, this is my, this is my turn to just to say things that that that I believe. But but I I want to preface it by saying, um, I also believe that other people do a lot of these things much better than I do. So I can only tell you my my side of it.

• 2:16:07Lex Fridman?

  So

• 2:16:10Lex Fridman?

  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 they can be proud of, how to have a successful career, how to have a successful life?

• 2:16:31Speaker 01

  It's always the same as I've said before, I guess,

• 2:16:35Speaker 01

  not to do something 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.

• 2:16:49Lex Fridman?

  How do you know you're called to do something?

• 2:16:53Speaker 01

  You try it and it works, 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 could do this if I worked a little bit harder. But you try something else and you say, well, I have really no intuition for this. And it looks like, you know, it looks like it doesn't have my name on it.

• 2:17:22Lex 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?

• 2:17:31Speaker 01

  Yeah, I probably overreact another way. When I see everybody else going some way, I probably, I probably say, hmm, too much competition.

• 2:17:45Speaker 01

  But mostly, 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 bored. It makes me very sad when I see kids talking to each other and they say,

• 2:18:10Speaker 01

  that was boring. And to me, a person should feel upset if he had to admit that he wasn't able to find something interesting.

• 2:18:23Lex Fridman?

  Yeah. So, you know.

• 2:18:26Speaker 01

  It's a skill. They're saying, I haven't learned how to enjoy life. I have to have somebody entertain me instead of.

• 2:18:35Lex Fridman?

  Right. That's really interesting. It is a skill. David Foster Wallace, I really like the thing he says about this, which is the key to life is to be unborable. 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.

• 2:19:00Lex Fridman?

  I don't believe it's because it's boring. It's because you haven't developed.

• 2:19:05Speaker 01

  I haven't learned how to.

• 2:19:06Lex Fridman?

  How to find the beauty in it, how to find the fun in it. That's a really, really good point.

• 2:19:12Speaker 01

  You know, sometimes it's more difficult than others to, I have to do this. I mean, during the COVID, lots of days when I, when I never saw another human being, but, uh, but, uh, I, I, I still find other ways to.

• 2:19:30Lex Fridman?

  It, it still was a pretty fun time.

• 2:19:32Speaker 01

  Yeah. Oh, yeah. I, I came earlier. I, I came a few minutes early today and I walked around Foster City. I didn't want, you know, I didn't know what was going on in Foster City. I saw beautiful, like some beautiful flowers at the nursery at Home Depot a few blocks away.

• 2:19:49Lex Fridman?

  Yeah.

• 2:19:52Lex Fridman?

  Life is amazing. It's full of amazing things like this. Yeah. I just, sometimes I'll, I'll sit there and just stare at a tree. Nature is beautiful. Uh, let me ask you the big ridiculous question. I don't think I asked you last time. I'll have to ask this time in case you have a good answer. What is the meaning of life?

• 2:20:12Lex Fridman?

  Our existence here on earth, the whole thing. Do you have?

• 2:20:20Lex Fridman?

  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.

• 2:20:30Lex Fridman?

  Because they're, they're surely, surely, Don Knuth, there must be an answer.

• 2:20:34Speaker 01

  What is the answer? Is it 42 or?

• 2:20:37Lex Fridman?

  Yes. Well, I don't think it's in numerical. That's, that's the, yes, the.

• 2:20:40Speaker 01

  That was, that was in, in Zen and, okay, but, all right. So, so anyway, um,

• 2:20:47Speaker 01

  it, it's only for me and, but I, but, but I personally think of my belief that, that God exists, although I have no idea

• 2:21:01Speaker 01

  what that means, but I believe that there is.

• 2:21:06Speaker 01

  Some something beyond human capabilities.

• 2:21:14Speaker 01

  And it might be, it might be some AI. But but whatever it is, but whatever, but I do believe that that there is 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.

• 2:21:46Lex Fridman?

  So you think you can have occasional glimpses of that being?

• 2:21:50Speaker 01

  I strive for that. Not that I ever think I'm going to get close to it, but but it's not. It's not for me. It's it's saying, what should I do that that being wants me to do? That's that's, you know, I I'm trying to ask

• 2:22:13Speaker 01

  what that, I mean, does that being want me to be talking to Lex Fridman right now? You know, and I said, yes, okay, but

• 2:22:22Lex Fridman?

  Thank you.

• 2:22:24Speaker 01

  Well, thank you.

• 2:22:26Lex Fridman?

  But

• 2:22:28Speaker 01

  what I'm trying to say is, I'm not trying to say what of all the strategies I could choose or something, which one I I try to do it not not strategically, but I try to

• 2:22:43Speaker 01

  to imagine that I'm following somebody's wishes.

• 2:22:47Lex Fridman?

  Even though you're not smart enough to

• 2:22:51Speaker 01

  To know what they are.

• 2:22:52Lex Fridman?

  Yeah. That funny little dance.

• 2:22:54Speaker 01

  Well, I I mean, this AI or whatever is it probably is is smart enough to help to give me clues.

• 2:23:05Lex Fridman?

  And to make the whole journey from clue to clue, a fun one.

• 2:23:10Speaker 01

  Yeah, I mean, it's it's as so many people have said, it's the journey, not the destination. And people live, live through crises, help each other. Always think things come up. History repeats itself.

• 2:23:27Speaker 01

  You try to say in the world today. Is there any government that's working? I, I, I read history, I, I know that things were.

• 2:23:38Lex Fridman?

  They, they, they were, they were, there were a lot worse in many ways.

• 2:23:43Speaker 01

  There's a lot of bad things all the time. And, and I read about, you know, I, I look at, at things and people had good ideas and they were working on great projects and then I know that it, that it didn't succeed though in the end. Uh, but, but the new insight I've gotten actually in that way was, I, I was reading, uh, what, what book was I reading recently? It was, it was by Ken Follett and it was called The Man From St. Petersburg. But it, but, but it was talking about the prequel to World War One. And, and Winston Churchill, according to this book, uh, sees that, that Germany has been spending all its gold reserves, uh, building up a huge military.

• 2:24:28Speaker 01

  And there's no question that if, if Germany would attack England, that England would be wiped out.

• 2:24:36Speaker 01

  So he wants Russia to help, uh, to attack Germany from the other side because Germany doesn't have enough of an army to,

• 2:24:45Speaker 01

  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

• 2:25:09Speaker 01

  any alliance between England and Russia because that would mean that a thousand and thousand of people of Russia would, would, would be killed that wouldn't be otherwise killed. All right, and so his, his life's goal is to assassinate a, a Russian prince who's visiting England because that will make, will mean the Tsar will not form the alliance, all right? So we have this.

• 2:25:38Speaker 01

  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 peace? 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 these questions are too hard, probably for any human being, but certainly for me.

• 2:26:12Lex 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, in the great leaders to arise and help build a better world. I mean, that's the hope of democracy.

• 2:26:42Speaker 01

  Yeah, Ben, let's hope that we can enhance their abilities with, with algorithms.

• 2:26:54Lex Fridman?

  Well put, Don. It's such a huge honor. You've been an inspiration to me and to millions for such a long time. 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 Knuth 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.