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

00:00:00.000 | The following is a conversation with Donald Knuth, his second time on this podcast.

00:00:04.960 | Don is a legendary computer scientist, Turing Award winner, father of algorithm analysis,

00:00:12.160 | author of the art of computer programming, creator of tech that led to latech, and one of the kindest

00:00:20.320 | and most fascinating human beings I've ever got a chance to talk to. I wrote him a letter a long

00:00:26.320 | time ago. He responded, and the rest, as they say, is history. We've interacted many times since then,

00:00:33.600 | and every time has been joyful and inspiring. To support this podcast, please check out our

00:00:39.200 | sponsors in the description. This is the Lex Friedman Podcast, and here is my conversation

00:00:45.600 | with Donald Knuth. Your first large-scale program, you wrote it in IBM 650 Assembler in the summer

00:00:53.520 | of 1957? I wrote it in decimal machine language. I didn't know about Assembler until a year later.

00:01:00.000 | But the year, 1957, and the program is Tic-Tac-Toe. Yeah, and I learned about Assembler later that

00:01:07.040 | summer. I probably did. In 1957, hardly anybody had heard of Assembler. You looked at the user

00:01:11.920 | manuals. How would you write a program for this machine? It would say 69, which meant load the

00:01:21.520 | distributor, and then you would give the address of the number you wanted to load into the distributor.

00:01:26.560 | Yesterday, my friend Doug Spicer at the Computer History Museum sent me a link to something that

00:01:35.040 | just went on YouTube. It was IBM's progress report from 1956, which is very contemporary with 1957.

00:01:45.120 | And in 1956, IBM had donated to Stanford University an IBM 650, one of the first ones,

00:01:52.720 | when they showed a picture of the assembly line for IBM 650s. And they said, "This is number 500

00:01:58.880 | or something coming off the assembly line." And I had never seen so many IBM 650s. I did in this

00:02:05.840 | movie that's on YouTube now. And it showed the picture from Stanford. They said, "Look, we

00:02:18.480 | donated one of these to Stanford, one to MIT," and they mentioned one other college. And in December

00:02:25.600 | of '56, they donated to my university, K-STEC. But anyway, they showed a picture then of a class

00:02:34.080 | session where a guy was teaching programming. And on the blackboard, it said 69, 8,000. I mean,

00:02:41.840 | he was teaching them how to write code for this IBM 650, which was in decimal numbers.

00:02:51.520 | So the instructions were 10 decimal digits. You had two digits that said what to do, four digits

00:03:00.640 | to say what to do it to, and four more digits to say where to get your next instruction.

00:03:07.360 | And there's a manual that describes what each of the numbers mean.

00:03:11.200 | And the manual was actually... If the manual had been well-written, I probably never would

00:03:16.160 | have gone into computer science, but it was so badly written, I figured that I must have a talent

00:03:21.280 | for it because I'm only a freshman and I could write a better manual. And-

00:03:27.200 | That's what you did.

00:03:28.720 | And so I started working at the computer center and wrote some manuals then. But yeah, but this

00:03:39.600 | was the way we did it. And my first program then was June of 1957.

00:03:46.160 | The Tic-Tac-Toe.

00:03:47.600 | No, that was the second program. The first program was factoring a number.

00:03:55.200 | Okay.

00:03:56.000 | So you dial a number on the switches. I mean, you sat at this big mainframe

00:04:03.360 | and you turn the dials, set a number, and then it would punch out the factors of that number on

00:04:12.640 | cards.

00:04:13.360 | So that's the input is the number?

00:04:15.440 | The input was, yeah, the input was a number, a 10-digit number, and the output was its factors.

00:04:25.360 | And I wrote that program. I still have a copy of it somewhere.

00:04:32.000 | How many lines of code? Do you remember?

00:04:36.080 | Well, yeah, it started out as about 20, but then I kept having to debug it. And I discovered

00:04:42.800 | debugging, of course, when I wrote my first program.

00:04:45.280 | What does debugging look like on a program with just all numbers?

00:04:50.800 | Well, you sit there and you... I don't remember how I got it into the machine,

00:04:54.640 | but I think there was a way to punch it on cards. So each instruction would be one card.

00:05:00.640 | Maybe I could get seven instructions on a card, eight instructions, I don't know. But anyway,

00:05:04.880 | so I'm sitting there at the console of the machine. I mean, I'm doing this at night when

00:05:09.040 | nobody else is around.

00:05:10.240 | Of course.

00:05:10.740 | And so you have one set of switches where you dial the number I'm inputting, but there's another

00:05:17.440 | switch that says, "Okay, now execute one instruction and show me what you did." Or there were another

00:05:26.320 | four switches I'd say, "Stop if you get to that instruction." So I could say, "Now go until you

00:05:33.120 | get there again and watch." Okay, so I could watch. It would take that number and it would

00:05:39.200 | divide it by two. And if there's no remainder, then okay, two is a factor. So then I work on...

00:05:46.800 | But if not divisible by two, divide by three. Okay, keep trying until you know you're at the end.

00:05:54.960 | And you would find a bug if you were just surprised that something weird happened?

00:06:01.600 | Well, certainly. I mean, first of all, I might have

00:06:05.120 | tried to divide by one instead of two. You're off by one error, as people make all the time.

00:06:12.000 | But maybe I go to the wrong instruction. Maybe I left something in a register that I shouldn't have

00:06:19.760 | done. But the first bugs were pretty... Probably on the first night, I was able to get the factors

00:06:27.360 | of 30 as equal to two, three, and five. Okay? Sorry to interrupt. So you're sitting there

00:06:34.960 | late at night. It feels like you spent many years late at night working on a computer.

00:06:42.480 | Oh, yeah. So what's that like? So most of the world is sleeping,

00:06:46.480 | and you have to be there at night because that's when you get access to the computer.

00:06:51.520 | Between my freshman and sophomore year, I didn't need sleep. I used to do all nighters. When I was

00:06:56.720 | in high school, I used to do the whole student newspaper every Monday night. I would just stay

00:07:05.520 | up all night, and it would be done on Tuesday morning. I didn't get ulcers and stuff like that

00:07:14.160 | until later. I don't know if you know Rodney Brooks.

00:07:19.760 | Rod Brooks, of course. Yeah. He told me a story.

00:07:26.080 | He really looked up to you. He was actually afraid of you.

00:07:28.400 | Well, vice versa, I must say.

00:07:31.280 | But he tells a story when you were working on tech, that they screwed up something with a

00:07:37.760 | machine. I think this might have been MIT. I don't know. And you were waiting for them to fix the

00:07:43.280 | machine so you can get back to work late at night. Oh, that happened all the time.

00:07:49.360 | He was really intimidated. He's like, "Dr. Knuth is not happy with this."

00:07:54.000 | That's interesting. But no, no. The machine at Danford AI Lab was down an awful lot because

00:08:03.920 | they had many talented programmers changing the operating system every day.

00:08:09.600 | And so the operating system was getting better every day, but it was also crashing. So I wrote

00:08:17.760 | almost the entire manual for tech during downtime of that machine. But that's another story.

00:08:24.400 | Well, he was saying it's a hardware problem. They tried to fix it and they reinserted something and

00:08:31.040 | smoke was everywhere. Oh, wow.

00:08:33.040 | Because he was hurt.

00:08:33.840 | Well, that didn't happen as often as the operating system.

00:08:35.840 | Anyway, it's a funny story because you're saying there's this tall Don Knuth that I look up to and

00:08:45.600 | there was pressure to fix the computer. It's funny. The kind of things we remember that stick

00:08:53.520 | in our memory.

00:08:54.080 | Well, okay. Yeah. Well, I could tell you a bunch of Rodbrook stories too, but let's go back to the

00:09:00.800 | 650. So I'm debugging my first program and I had more bugs in it than number of lines of code. I

00:09:13.920 | mean, the number of lines of code kept growing. And let me explain. So I had to punch the answers

00:09:18.800 | on cards. So suppose I'm factoring the number 30, then I got to put two somewhere on the card. I

00:09:29.520 | got to put a three somewhere on the card. I got to put a five somewhere on the card. And you know

00:09:34.080 | what? It was my first program. I probably screwed up and it fell off the edge of the card or

00:09:41.120 | something like that. But I didn't realize that there are some tensioned numbers that have more

00:09:48.000 | than eight factors. And the card has only 80 columns. And so I need 10 columns for every

00:09:54.480 | factor. So my first program didn't take account for the fact that I would have to punch more than

00:09:59.680 | one card. My first program just lined the stuff up in memory and then I punched the card. So by

00:10:06.640 | the time I finished, I had to deal with lots of things. Also, if you put a large prime number in

00:10:16.560 | there, my program might have sat there for 10 minutes. The 650 was pretty slow. And so it would

00:10:22.320 | sit there spinning its wheels and you wouldn't know if it was in a loop or whatever. You said

00:10:26.240 | 10 digit is the input? 10 digits, yeah. So I think the largest is sort of 9999999997 or something

00:10:34.000 | like that. That would take me a while for that first one. Anyway, that was my first program.

00:10:40.960 | Well, what was your goal with that program? Was there something you were hoping to find a large

00:10:46.560 | prime maybe or the opposite? No, my goal was to see the lights flashing and

00:10:51.520 | understand how this magical machine would be able to do something that took so long by hand.

00:10:58.480 | So what was your second program?

00:10:59.920 | My second program was a converted number from binary to decimal or something like that. It was

00:11:09.040 | much simpler. It didn't have that many bugs in it. My third program was Tic-Tac-Toe.

00:11:14.400 | Yeah. And it had some machines. So the Tic-Tac-Toe program is interesting on many levels,

00:11:20.560 | but one of them is that it had some, you can call machine learning in it.

00:11:25.520 | That's, yeah, that's right. I don't know how long it's going to be before the name of our field has

00:11:34.240 | changed from computer science to machine learning. But anyway, it was my first experience with

00:11:42.560 | machine learning. Okay, so here we had... Yeah. How does the program... Well, first of all,

00:11:46.880 | what is the problem you were solving? What is Tic-Tac-Toe? What are we talking about? And then

00:11:55.120 | how is it designed? Right. So you've got a three by three grid and each can be in three states. It

00:12:04.160 | can be empty or it can have an X or an O. Yeah. All right. So three to the ninth is a... Well,

00:12:12.080 | what is... How big is it? I should know. But it's 81 times 81 times three. So

00:12:21.680 | anyway, eight is like two to the third. So that would be like two to the sixth.

00:12:31.120 | But that'd be 64. Then you have to... Anyway. I love how you're doing the calculation.

00:12:38.480 | Anyway, the three comes from the fact that it's either empty, an X or an O. Right. And the 650

00:12:49.360 | was a machine that had only 2,010 digit words. You go from 0,0,0,0 to 1,9,9,9 and that's it.

00:13:02.160 | And each word, you have a 10 digit number. So that's not many bits. I mean, I got to have...

00:13:10.320 | In order to have a memory of every position I've seen, I need three to the ninth bits.

00:13:18.480 | Okay. But it was a decimal machine too. It didn't have bits. But it did have strange instruction

00:13:25.680 | where if you had a 10 digit number, but all the digits were either eight or nine,

00:13:30.480 | you'd be 89988 or something like that. You could make a test whether it was eight or nine. That

00:13:40.080 | was one of the strange things IBM engineers put into the machine. I have no idea why.

00:13:45.600 | Well, hardly ever used. But anyway, I needed one digit for every position I'd seen. Zero meant it

00:13:54.880 | was a bad position. Nine meant it was a good position. I think I started out at five or six.

00:14:01.200 | But if you win a game, then you increase the value of that position for you, but you decrease it

00:14:10.720 | for your opponent. But I had that much total memory for every possible position was one digit.

00:14:21.440 | And I had a total of 20,000 digits, which had to also include my program and all the logic and

00:14:28.800 | everything, including how to ask the user what the moves are and things like this. Okay. So I think I

00:14:36.480 | had to work it out. Every position in tic-tac-toe is equivalent to roughly eight others because you

00:14:44.080 | can rotate the board, which gives you a factor of four, and you can also flip it over.

00:14:50.480 | And that's another factor too. So I might have needed only three to the ninth over eight positions

00:14:58.960 | plus a little bit. But anyway, that was a part of the program to squeeze it into this tiny...

00:15:06.800 | So you tried to find an efficient representation that took account for that kind of rotation?

00:15:12.640 | I had to, otherwise I couldn't do the learning.

00:15:14.560 | Wow.

00:15:16.660 | But I had three parts to my tic-tac-toe program, and I called it brain one, brain two, and brain

00:15:24.880 | three. So brain one just played a... Let's see. At random.

00:15:35.280 | Okay.

00:15:37.060 | It's your turn. Okay. You got to put an X somewhere. It has to go in an empty space,

00:15:40.960 | but that's it. Okay. Choose one and play there. Brain two

00:15:51.680 | had a canned routine, and I think it also... Maybe it assumed you were the first player,

00:15:59.200 | or maybe it allowed you to be first. I think you're allowed to be either first or second,

00:16:03.440 | but it had a canned built-in strategy known to be optimum for tic-tac-toe. Before I forget,

00:16:09.760 | by the way, I learned many years later that Charles Babbage had thought about programming

00:16:18.480 | tic-tac-toe for his dream machine that he was never able to finish.

00:16:23.680 | Wow. So that was the program he thought about?

00:16:26.400 | More than 100 years ago.

00:16:27.680 | Yeah. Wow.

00:16:28.480 | Yeah. He did that. Okay. And I had, however, been influenced by a demonstration at the

00:16:38.080 | Museum of Science and Industry in Chicago. It's like Boston's science museum. I think

00:16:44.400 | Bell Labs had prepared a special exhibit about telephones and relay technology, and they had a

00:16:51.440 | tic-tac-toe playing machine as part of that exhibit. So that had been one of my...

00:16:58.000 | Something I'd seen before I was a freshman in college and inspired me to see if I could write

00:17:05.280 | a program for it. Okay. So anyway, brain one, random, knowing nothing. Brain two,

00:17:13.840 | knowing everything. Then brain three was the learning one. And I could play brain one against

00:17:22.000 | brain one, brain one against brain two, and so on. And so you could also play against the user,

00:17:28.720 | against a live universe. So I started going, the learning thing, and I said, "Okay,

00:17:35.120 | take two random people just playing tic-tac-toe, knowing nothing." And after about... I forget the

00:17:47.680 | number now, but it converged after about 600 games to a safe draw. The way my program learned was

00:17:56.880 | actually, it learned how not to make mistakes. It didn't try to do anything for winning, it just

00:18:05.120 | tried to say not losing. Yeah, draw. Yeah, not lose.

00:18:07.760 | So that was probably because of the way I designed the learning thing. I could have had a different

00:18:12.880 | reinforcement function that would reward brilliant play. But anyway, it didn't...

00:18:21.280 | And if I took a novice against a skilled player, it was able to learn how to play a good game.

00:18:29.520 | And that was really my... But after I finished that, I felt I understood programming.

00:18:38.160 | Was there... Did a curiosity and interest in learning systems persist for you?

00:18:48.800 | So why did you want Brain 3 to learn? Yeah, I think naturally, we're talking

00:18:58.000 | about Rod Brooks. He was teaching all kinds of very small devices to learn stuff. If a leaf

00:19:07.520 | drops off of a tree, he was saying something, "Well, it learns if there's wind or not."

00:19:17.120 | But I mean, he pushed that a little bit too far, but he said he could probably train some little

00:19:22.480 | mini bugs to scour out dishes if he had enough financial support. I don't know.

00:19:27.920 | Can I ask you about that? Because he also mentioned that during those years,

00:19:36.960 | there was discussion about, inspired by Turing, about computation, of what is computation.

00:19:46.480 | Yeah. And...

00:19:47.840 | Yeah, I never thought about any stuff like that. That was way too philosophical. I mean,

00:19:56.080 | I was a freshman after all. I mean, I didn't... I was pretty much a machine.

00:20:05.360 | So it's almost like, yeah, I got you. It's a tinkering mindset, not a philosophical mindset.

00:20:13.840 | It was just exciting to me to be able to control something, but not to say, "Hmm,

00:20:21.120 | am I solving a big problem or something like that? Or is this a step for humankind or anything?"

00:20:26.160 | No, no way.

00:20:26.720 | When did you first start thinking about computation in the big sense? You know,

00:20:34.000 | like the universal Turing machine sense?

00:20:35.760 | Well, I mean, I had to pass an exam. I had to take classes on computability when I was a senior.

00:20:45.440 | So we read this book by Martin Davis and, yeah, this is cool stuff. But I learned about it because

00:20:52.560 | I needed to pass the exams, but I didn't invent any of that boring stuff. But I had great fun

00:21:00.400 | playing with the machine. I wrote programs because it was fun to write programs and get this...

00:21:09.040 | I mean, it was like watching miracles happen.

00:21:13.760 | You mentioned in an interview that when reading a program, you can tell when the author of the

00:21:22.320 | program changed. How the heck can you do that? What makes a distinct style for a programmer,

00:21:31.600 | do you think? There's different... Hemingway has a style of writing versus James Joyce or something.

00:21:39.600 | Yeah, those are pretty easy to imitate, but it's the same with music and whatever.

00:21:50.320 | During the pandemic, I spent a lot more time playing the piano and I found something that I'd

00:21:55.760 | had when I was taking lessons before I was a teenager. And it was Yankee Doodle played in

00:22:07.760 | the style of... You had Beethoven and you had Debussy and Chopin, and the last one was Gershwin.

00:22:19.040 | And I played over and over again. I thought it was so brilliant, but it was so easy. But also

00:22:26.720 | to appreciate how this author, Mario, somebody or other, had been able to reverse engineer

00:22:35.600 | the styles of those composers. But now, particularly to your question, I mean,

00:22:47.120 | it was pretty obvious in this program I was reading, it was a compiler and it had been

00:22:53.600 | written by a team at Carnegie Mellon. And I have no idea which program was responsible for it,

00:23:02.880 | but you would get to a part where the guy would just not know how to move things between registers

00:23:09.760 | very efficiently. And so everything that could be done in one instruction would take three or

00:23:15.840 | something like that. That would be a pretty obvious change in style. But there were also

00:23:21.760 | flashes of brilliance where you could do in one instruction. Normally I used two, because you knew

00:23:28.480 | enough about the way the machine worked that you could accomplish two goals in one step.

00:23:34.240 | So it was mostly the brilliance of the concept more than the semicolons or the use of short

00:23:44.000 | sentences versus long sentences or something like that.

00:23:46.320 | So you would see the idea in the code, and you can see the different style of thinking expressed.

00:23:52.160 | Right. It was stylistic. I mean, I could identify authors by the amount of technical

00:24:01.120 | aptitude they had, but not by style in the sense of rhythm or something like that.

00:24:08.480 | So if you think about Mozart, Beethoven, Bach, if somebody looked at Don Knuth's code,

00:24:15.840 | would they be able to tell that this is a distinct style of thinking going on here?

00:24:22.720 | What do you think? And what would be the defining characteristic of the style?

00:24:31.440 | Well, my code now is literate programming, so it's a combination of English and C mostly. But

00:24:40.000 | if you just looked at the C part of it, you would also probably notice that I use a lot of global

00:24:49.120 | variables that other people don't. And I expand things in line more than instead of calling.

00:24:55.200 | Anyway, I have different subset of C that I use.

00:25:00.000 | Okay. But that's a little bit stylistic.

00:25:02.320 | But with literate programming, you alternate between English and C or whatever.

00:25:08.160 | And by the way, people listening to this should look up literate programming. It's

00:25:14.480 | very interesting concept that you proposed and developed over the years.

00:25:21.040 | Yeah. That's the most significant thing, I think, to come out of the tech project.

00:25:30.880 | I realized that my programs were to be read by people and not just by computers, and

00:25:44.080 | that typography could massively enhance that. And so, I mean, they're just wondering if they're

00:25:53.360 | going to look it up, that they should also look up this book called Physically Based Rendering

00:25:58.880 | by Matt Farr. And gosh, anyway, it got an Academy Award. But all the graphic effects you see in

00:26:10.080 | movies are accomplished by algorithms. And the whole book is a literate program. It tells you not

00:26:19.040 | only how you do all the shading and bring images in that you need for animation and textures and so

00:26:28.160 | on, but it also, you can run the code. And so, I find it an extension of how to teach programming

00:26:42.640 | by telling a story as part of the program. So, it works as a program, but it's also readable

00:26:51.840 | by humans. Yes, and especially by me a week later or a year later.

00:26:58.720 | That's a good test. You yourself understand the code easily a week or a month or a year later.

00:27:06.160 | So, it's the greatest thing since sliced bread.

00:27:12.160 | Programming? Or literate?

00:27:14.640 | Literate programming.

00:27:15.600 | Okay. You heard it here first. Okay. You dodged this question in an interview I listened to.

00:27:24.080 | So, let me ask you again here. What makes for a beautiful program?

00:27:29.680 | What makes for a beautiful program?

00:27:31.840 | Yeah. What are the characteristics you see? Like you just said, literate programming.

00:27:36.000 | What are the characteristics you see in a program that make you sit back and say, "That's pretty

00:27:41.600 | good"?

00:27:43.280 | Well, the reason I didn't answer is because there are dozens and dozens of answers to that.

00:27:48.080 | Because you can define beauty, the same person will define beauty a different way from hour to

00:27:56.080 | hour. I mean, it depends on what you're looking for. At one level, it's beautiful just if it

00:28:02.560 | works at all. Another level, it's beautiful if it can be understood easily. It's beautiful if it's

00:28:18.000 | literate programming, it's beautiful, it makes you laugh. I mean…

00:28:21.280 | Yeah. I'm actually… So, I'm with you. I think beauty, if it's readable…

00:28:26.480 | Readable, yeah.

00:28:28.320 | If you understand what's going on and also understand the elegance of thought behind it.

00:28:35.120 | And then also, as you said, wit and humor. I was always… I remember having this conversation. I

00:28:42.960 | had this conversation on Stack Overflow, whether humor is good in comments. And I think it is.

00:28:51.040 | Whether humor is good in comments.

00:28:53.120 | Like when you add comments in the code.

00:28:55.520 | Yeah.

00:28:56.720 | I always thought a little bit of humor is good. It shows personality. It shows character,

00:29:03.440 | shows wit and fun and all those kinds of things of the personality of the programmer.

00:29:08.800 | Yeah. Okay. So, a couple days ago, I received a wonderful present from my former editor at

00:29:17.040 | Aston Wesley. He's downsizing his house and he found that somebody at the company had

00:29:24.880 | found all of their internal files about the art of computer programming from the 1960s,

00:29:32.240 | and they gave it to him. And then, before throwing it in the garbage. And then, so he said, "Oh,

00:29:40.080 | yeah." He planned to keep it for posterity, but now he realized that posterity is a bit too much

00:29:46.400 | for him to handle, so he sent it to me. And so, I just received this big stack of letters,

00:29:56.320 | some of which I had written to them, but many of which they had written to

00:30:01.200 | early guinea pigs who were telling them whether they should publish or not. And one of the things

00:30:08.560 | was in the comments to volume one, the major reader was Bob Floyd,

00:30:19.840 | who is my great co-worker in the '60s, died early, unfortunately. And he commented about the humor

00:30:35.360 | in it. And so, we had, he ran it by me, he says, "Keep this joke in or not."

00:30:41.200 | They also sent it out to focus groups. What do you think about humor in a book about computer

00:30:49.760 | programming? What's the conclusion? And I stated my philosophy is that the ideal thing is that it's

00:30:57.840 | something where the reader knows that there's probably a joke here if he only understood it,

00:31:04.160 | and this is a motivation to understand, to think about it a little bit. But anyway,

00:31:11.360 | very delicate humor. I mean, it's really, each century invents a different kind of humor too.

00:31:19.200 | Different cultures have different kinds of humor. Yeah, like we talked about Russia a little bit

00:31:27.600 | offline. There's dark humor. And when a country goes through something difficult-

00:31:35.120 | Right, "Veteran of the Night Live" and stuff like this. And Jack Benny, I mean,

00:31:39.600 | Steve Allen wrote this book about humor, and it was the most boring book. But he was one of my

00:31:47.040 | idols. But yeah, it's called "The Funny Men" or something like that. But yeah, okay. So anyway,

00:31:54.960 | I think it's important to know that this is part of life, and it should be fun and not.

00:32:00.960 | And so I wrote this organ composition, which is based on the Bible, but I didn't refrain from

00:32:10.160 | putting little jokes in it also in the music. It's hidden in the music.

00:32:15.600 | It's there, yeah. A little humor is okay?

00:32:19.440 | Yeah. I mean, not egregious humor. So in this correspondence, there were

00:32:24.960 | things I said, "Yeah, I really shouldn't have done that." But other ones I insisted on. And I've got

00:32:35.760 | jokes in there that nobody has figured out yet. In fact, in volume two, I've got a cryptogram,

00:32:45.200 | a message, enciphered. And in order to decipher it, you're going to have to break an RSA key,

00:32:53.120 | which is larger than people know how to break. And so if computers keep getting faster and faster,

00:33:00.720 | then it might be 100 years, but somebody will figure out what this message is, and they will

00:33:05.760 | laugh. I mean, I've got a joke in there. So that one you really have to work for.

00:33:12.560 | I don't know if you've heard about this. Let me explain it. Maybe you'll find it interesting.

00:33:18.560 | So OpenAI is a company that does AI work, and they have this language model. It's a neural

00:33:26.880 | network that can generate language pretty well. But they also, on top of that, developed something

00:33:35.280 | called OpenAI Codex. And together with GitHub, they developed a system called OpenAI Copilot.

00:33:42.720 | Let me explain what it does. There's echoes of literate programming in it. So what you do

00:33:50.720 | is you start writing code, and it completes the code for you. So for example, you start,

00:33:57.600 | let's go to your factoring program. You write in JavaScript and Python and any language

00:34:04.480 | that it trained on. You write the first line and some comments, like what this code does,

00:34:12.080 | and it generates the function for you. And it does an incredibly good job. It's not provably right,

00:34:19.520 | but it often does a really good job of completing the code for you.

00:34:23.040 | - I see. But how do you know whether it did a good job or not?

00:34:26.880 | - You could see a lot of examples where it did a good job. And so it's not a thing that

00:34:34.000 | generates the code for you. It starts, it gives you, so it puts the human in the seat of fixing

00:34:41.760 | issues versus writing from scratch. Do you find that kind of idea at all interesting?

00:34:47.920 | - Every year we're going to be losing more and more control over what machines are doing. And

00:34:53.520 | people are saying, well, it seems to, when I was a professor at Caltech,

00:35:00.880 | in the sixties, we had this guy who talked a good game. He could give inspiring lectures and you'd

00:35:10.240 | think, well, certainly the things he was talking about an hour later, you say, well, what did he

00:35:16.640 | say? But he really felt that it didn't matter whether computers got the right answer or not.

00:35:23.520 | It just mattered whether it made you happy or not. In other words, if your boss paid for it,

00:35:29.040 | then you had a job, you could take care of your wife.

00:35:35.200 | - So happiness is more important than truth.

00:35:37.120 | - Exactly. He didn't believe in truth, but he was a philosopher.

00:35:40.800 | - I like it. And somehow you see...

00:35:45.680 | - We're going that way. I mean, so many more things are taken over by saying, well, this seems to

00:35:52.640 | work. And when there's a competing interest involved, neither side understands why the

00:36:01.200 | decision is being made. We realize now that it's bad, but consider what happens five years, 10

00:36:11.120 | years down the line, when things get even more further detached and each thing is based on

00:36:17.840 | something from the previous year.

00:36:19.760 | - Yeah. So you start to lose... The more you automate, the more you start to lose track of

00:36:25.920 | some deep human thing.

00:36:27.520 | - Exponentially.

00:36:27.600 | - Exponentially. So that's the dark side. The positive side is the more you automate,

00:36:36.080 | the more you let humans do what humans do best. So maybe programming, maybe humans should focus

00:36:45.200 | on a small part of programming that requires that genius, the magic of the human mind,

00:36:50.480 | and the mess you let the machine generate. I mean, that's the positive, but of course,

00:36:57.360 | it does come with the darkness of automation. What's better, correctness?

00:37:02.720 | - I'm never going to try to write a book about that. I'm never going to recommend to any of

00:37:08.080 | my students to work for them.

00:37:09.360 | - So you're on the side of correctness, not beauty.

00:37:13.840 | - I'm on the side of understanding.

00:37:16.560 | - Understanding.

00:37:17.680 | - And I think these things are really marvelous if what they do is, all of a sudden we have a

00:37:25.600 | better medical diagnosis or it'll help guide some scientific experiment or something like this,

00:37:31.760 | curing diseases or whatever. But when it affects people's lives in a serious way,

00:37:43.520 | so if you're writing code for, "Oh yeah, here, this is great. This will make a slaughter bot."

00:37:50.160 | - Okay. So I see. So you have to be very careful. Like right now, it seems like fun and games.

00:37:59.600 | It's useful to write a little JavaScript program that helps you with a website.

00:38:04.160 | But like you said, one year passes, two years passes, five years, and you forget.

00:38:10.080 | You start building on top of it, and then all of a sudden you have autonomous weapon systems.

00:38:14.560 | - Well, we're all dead. It doesn't matter in that sense.

00:38:19.520 | - Well, in the end, this whole thing ends anyway.

00:38:25.440 | - There is a heat death of the universe predicted, but I'm trying to postpone that for...

00:38:35.200 | - For a little bit? Well, it'd be nice that at the end, as we approach the heat death of the

00:38:42.400 | universe, there's still some kind of consciousness there to appreciate it. Hopefully human consciousness.

00:38:51.200 | - I'll settle for 10 to the 10 to the 10 to the 10th year, some finite number. But

00:38:55.680 | things like this might be the reason we don't pick up any signals from extraterrestrial...

00:39:04.240 | - They don't want anything to do with us. Oh, because they...

00:39:07.760 | - Because they invented it too.

00:39:10.080 | - So you do have a little bit of worry on the existential threats of AI and automation.

00:39:22.480 | So like removing the human from the picture.

00:39:25.840 | - Et cetera, yeah. People have more potential to do harm now by far than they did 100 years ago.

00:39:35.120 | - But are you optimistic about... So humans are good at creating destructive things,

00:39:42.000 | but also humans are good at solving problems.

00:39:44.240 | - Yeah, I mean, there's half empty and half full, you know.

00:39:46.480 | - So are we half full?

00:39:50.000 | - I can go... So let me put it this way, because it's the only way I can be optimistic. But

00:40:00.000 | think of things that have changed because of civilization. They don't occur just in nature.

00:40:11.040 | So just imagine the room we're in, for example. Okay, we've got pencils, we've got books, we've

00:40:20.880 | got tables, we've got microphones, clothing, food. All these things were added. Somebody

00:40:28.240 | invented them one by one, and millions of things that we inherit, okay? And it's inconceivable

00:40:38.560 | that so many millions of billions of things wouldn't have problems, and we'd get it all right.

00:40:46.720 | And each one would have no negative effects and so on. So it's very amazing that as much

00:40:57.680 | works as does work. - It's incredibly amazing. And actually,

00:41:03.760 | that's the source of my optimism as well, including for artificial intelligence. So

00:41:09.680 | we drive over bridges, we use all kinds of technology, we don't know how it works,

00:41:17.440 | and there's millions of brilliant people involved in building a small part of that,

00:41:22.000 | and it doesn't go wrong, and it works. And I mean, it works, and it doesn't go wrong often enough

00:41:30.240 | for us to suffer. - And we can identify

00:41:32.720 | things that aren't working and try to improve on them.

00:41:37.840 | - In a often suboptimal way. - Oh, absolutely.

00:41:41.920 | - But it's still so- - But the kind of things that I know how to

00:41:48.560 | improve require human beings to be rational, and I'm losing my confidence that human beings

00:41:54.160 | are rational. - Yeah, yeah. Now, here you go again with

00:41:58.560 | the worst-case analysis. They may not be rational, but they're clever and beautiful in their own kind

00:42:11.360 | of way. I tend to think that most people have the desire and the capacity to be good to each other,

00:42:19.280 | and love will ultimately win out. If they're given the opportunity, that's where they lean.

00:42:25.440 | In "The Art of Computer Programming," you wrote, "The real problem is that programmers have spent

00:42:32.000 | far too much time worrying about efficiency in the wrong places and at the wrong times.

00:42:37.760 | Premature optimization is the root of all evil," in parentheses, or at least most of it,

00:42:44.800 | in programming. Can you explain this idea? What's the wrong time? What is the wrong place for

00:42:53.040 | optimization? - So, first of all, the word

00:42:56.640 | optimization. I started out writing software, and optimization was, I was a compiler writer,

00:43:05.120 | so optimization meant making a better translation so that it would run faster on a machine. So,

00:43:15.920 | an optimized program is just like, you run a program and you set the optimization level

00:43:21.600 | to the compiler. So, that's one word for optimization. At that time, I happened to

00:43:30.240 | be looking in an unabridged dictionary for some reason or other, and I came to the word optimize.

00:43:36.800 | What's the meaning of the word optimize? And it says, "To view with optimism."

00:43:42.080 | And you look in Webster's dictionary of English language in the early 1960s, that's what optimize

00:43:51.840 | meant. Okay. So, people started doing cost optimization, other kinds of things,

00:43:59.520 | whole subfields of algorithms and economics and whatever are based on what they call optimization

00:44:09.760 | now. But to me, optimization, when I was saying that, was changing a program to make it more

00:44:20.080 | tuned to the machine. And I found out that when a person writes a program,

00:44:26.640 | he or she tends to think that the parts that were hardest to write are going to be hardest for the

00:44:36.000 | computer to execute. So, maybe I have 10 pages of code, but I had to work a week writing this page.

00:44:46.000 | I mentally think that when the computer gets to that page, it's going to slow down.

00:44:50.800 | Right.

00:44:52.020 | It's going to say, "Oh, I don't understand what I'm doing. I better be more careful." Anyway,

00:44:56.880 | this is, of course, silly, but it's something that we don't know when we write a piece of code. We

00:45:04.160 | don't know whether the computer is actually going to be executing that code very much.

00:45:10.720 | So, people had a very poor understanding of what the computer was actually doing.

00:45:17.920 | I made one test where we studied a Fortran compiler,

00:45:23.600 | and it was spending more than 80% of its time reading the comments card.

00:45:28.480 | But as a programmer, we were really concerned about how fast it could take a complicated

00:45:35.040 | expression that had lots of levels of parentheses and convert that into something. But that was just

00:45:43.760 | less than 1%. So, if we optimize that, we didn't know what we were doing. But if we knew that it

00:45:53.120 | was spending 80% of its time on the comments card in 10 minutes, we could make the compiler run more

00:45:59.760 | than twice as fast.

00:46:01.120 | You could only do that once you've completed the program, and then you empirically study where...

00:46:05.760 | I had some kind of profiling that I knew what was important. Yeah.

00:46:09.520 | So, you don't think this applies generally? I mean, there's something that rings true to this

00:46:15.200 | across all of them.

00:46:15.680 | I'm glad that it applied generally, but it was only my good luck. I said it, but I said it in

00:46:23.440 | a limited context, and I'm glad if it makes people think about stuff.

00:46:28.960 | But it applies in another sense too, that is, sometimes I will do optimization in a way that

00:46:41.200 | does help the actual running time, but makes the program impossible to change next week,

00:46:49.520 | because I've changed my data structure or something that made it less adaptable.

00:46:56.080 | So, one of the great principles of computer science is laziness, or whatever you call it,

00:47:04.000 | late binding. Hold off decisions when you can. And we understand now,

00:47:14.720 | quantitatively, how valuable that is.

00:47:18.640 | What do you mean we understand?

00:47:23.680 | People have written thesis about how late binding will improve the... I mean, just-in-time

00:47:31.360 | manufacturing or whatever, you can defer a decision instead of doing your advanced planning

00:47:37.840 | and say, "I'm going to allocate 30% to this and 50%..."

00:47:41.440 | So, in all kinds of domains, there's an optimality to laziness in many cases.

00:47:45.920 | Decision is not made in advance. So, instead, you design, in order to be flexible,

00:47:53.120 | to change with the way the wind is blowing.

00:47:56.800 | Yeah. But so, the reason that line resonated with a lot of people is because there's something

00:48:04.240 | about the programmer's mind that wants, that enjoys optimization. So, it's a constant struggle

00:48:11.040 | to balance laziness and late binding with the desire to optimize, the elegance of a well-optimized

00:48:23.040 | code is something that's compelling to programming.

00:48:25.920 | Yeah. It's another concept of beauty.

00:48:30.000 | Let me ask you a weird question. So, Roger Penrose has talked about computation, computers,

00:48:39.600 | and he proposed that the way the human mind discovers mathematical ideas is something more

00:48:49.360 | than a computer, that a universal Turing machine cannot do everything that a human mind can do.

00:48:57.520 | Now, this includes discovering mathematical ideas, and it also includes, he's written a

00:49:04.880 | book about it, consciousness. So, I don't know if you know, Roger, but...

00:49:08.240 | My daughter's kids played with his kids in Oxford.

00:49:14.400 | Nice. So, do you think there is such a limit to the computer? Do you think consciousness is more

00:49:21.520 | than a computation? Do you think the human mind, the way it thinks, is more than a computation?

00:49:27.520 | I mean, I can say yes or no, but I have no reason.

00:49:33.760 | I mean...

00:49:36.000 | So, you don't find it useful to have an intuition in one way or the other? Like,

00:49:40.320 | when you think about algorithms, isn't it useful to think about...

00:49:43.040 | I think it's an unanswerable question, in my opinion, is no better than anybody else's.

00:49:49.200 | You think it's unanswerable. So, you don't think eventually science...

00:49:52.160 | How many angels can dance on the head of a... I mean, I don't know.

00:49:54.800 | But angels...

00:49:56.560 | Anyway, there are lots of things that we can speculate about, but I don't want somebody to

00:50:04.480 | say, "Oh, yeah, Cano said this, and so he's smart, and so that must be..." I mean, I say it's

00:50:12.560 | something that we'll never know.

00:50:14.480 | Interesting. Okay, that's a strong statement. I personally think it's something we will know

00:50:22.560 | eventually. Like, there's no reason to me why the workings of the human mind

00:50:28.000 | are not within the reach of science.

00:50:30.640 | That's absolutely possible, and I'm not denying it.

00:50:34.000 | Yeah. But right now, you don't have a good intuition one way or the other.

00:50:37.600 | That's also possible that an AI created the universe. Intelligent design has all been done

00:50:45.680 | by an AI. All of these things are... But you're asking me to pronounce on it, and I don't have

00:50:54.800 | any expertise. I'm a teacher that passes on knowledge, but I don't know... The fact that I

00:51:02.880 | vote yes or no on...

00:51:06.480 | Well, you do have expertise as a human, not as a teacher or a scholar of computer science.

00:51:13.840 | I mean, that's ultimately the realm of where the discussion of human thought and consciousness is.

00:51:21.040 | I know where Penrose is coming from. I'm sure he has no... He might even have thought he

00:51:27.840 | proved it, but...

00:51:28.880 | No, he doesn't. He doesn't prove it. He is following intuition.

00:51:33.520 | I mean, you have to ask John McCarthy. John McCarthy, I think,

00:51:38.560 | was totally unimpressed by these statements.

00:51:41.920 | So you don't think... So even like the Turing paper on the Turing test that starts by asking,

00:51:52.400 | "Can machines think?" You don't think these kind of... So Turing doesn't like that question.

00:51:59.520 | Yeah. I don't consider it important, let's just put it that way,

00:52:03.280 | because it's in the category of things that it would be nice to know, but I think it's

00:52:10.720 | beyond knowledge. And so I don't... I'm more interested in knowing about the Riemann hypothesis

00:52:19.040 | or something.

00:52:19.540 | So when you say... It's an interesting statement, "beyond knowledge."

00:52:23.680 | Yeah.

00:52:24.720 | I think what you mean is it's not sufficiently well... It's not even known well enough to be

00:52:31.200 | able to formalize it in order to ask a clear question. And so that's why it's beyond knowledge,

00:52:37.840 | but that doesn't mean it's not eventually going to be formalized.

00:52:41.680 | Yeah. Maybe consciousness will be understood some day, but the last time I checked,

00:52:49.600 | it was still 200 years away. I haven't been specializing in this by any means, but I went

00:52:56.080 | to lectures about it 20 years ago when I was... There was a symposium at the American Academy

00:53:02.800 | in Cambridge, and it started out by saying essentially,

00:53:06.400 | "Everything that's been written about consciousness is hogwash."

00:53:12.880 | I tend to disagree with that a little bit. So consciousness for the longest time still

00:53:22.480 | is in the realm of philosophy. So it's just conversations without any basis and understanding.

00:53:28.240 | Still, I think once you start creating artificial intelligence systems that interact with humans,

00:53:38.320 | and they have personality, they have identity, you start flirting with the question of consciousness,

00:53:45.760 | not from a philosophical perspective, but from an engineering perspective.

00:53:49.680 | Yeah.

00:53:50.240 | And then it starts becoming much more... I feel like...

00:53:53.840 | Yeah. Don't misunderstand me. I certainly don't disagree with that at all.

00:53:59.360 | Even at these lectures that we had 20 years ago, there were neurologists pointing out that

00:54:08.560 | that human beings had actually decided to do something before they were conscious of making

00:54:14.480 | that decision. I mean, they could tell that signals were being sent to their arms before

00:54:22.400 | they knew that they were sick, and things like this are true. And Les Valiant has

00:54:31.920 | an architecture for the brain, and more recently, Christos Papadimitriou,

00:54:37.600 | in the Academy of Science Proceedings a year ago with two other people, but I know Christos

00:54:45.920 | very well. And he's got this model of this architecture by which you could create things

00:54:58.640 | that correlate well with experiments that are done on consciousness. And he actually has a

00:55:08.400 | machine language in which you can write code and test hypotheses. And so we might have a big

00:55:22.160 | breakthrough. My personal feeling is that consciousness, the best model I've heard of

00:55:30.240 | to explain the miracle of consciousness is that somehow inside of our brains, we're having a

00:55:45.200 | continual survival for the fittest competition. As I'm speaking to you, all the possible things I

00:55:52.560 | might be wanting to say... Are all in there. There's like a voting going on.

00:55:57.760 | Yeah, right. And one of them is winning, and that's affecting the next sentence and so on.

00:56:06.080 | And there was this book, Machine Intelligence or something?

00:56:11.840 | On Intelligence.

00:56:12.640 | On Intelligence. Yeah. Bill Atkinson was a total devotee of that book.

00:56:21.360 | Well, I like whether it's consciousness or something else, I like the storytelling part

00:56:27.360 | that it feels like for us humans, it feels like there's a concrete... It's almost like

00:56:35.120 | literary programming. I don't know what the programming going on on the inside,

00:56:38.640 | but I'm getting a nice story here about what happened. And it feels like I'm in control and

00:56:44.080 | I'm getting a nice clear story. But it's also possible there's a computation going on

00:56:48.960 | that's really messy. There's a bunch of different competing ideas. And in the end,

00:56:54.000 | it just kind of generates a story for you to... A consistent story for you to believe.

00:57:00.080 | And that makes it all nice.

00:57:01.680 | Yeah. And so I prefer to talk about things that I have some expertise in

00:57:07.520 | than things which I'm only on the sideline.

00:57:13.440 | So there's a tricky thing. I don't know if you have any expertise in this.

00:57:18.560 | You might be a little bit on the sideline. It'd be interesting to ask though.

00:57:21.280 | What are your thoughts on cellular automata in the game of life?

00:57:24.960 | Have you ever played with those kinds of little games?

00:57:28.800 | I think the game of life is wonderful and shows all kinds of stuff about how things can evolve

00:57:43.200 | without the creator understanding anything more than the power of learning in a way. But to me,

00:57:51.520 | the most important thing about the game of life is how it focused for me

00:57:58.880 | what it meant to have free will or not. Because the game of life is obviously totally deterministic.

00:58:09.200 | Yes.

00:58:09.700 | I find it hard to believe that anybody who's ever had children cannot believe in free will. On the

00:58:17.360 | other hand, this makes it crystal clear. John Conway said he wondered whether it was immoral

00:58:30.080 | to shut the computer off after he got into a particularly interesting play of the game of life.

00:58:34.960 | Wow. Yeah. So to me, the reason I love the game of life is exactly as you said,

00:58:43.200 | a clear illustration that from simple initial conditions with simple rules,

00:58:48.960 | you know exactly how the system is operating, is deterministic. And yet, if you allow yourself to

00:58:58.080 | lose that knowledge a little bit, enough to see the bigger organisms that emerge,

00:59:06.240 | and then all of a sudden they seem conscious. They seem not conscious, but living.

00:59:11.040 | If the universe is finite, we're all living in the game of life to slow down. I mean,

00:59:17.520 | it's sped up a lot. But do you think technically some of the ideas that you used for analysis of

00:59:26.880 | algorithms can be used to analyze the game of life? Can we make sense of it or is it too weird?

00:59:33.040 | Yeah. I mean, I've got a dozen exercises in volume for fascicle six that actually work

00:59:43.360 | rather well for that purpose. Bill Gosspers came up with the algorithm that allowed Gali to run

00:59:57.120 | thousands and thousands of times faster. You know the website called Gali? G-O-L-L-Y.

01:00:04.400 | It simulates the cellular automata, a game of life.

01:00:07.680 | Yeah. You got to check it out. Yeah.

01:00:09.440 | Can I ask you about John Conway?

01:00:11.920 | Yes. In fact, I'm just reading now the issue of mathematical intelligence that came in last week.

01:00:20.480 | It's a whole issue devoted to remembrance of him.

01:00:27.680 | Did you know him?

01:00:29.040 | I slept overnight in his house several times.

01:00:33.840 | Yeah.

01:00:36.320 | He recently passed away.

01:00:37.760 | Yeah. He died a year ago, May, I think it was, of COVID.

01:00:49.200 | What are some memories of him, of his work that stand out for you? On a technical level,

01:00:58.160 | did any of his work inspire you? On a personal level, did he himself inspire you in some way?

01:01:04.560 | Absolutely, all of those things. But let's see, when did I first meet him? I guess I first met

01:01:11.360 | him at Oxford in 1967 when I was...

01:01:14.720 | Wow. Okay. That's a long time ago.

01:01:17.120 | Yeah. You were minus 20 years old or something. I don't know, 1967. But there was a conference where

01:01:25.840 | Minus 20 years old.

01:01:28.720 | I think I was speaking about something known as the Knuth-Bendix algorithm now. But he gave a

01:01:37.760 | famous talk about knots. I didn't know at the time, but that talk had now... It was the source

01:01:48.160 | of thousands and thousands of papers since then. He was reported on something that he had done

01:01:55.120 | in high school, almost 10 years earlier, before this conference, but he never published it.

01:02:05.360 | He climaxed his talk by building some knots. You have these little plastic things that you

01:02:13.760 | can stick together. It's something like Lego, but easier. He made a whole bunch of knots in front of

01:02:23.600 | the audience and so on, and then disassembled it. It was a dramatic lecture. Before he had learned

01:02:31.680 | how to give even more dramatic lectures later. All right.

01:02:35.680 | Were you at that lecture?

01:02:37.920 | And I was there, yeah, because I was at the same conference. For some reason, I happened to be in

01:02:46.240 | Calgary at the same day that he was visiting Calgary. It was the spring of '72, I'm pretty sure.

01:02:58.240 | And we had lunch together. He wrote down during the lunch on a napkin,

01:03:03.840 | all of the facts about what he called numbers. He covered the napkin with the theorems about his

01:03:20.000 | idea of numbers. I thought it was incredibly beautiful. Later in 1972, my sabbatical year

01:03:31.280 | began and I went to Norway. In December of that year, in the middle of the night,

01:03:37.440 | the thought came to me, Conway's theory about numbers would be a great thing to teach students

01:03:46.880 | how to invent research and what the joys are of research. I had also read a book in dialogue

01:03:58.160 | by Alfred Rényi, kind of a Socratic thing where the two characters were talking to each other

01:04:07.280 | about mathematics. At the end, in the morning, I woke up my wife and said, "Jill, I think I want

01:04:18.160 | to write a book about Conway's theory. You know, I'm supposed to be writing the Art of Computer

01:04:28.640 | Programming and doing all this other stuff, but I really want to write this other book."

01:04:34.160 | And so we made this plan, but I said, "I thought I could write it in a week."

01:04:39.360 | And we made the plan then. So in January, I rented a room in a hotel in downtown Oslo. We

01:04:47.440 | were in sabbatical in Norway. And I rented the hotel in downtown Oslo and did nothing else

01:04:56.160 | except write up Conway's theory. And I changed the name to Surreal Numbers. So this book is now

01:05:03.920 | published as Surreal Numbers. And we'd always wondered, "Would he like to have an affair in a

01:05:13.440 | hotel room?" So we figured out that she would visit me twice during the week. Things like this,

01:05:19.440 | you know, we would try to sneak in. This hotel was run by a mission organization. These ladies were

01:05:28.400 | probably very strict. But anyway, so- Yeah.

01:05:30.320 | And- It's a wild week in every way.

01:05:35.520 | But the thing is, I had lost that napkin in which he wrote the theory. But I looked for it,

01:05:42.640 | but I couldn't find it. So I tried to recreate from memory what he had told me at that lunch

01:05:48.480 | in Calgary. And as I wrote the book, I was going through exactly what the characters in the book

01:05:57.040 | were supposed to be doing. So I start with the two axioms and start out the whole thing. And

01:06:02.960 | everything is defined, flows from that, but you have to discover why. And every mistake that I

01:06:09.280 | make as I'm trying to discover it, my characters make too. And so it's a long, long story. But I

01:06:18.240 | worked through this week. And it was one of the most intense weeks of my life. And I described it

01:06:31.360 | in other places. But anyway, after six days, I finished it. And on the seventh day, I rested.

01:06:37.440 | And I sent to my secretary to type it. It was flowing as I was writing it,

01:06:46.160 | faster than I could think almost. But after I finished it, and try to write a letter to my

01:06:54.240 | secretary, telling her how to type it, I couldn't write anymore.

01:06:57.200 | You gave it everything.

01:06:59.440 | The muse had left me completely.

01:07:00.960 | Can you explain how that week could have happened? Like why is that seems like such a magical week?

01:07:06.880 | I have no idea. But anyway, there was some, it was almost as if I was channeling.

01:07:13.120 | So the book was typed, I sent it to Conway. And he said, well, Dan, you got the one axiom wrong.

01:07:21.520 | There's a difference between less than or equal and not greater than. I don't know.

01:07:30.240 | The opposite of being greater than and less than or equal. But anyway,

01:07:36.000 | technically, it can make a difference when you're developing a logical theory.

01:07:41.840 | And the way I had chosen was harder to do than John's original.

01:07:45.920 | So, and we visited him at his house in Cambridge. In April, we took a boat actually from Norway

01:07:53.840 | over to across the channel and so on and stayed with him for some days. And,

01:07:58.320 | and he told he talked, we talked about all kinds of things he has. He had

01:08:08.480 | puzzles that I'd never heard of before. He had a great way to solve the game of solitaire.

01:08:13.760 | Many of the common interests that we'd, you know, he'd never written them up. But anyway,

01:08:20.240 | then in the summertime, I took another week off and went to a place in the mountains of Norway and

01:08:30.080 | rewrote the book using the correct axiom. So that was the most intensive connection with Conway.

01:08:38.800 | After that, it started with a napkin.

01:08:41.440 | It started with a napkin. But we would run into each other. Yeah, the next really,

01:08:50.080 | I was giving lectures in Montreal. I was giving a series of seven lectures about a topic called

01:09:02.560 | stable marriages. And he arrived in Montreal between my sixth and seventh lecture. And we met

01:09:13.200 | at a party. And I started telling him about the topic I was doing. And he sat and thought about

01:09:21.920 | it. He came up with a beautiful theory to show that the, I mean, in technical terms, it's that

01:09:29.440 | the set of all stable marriages, it forms a lattice. And there was a simple way to find the

01:09:35.680 | greatest lower bound of two stable pairings and least upper bound of two stable marriage. And so

01:09:42.720 | I could use it in my lecture the next day. And he came up with this theorem during the party.

01:09:47.920 | And it's a brilliant.

01:09:51.520 | It's a distributive lesson. I mean, it added greatly to the theory of stable matching.

01:10:00.000 | So you mentioned your wife, Jill, you mentioned stable marriage. Can you tell the story of how

01:10:07.280 | you two met?

01:10:07.920 | So we celebrated 60 years of wedded bliss last month. And we met because I was dating her

01:10:17.680 | roommate. This was my sophomore year, her freshman year. I was dating her roommate and

01:10:24.480 | I wanted her advice on strategy or something like this. And anyway, I found I enjoyed her

01:10:32.720 | advice better than her. I enjoyed her roommate.

01:10:35.840 | You guys were majoring the same thing?

01:10:39.440 | No, no, no.

01:10:40.480 | Because I read something about working on a computer in grad school, on a difficult

01:10:47.440 | computer science topic.

01:10:48.640 | So she's an artist and I'm a geek.

01:10:55.120 | Okay. What was she doing with a computer science book? Or I read, was it the manual that she was

01:11:01.200 | reading? What was she reading?

01:11:02.560 | I wrote the manual that she had to take a class in computer science.

01:11:07.040 | Okay. And so...

01:11:09.440 | You're the tutor.

01:11:10.560 | No, no. Yeah. There were terrible times trying to learn certain concepts, but I learned art

01:11:22.400 | from her. And so we worked together occasionally in design projects, but every year we write a

01:11:31.120 | Christmas card and we each have to compromise our own notions of beauty.

01:11:39.520 | Yes. When did you fall in love with her?

01:11:43.360 | That day that I asked her about her roommate.

01:11:48.480 | Okay.

01:11:50.400 | I mean, no, I... Okay. So you're... I don't mind telling these things, depending on how

01:11:57.920 | you far, how far you go, but... But let me tell you...

01:12:02.880 | I promise. I promise not to go too far.

01:12:05.280 | Let me tell you this, that I never really enjoyed kissing until I found how she did it.

01:12:13.600 | Wow. And 60 years.

01:12:17.600 | Is there a secret you can say in terms of stable marriages of how you stayed together so long?

01:12:26.480 | The topic stable marriage, by the way, is not... It is a technical term.

01:12:32.800 | Yes.

01:12:34.560 | It's a joke, Don.

01:12:36.560 | But two different people will have to learn how to compromise and work together, and you're

01:12:48.320 | going to have ups and downs and crises and so on. And so as long as you don't set your expectation on

01:12:58.080 | having 24 hours of bliss, then there's a lot of hope for stability. But if you decide that it's...

01:13:06.960 | That there's going to be no frustration, then...

01:13:11.200 | So you're going to have to compromise on your notions of beauty when you write Christmas cards.

01:13:18.080 | That's it.

01:13:18.560 | You mentioned that Richard Feynman was someone you looked up to.

01:13:24.800 | Yep.

01:13:27.040 | Probably you've met him in Caltech.

01:13:28.880 | Well, we knew each other. Yeah, at Caltech for sure.

01:13:34.080 | You are one of the seminal personalities of computer science. He's one for physics.

01:13:41.520 | Is there specific things you picked up from him by way of inspiration or...?

01:13:49.520 | So we used to go to each other's lectures, but if I saw him sitting in the front row,

01:13:57.280 | it would throw me for a loop, actually. I would miss a few sentences.

01:14:05.440 | What unique story do I have? I mean, I often refer to his time in Brazil,

01:14:16.400 | where he essentially said they were teaching all the physics students the wrong way. They were just

01:14:22.880 | learning how to pass exams and not learning any physics. And he said, "If you want me to prove it,

01:14:29.760 | here, I'll turn to any page of this textbook, and I'll tell you what's wrong with this page."

01:14:36.960 | And he did so. And the textbook had been written by his host, and it was a big embarrassing

01:14:44.400 | incident, but he had previously asked his host if he was supposed to tell the truth.

01:14:48.480 | But anyway, it epitomizes the way education goes wrong in all kinds of fields,

01:14:58.160 | and has to periodically be brought back from a process of giving credentials to a process of

01:15:08.880 | giving knowledge. Yeah, that's probably a story that continues to this day in a bunch of places.

01:15:14.640 | Where it's too easy for educational institutions to fall into credentialism versus inspirationalism.

01:15:26.400 | I don't know if those are words, but sort of understanding versus just giving a little

01:15:33.600 | plaque. And it's very much like what we were talking about. If you want the computer to,

01:15:43.840 | if you want to be able to believe the answer, a computer is doing. One of the things Bob Floyd

01:15:50.320 | showed me in the '60s, there was a, he loved this cartoon. There were two guys standing in front of,

01:15:58.320 | in those days, a computer was a big thing, you know. And the first guy says to the other guy,

01:16:03.200 | he said, "This machine can do in one second what it would take a million people to do in a hundred

01:16:11.120 | years." And the other guy says, "Oh, so how do you know it's right?" That's a good line.

01:16:18.720 | Is there some interesting distinction between physics and math to you? Have you looked at

01:16:26.880 | physics much? Like speaking of Richard Feynman, the difference between the physics community,

01:16:33.520 | the physics way of thinking, the physics intuition versus the computer science,

01:16:38.000 | the theoretical computer science, the mathematical sciences, do you see that as a gap or are they

01:16:42.960 | strongly overlapping? It's quite different, in my opinion. I started as a physics major and I

01:16:50.400 | switched into math. And probably the reason was that I could get A+ on the physics exam, but I

01:16:58.640 | never had any idea why I would have been able to come up with the problems that were on those exams.

01:17:06.720 | But in math, I knew why the teacher set those problems and I thought of other problems that

01:17:15.120 | I could set too. And I believe it's quite a different mentality. It has to do with your

01:17:23.600 | philosophy of geekdom? Some of my computer scientist friends are really good at physics

01:17:31.760 | and others are not. And I'm really good at algebra, but not at geometry. Talk about different

01:17:40.560 | parts of mathematics. So they're different kinds of physical, but physicists think of things in

01:17:46.480 | terms of waves. And I can think of things in terms of waves, but it's like a dog walking on hind

01:17:53.360 | legs if I'm thinking about it. So you basically, you like to see the world in discrete ways and

01:18:00.960 | then physics is more continuous. Yeah. I'm not sure if Turing would have been a great physicist.

01:18:07.040 | I think he was a pretty good chemist, but I don't know. But anyway, I see things.

01:18:14.960 | I believe that computer science is largely driven by people who have brains who are good at

01:18:28.960 | resonating with certain kinds of concepts. And quantum computers, it takes a different kind of

01:18:37.120 | brain. Yeah, that's interesting. Yeah. Well, quantum computers is almost like at the intersection

01:18:42.640 | in terms of brain between computer science and physics, because it involves both at least at

01:18:49.920 | this time. But there is like the physicists I've known, they have incredibly powerful intuition.

01:18:59.200 | And I mean, statistical mechanics. So I study statistical mechanics and

01:19:05.760 | random processes are related to algorithms in a lot of ways. But there's lots of different

01:19:15.600 | flavors of physics as there are different flavors of mathematics as well. But the thing is that I

01:19:23.200 | don't see, well, actually when they talk to physicists, use a completely different language

01:19:30.640 | than when they're talking to, when they're writing expository papers. And so I didn't

01:19:35.840 | understand quantum mechanics at all from reading about it in Scientific American.

01:19:39.840 | But when I read how they described it to each other, talking about eigenvalues and various

01:19:47.760 | mathematical terms that made sense, then it made sense to me. But Hawking said that

01:19:56.000 | every formula you put in a book, you lose half of your readers. And so he didn't put any formulas

01:20:01.520 | in the book. So I couldn't understand his book at all. You could say you understood it, but I

01:20:06.640 | really didn't. Well, Feynman also spoke in this way. So Feynman, I think, prided himself on a

01:20:17.280 | really strong intuition, but at the same time, he was hiding all the really good, the deep

01:20:22.560 | computation he was doing. So there was one thing that I was never able to, I wish I'd had more time

01:20:31.520 | to work out with him, but I guess I could describe it for you. There's something that

01:20:37.520 | got my name attached to it called Knuth-Arrow notation, but it's a notation for very large

01:20:44.240 | numbers. And so I find out that somebody invented it in the 1830s. It's fairly easy to understand

01:20:55.600 | anyway. So you start with X plus X plus X plus X, N times, and you can call that XN.

01:21:04.960 | So XN is multiplication. Then you take X times X, times X times X, and N times. That gives you

01:21:13.920 | exponentiation, X to the Nth power. So that's one arrow. So XN with no arrows is multiplication.

01:21:22.720 | X arrow N is X to the Nth power. Yeah. So just to clarify for the...

01:21:27.760 | So X times X times X, N times is obviously XN.

01:21:34.640 | X plus X plus X, N times.

01:21:38.160 | Oh yeah. Okay. And then...

01:21:40.560 | XN, no arrows.

01:21:41.920 | And then multiplication is X to the N. And then here, the arrow is when you're doing the same

01:21:48.400 | kind of repetitive operation for the exponential.

01:21:51.680 | So I put in one arrow and I get X to the Nth power. Now I put in two arrows, and that takes

01:21:57.360 | X to the X to the X to the X to the X, N times power. So in other words, if it's two double arrow

01:22:08.080 | three, that would be two to the two to the two. So that would be two to the fourth power. That'd

01:22:14.880 | be 16. Okay. So that's the double arrow. And now you can do a triple arrow, of course, and so on.

01:22:28.800 | And I had this paper called, well, essentially big numbers. You try to impress your friend,

01:22:38.960 | but by saying a number they never thought of before. And I gave a special name for it,

01:22:46.160 | and designed a font for it that has script K and so on. But it really is 10, I think,

01:22:53.680 | like 10 quadruple arrow three or something like that. And I claim that that number is so mind

01:23:00.560 | boggling that you can't comprehend how large it is. But anyway, I talked to Feynman about this,

01:23:07.120 | and he said, "Oh, let's just use double arrow. But instead of taking integers, let's consider

01:23:15.440 | complex numbers." So you have, I mean, okay, X arrow, arrow two, that means X to the X.

01:23:23.600 | But what about X double arrow 2.5? Well, that's not too hard to figure out. That's

01:23:33.760 | interpolate between those. But what about X double arrow I, or one plus I, or some complex number?

01:23:44.080 | And so he claimed that there was no analytic function that would do the job.

01:23:53.040 | But I didn't know how he could claim that that wasn't true.

01:24:00.080 | And his next question was, did then have a complex number of arrows?

01:24:05.600 | Yeah, okay.

01:24:10.400 | Wow, okay.

01:24:11.760 | So that's Feynman.

01:24:13.280 | Can you describe what the Knuth-Morris-Pratt algorithm does, and how did you come to develop

01:24:24.080 | it? One of the many things that you're known for, and has your name attached to it.

01:24:28.640 | Yeah, all right. So it should be actually Morris-Pratt-Knuth,

01:24:33.920 | but we decided to use alphabetical order when we published the paper.

01:24:39.200 | The problem is something that everybody knows now if they're using a search engine.

01:24:45.760 | You have a large collection of text, and you want to know if the word Knuth appears anywhere in the

01:24:56.640 | text, let's say, or some other word that's less interesting than Knuth.

01:25:02.400 | That's the most interesting word.

01:25:05.040 | Like Morris or something.

01:25:05.920 | Like Morris, right.

01:25:07.520 | So anyway, we have a large piece of text, and it's all one long, one-dimensional thing.

01:25:15.520 | You know, first letter, second letter, et cetera, et cetera, et cetera.

01:25:19.520 | And so the question, we'd like to be able to do this quickly.

01:25:24.720 | And the obvious way is, let's say we're looking for Morris.

01:25:30.560 | So we would go through and wait till we get to letter M.

01:25:36.320 | Then we look at the next word, and sure enough, it's an O, and then an R.

01:25:40.800 | But then, too bad, the next letter is E.

01:25:46.880 | So we missed out on Morris.

01:25:50.240 | And so we go back and start looking for another.

01:25:54.480 | I'll go over again.

01:25:55.920 | So that's the obvious way to do it.

01:25:57.600 | All right.

01:26:00.560 | And Jim Morris noticed there was a more clever way to do it.

01:26:06.320 | The obvious way would have started, let's say, we found that letter M at character position 1000.

01:26:13.760 | So it was started next at character position 1001.

01:26:18.480 | But he said, no, look, we already read the O and the R, and we know that they aren't M's.

01:26:27.920 | So we don't have to read those over again.

01:26:32.560 | And this gets pretty tricky when the word isn't Morris, but it's more like abracadabra,

01:26:41.920 | where you have patterns that are occurring.

01:26:44.160 | Like repeating patterns, at the beginning, at the middle, and--

01:26:49.200 | Right.

01:26:49.700 | So he worked it out, and he put it into the system software at Berkeley, I think it was,

01:26:57.680 | where he was writing some Berkeley Unix, I think it was some routine that was supposed

01:27:03.280 | to find occurrences of patterns in text.

01:27:05.600 | And we didn't explain it.

01:27:11.520 | And so he found out that several months later, somebody had looked at it, didn't look right,

01:27:18.240 | and so they ripped it out.

01:27:19.200 | So he had this algorithm, but it didn't make it through, because it wasn't understood.

01:27:27.520 | Nobody knew about this particularly.

01:27:29.440 | Von Pratt also had independently discovered it a year or two later.

01:27:36.240 | I forget why.

01:27:39.280 | I think Von was studying some technical problem about palindromes or something like that.

01:27:50.480 | Von wasn't working on text searching, but he was working on an abstract problem that was related.

01:27:59.040 | Well, at that time, Steve Cook was a professor at Berkeley, and it was the greatest mistake that

01:28:08.400 | Berkeley CS department made, was not to give him tenure.

01:28:12.320 | So Steve went to Toronto.

01:28:17.680 | But I knew Steve while he was at Berkeley, and he had come up with a very peculiar theorem

01:28:24.400 | about a technical concept called a stack automaton.

01:28:29.120 | And a stack automaton is a machine that can't do everything a Turing machine can do, but

01:28:37.040 | it can only look at something at the top of a stack, or it can put more things on the stack,

01:28:43.680 | or it can take things off the stack.

01:28:46.880 | It can't remember a long string of symbols, but it can remember them in reverse order.

01:28:52.720 | So if you tell a stack automaton A, B, C, D, E, it can tell you afterwards E, D, C, B, A.

01:29:00.800 | It doesn't have any other memory except this one thing that it can see.

01:29:06.720 | And Steve Cook proved this amazing thing that says, if a stack automaton can recognize a language

01:29:16.560 | where the strings of the language are length N, in any amount of time whatsoever,

01:29:21.760 | to the stack automaton, you might use a zillion steps, a regular computer can recognize that

01:29:28.240 | same language in time N log N. So Steve had a way of transforming a computation that goes on and on

01:29:35.680 | and on and on, into using different data structures, into something that you can do on a regular

01:29:42.960 | computer, fast. The stack automaton goes slow, but somehow the fact that it can do it at all

01:29:52.720 | means that there has to be a fast way. So I thought this was a pretty cool theorem.

01:29:58.640 | And so I tried it out on a problem where I knew a stack automaton could do it,

01:30:07.280 | but I couldn't figure out a fast way to do it on a regular computer. I thought I was a pretty

01:30:12.720 | good programmer, but by golly, I couldn't think of any way to recognize this language efficiently.

01:30:21.840 | So I went through Steve Cook's construction. I filled my blackboard with all the, everything

01:30:29.760 | that stack automaton did, you know, I wrote down. And then I tried to see patterns in that,

01:30:40.080 | and how did he convert that into a computer program on a regular machine? And finally,

01:30:46.720 | I psyched it out. What was the thing I was missing so that I could say, oh yeah,

01:30:53.520 | this is what I should do in my program. And now I have a efficient program. And so I would never

01:31:02.720 | have thought about that if I hadn't had his theorem, which was a purely abstract thing.

01:31:09.200 | So you used this theorem to try to intuit how to use the stack automaton for the string matching

01:31:16.160 | problem?

01:31:16.960 | Yeah. So the problem I had started with was not the string matching problem, but then I realized

01:31:24.480 | that the string matching problem was another thing which could be done by a stack automaton.

01:31:30.640 | And so when I looked at what that told me, then I had a nice algorithm for this

01:31:36.000 | string matching problem. And it told me exactly what I should remember as I'm going through the

01:31:44.320 | string. And I worked it out, and I wrote this little paper called "Automata Theory Can Be

01:31:50.320 | Useful." And the reason was that it was the first, I mean, I had been reading all kinds of papers

01:31:56.480 | about automata theory, but it never taught me, it never improved my programming for everyday

01:32:03.360 | problems. It was something that you published in journals and it was interesting stuff. But

01:32:10.080 | here was a case where I couldn't figure out how to write the program. I had a theorem from

01:32:15.760 | automata theory, then I knew how to write the program. So this was, for me, a change in life.

01:32:24.160 | I started to say, maybe I should learn more about automata theory. And I showed this note to Vaughn

01:32:32.160 | Pratt, and he said, "Hey, that's similar to something I was working on." And then, and Jim

01:32:40.080 | Morris was at Berkeley too at the time. Anyway, he's had an illustrious career, but I haven't kept

01:32:48.160 | track of Jim, but Vaughn is my colleague at Stanford and my student later. But this was before

01:32:55.680 | Vaughn, Vaughn was still a graduate student and hadn't come to Stanford yet. So we found out that

01:33:01.360 | we'd all been working on the same thing. So it was our algorithm, we each discovered it

01:33:05.760 | independently, but each of us had discovered a different part of the elephant, a different

01:33:13.920 | aspect of it. And so we could put our things together. It was my job to write the paper.

01:33:19.840 | How did the elephant spring to life?

01:33:22.560 | Spring to life was because I had drafted this paper, automata theory can be useful,

01:33:31.840 | which was seen by Vaughn and then by Jim. And then we combined, because maybe they had also

01:33:37.600 | been thinking of writing something up about it.

01:33:40.720 | About specifically the string match?

01:33:42.240 | Specifically the string match problem, period.

01:33:45.840 | Let me ask a ridiculous question. Last time we talked, you told me what the most beautiful

01:33:54.080 | algorithm is actually for strongly connected graphs. What is the hardest problem, puzzle,

01:34:02.800 | idea in computer science for you personally that you had to work through? Just something that was

01:34:09.200 | just a...

01:34:09.520 | The hardest thing that I've ever been involved with?

01:34:13.280 | Yeah.

01:34:13.520 | Okay. Well, yeah, that's, I don't know how to answer questions like that, but in this case,

01:34:19.840 | it's pretty clear. Because it's called the birth of the giant component. Okay, so now let me explain

01:34:32.240 | that because this is actually gets into physics too. And it gets into something called Bose-Einstein

01:34:38.880 | statistics, but anyway, it's got some interesting stories and it connected with Berkeley again.

01:34:46.800 | So start with the idea of a random graph. Now this is, here we just say we have N points that

01:34:58.480 | are totally unconnected and there's no geometry involved. There's no saying some points are

01:35:05.520 | further apart than others. All points are exactly alike. And let's say we have a hundred points

01:35:13.040 | and we number them from zero to nine, nine. All right. Now let's take pi, the digits of pi, so

01:35:25.360 | two at a time. So we had 31, 41, 59, 26. We can go through pi. And so we take the first two, 31,

01:35:36.400 | 41, and let's put a connection between 0.31 and 0.41. That's an edge in the graph.

01:35:48.160 | Then we take 59, 26 and make another edge. And the graph gets bigger, gets more and more connected

01:35:58.160 | as we add these things one at a time. Okay. We started out with N points and we add M edges.

01:36:07.360 | Okay. Each edge is completely, we forgot about edges we had before. We make an edge twice.

01:36:15.600 | We make an edge from a point to itself even. Maybe pi is going to have a run of four digits in there.

01:36:23.280 | But anyway, we're evolving a graph at random. And a magical thing happens

01:36:34.880 | when the number of edges is like 0.49. And so maybe N is a million and I have 490,000 edges.

01:36:48.640 | Then it almost all the time, it consists of isolated trees, not even any loops.

01:37:01.360 | It's a very small number of edges so far. A little less than half N.

01:37:06.000 | But if I had 0.51 edges, it's a little more than half N. So a million points, 510,000 edges.

01:37:16.160 | Now it probably has one component that's much bigger than the others.

01:37:29.200 | And we call that the giant component. >> Can you clarify, first of all,

01:37:35.440 | is there a name for this kind of super cool pi random graph?

01:37:39.360 | >> Well, I call it the pi graph. No, no, the pi graph is actually, my pi graph is based on

01:37:51.840 | binary representation of pi, not the decimal representation of pi. But anyway,

01:37:57.360 | let's suppose I was rolling dice instead. >> So it doesn't have to be pi?

01:38:04.560 | >> It could be any source. The point is every step, choose totally at random one of those endpoints.

01:38:12.080 | Choose totally at random another one of the endpoints. Make that an edge. That's the process.

01:38:20.160 | >> Yeah. So there's nothing magical about pi that you were just giving us as an example?

01:38:24.320 | >> No, no. I was using pi to, I was sort of saying pi is sort of random that nobody knows

01:38:29.200 | a pattern in. >> Exactly. Got it. Got it.

01:38:31.360 | >> But it's not, yeah, I could have just as well drawn straws or something. This was a concept

01:38:39.280 | invented by Erdos and Rényi, and they called it the evolution of random graphs. And if you start

01:38:44.640 | out with a large number n and you repeat this process, all of a sudden a big bang happens

01:38:51.760 | at one half n. There'll be two points together, then maybe we'll have three,

01:38:56.480 | and then they maybe branch out a little bit. But they'll all be separate until we get to

01:39:04.640 | one half n. And we pass one half n, and all of a sudden there's substance to it. There's a big

01:39:14.240 | clump of stuff that's all joined together. >> So it's almost like a phase transition

01:39:18.320 | of some kind. >> It's exactly, it's a phase transition,

01:39:21.840 | but it's a double phase transition. It turns out it happens, there's actually two things going on

01:39:29.120 | at once at this phase transition, which is very remarkable about it. Okay. So a lot of the most

01:39:38.400 | important algorithms are based on random processes. And so I want to understand random processes

01:39:44.000 | and how, so there are data structures that sort of grow this way. Okay. So Dick Karp, one of the

01:39:50.800 | leading experts on randomized algorithms, had his students looking at this at Berkeley. And we heard

01:40:00.240 | a rumor that the students had found something interesting happening. The students are

01:40:07.280 | generating this, or simulating this random evolution of graphs, and they're taking snapshots

01:40:14.480 | every so often to take a look at what the graph is. And the rumor was that every time they looked,

01:40:22.560 | there was only one component that had loops in it, almost always. They do a million experiments,

01:40:28.560 | and only three or four times did they ever happen to see a loop at this point.

01:40:36.800 | I mean, no, more than one component with a loop. So they watch until the graph gets

01:40:43.200 | completely full. So it starts out totally empty and gets more and more edges all the time.

01:40:50.800 | And so, okay, certainly a loop comes along once, but now all the loops stay somehow joined to that

01:40:59.200 | one. There never were two guys with loops. Wow, interesting.

01:41:06.960 | In these experiments. Okay. So anyway, almost always, certainly not always. But with very high

01:41:16.480 | probability, this seemed to be true. So we heard about this rumor at Stanford, and we said, "Hmm,

01:41:23.040 | if that's true, then a lot more must also be true. So there's a whole theory out there waiting to be

01:41:29.840 | discovered that we haven't ever thought about. So let's take a look at it." And so we looked

01:41:34.720 | closer and we found out, no, actually, it's not true. But in fact, it's almost true. Namely,

01:41:43.040 | there's a very short interval of time when it's true. And if you don't happen to look at it

01:41:50.400 | during that short interval of time, then you miss it. So in other words, there'll be a period where

01:41:58.160 | there are two or three components that have loops, but they join together pretty soon.

01:42:05.440 | Okay. So-

01:42:07.360 | If you don't have a real fast shutter speed, you're going to miss that instant.

01:42:15.680 | So separate loops don't exist for long.

01:42:18.560 | That's it. Yeah. I started looking at this to make it quantitative. And the basic problem was

01:42:25.440 | to slow down the Big Bang so that I could watch it happening. I think I can explain it actually

01:42:31.840 | in fairly elementary terms, even without writing a formula-

01:42:37.200 | Let's try.

01:42:37.840 | Like Hawking would do. And so let's watch the evolution. And at first,

01:42:46.880 | these edges are coming along and they're just making things without loops, which we call trees.

01:42:52.160 | So then all of a sudden, a loop first appears. So at that point, I have one component that has a loop.

01:42:58.240 | Now I say that the complexity of a component is the number of edges minus the number of vertices.

01:43:07.600 | So if I have a loop, I have like a loop of length five, has five edges and five vertices.

01:43:16.160 | Mm-hmm.

01:43:16.660 | Or I could put a tail on that, and that would be another edge, another vertex.

01:43:22.400 | It's like a zero, one, two complexity kind of thing.

01:43:25.920 | So if the complexity is zero, we have one loop I call it, a cycle, or I call it a cyclic component.

01:43:33.440 | So a cyclic component looks like a wheel to which you attach fibers or trees.

01:43:44.880 | They go branching, but there are no more loops. There's only one loop and everything else

01:43:49.360 | feeds into that loop. And that has complexity zero. But a tree itself has complexity minus one,

01:43:57.440 | because it has, like it might have 10 vertices and nine edges to tie them together.

01:44:05.200 | So nine minus 10 is minus one. So complexity minus one is a tree. It's got to be connected.

01:44:13.200 | That's what I mean by a component. It's got to be connected.

01:44:15.200 | If I have 10 things connected, I have to have nine edges.

01:44:19.840 | Can you clarify why when complexity goes, can go above zero? I'm a little confused why.

01:44:28.880 | Right. So the complexity plus one is the number of loops. So if complexity is zero, I have one loop.

01:44:35.280 | If complexity is one, that means I have one more edge than I have vertices.

01:44:43.040 | So I might have like 11 edges and 10 vertices. So it turns, we call it a bicycle because

01:44:51.040 | it's got two loops and it's got to have two loops in it.

01:44:54.480 | Why can't it be trees just going off of the loop?

01:45:00.560 | I would need more edges than that.

01:45:03.280 | Oh, right. Right. Okay. I got it.

01:45:06.960 | So every time I get another loop, I get another excess of edges over vertices.

01:45:11.680 | I got you.

01:45:12.160 | Okay. So in other words, we start out and after I have one loop, I have one component that has

01:45:20.720 | a cycle in it. Now the next step, according to the rumor, would be that at the next step,

01:45:29.280 | I would have a bicycle in the evolution of almost all graphs. It would go from cycle to bicycle.

01:45:38.400 | But in fact, there's a certain probability it goes from cycle to two different cycles.

01:45:46.720 | And I worked out the probability was something like five out of 24.

01:45:51.760 | That's pretty high.

01:45:53.520 | It was substantial.

01:45:55.600 | But still, soon they're going to merge together almost. Okay.

01:46:01.280 | That's so cool.

01:46:03.920 | But then it splits again after you have either two or one, one. The next step is you either have

01:46:11.280 | three or you have two, one or you have one, one, one. Okay. And so I worked out the probability

01:46:17.920 | for those transitions. And I worked it out up to the first five transitions.

01:46:25.600 | And I had these strange numbers, five 24s. And I stayed up all night and about 3 a.m.

01:46:33.840 | I had the numbers computed and I looked at them and here were the denominator was something like

01:46:40.640 | 223023. So the probability was something over 23023.

01:46:51.280 | I don't know how you worked that out, but-

01:46:53.520 | I had a formula that I could calculate the probability.

01:46:56.480 | And I could find the limiting probability as n goes to infinity. And it turned out to be

01:47:02.240 | this number, but the denominator was two three. And I looked at the denominator and I said,

01:47:06.960 | wait a minute, this number factors because 1001 is equal to seven times 11 times 13.

01:47:14.560 | I had learned that in my first computer program. So 23023 is seven times 11 times 13 times 23.

01:47:28.240 | That's not a random number. There has to be a reason why those small primes appear

01:47:34.160 | in the denominator. But my thing, so all of a sudden that suggested

01:47:38.880 | another way of looking at the problem where small prime factors would occur.

01:47:45.920 | So what would that be?

01:47:48.640 | So that said, oh yeah, let me take the logarithm of this formula. And sure enough,

01:47:54.720 | it's going to simplify. And it happened. And I wouldn't have noticed it except for this

01:48:01.760 | factorization. So I go to bed and I say, oh, okay, this looks like I'm slowing down the big bang. I

01:48:08.480 | can figure out what's going on here. And the next day it turned out Bill Gates comes to Stanford to

01:48:15.040 | visit. They're trying to sell him on donating money for a new computer science building.

01:48:20.800 | Sure.

01:48:21.680 | And I said, so they gave me an appointment to talk to Bill. And I wrote down on the blackboard

01:48:28.560 | this evolutionary diagram, going from one to two, five 24ths and all this business.

01:48:34.880 | And I wrote it down. And anyway, at the end of the day, he was discussing people with the

01:48:41.760 | development office. And he said, boy, I was really impressed with what Professor Knuth said

01:48:50.240 | about this giant component. And so, I love this story because it shows that

01:48:57.200 | theoretical computer science is really worthwhile.

01:49:01.200 | Have you ever talked to Bill Gates about it since then?

01:49:05.520 | Yeah.

01:49:06.800 | That's a cool little moment in history.

01:49:09.840 | Anyway, he happened to visit on exactly the day after I had found this pattern. And that allowed

01:49:19.120 | me to crack the problem so that I could develop the theory some more and understand what's happening

01:49:27.600 | because I could now write down explicit formulas for stuff. And so, it would work not only the

01:49:37.440 | first few steps, but also the whole study, the whole process. And I worked further and further

01:49:43.600 | with two authors, co-authors. And we finally figured out that the probability that the rumor

01:49:51.520 | was true. In other words, look at the evolution of a random graph going from zero to complete

01:50:00.240 | and say, what's the probability that at every point in time, there was only one component with

01:50:06.640 | a cycle? We started with this rumor saying there's only one component with a cycle. And-

01:50:13.920 | So, the rumor was that it's 100%.

01:50:17.440 | Rumor was that it was 100%. It turned out the actual numbers is like 87%. I should remember

01:50:26.160 | the number, but I don't have it with me. But anyway, but the number, it turned out to be like

01:50:34.320 | 12 over pi squared or eight over pi. Anyway, it was a nice, it related to pi. And we could never

01:50:44.320 | done that with... So, that's the hardest problem I ever solved in my life was to prove that this

01:50:50.480 | probability is- It was proven. The probability was proven.

01:50:55.440 | Yeah. I was able to prove this, and this shed light on a whole bunch of other things about

01:51:02.080 | random graphs. That was sort of the major thing we were after.

01:51:07.600 | That's super cool. What was the connection to physics that you mentioned?

01:51:11.440 | Well, Bose-Einstein statistics is a study of how molecules bond together

01:51:18.960 | without geometry, without distance.

01:51:26.320 | You created the tech typesetting system and released it as open source. Just on that little

01:51:34.560 | aspect, why did you release it as open source? What is your vision for open source?

01:51:40.560 | Okay. Well, the word open source didn't exist at that time, but I didn't want proprietary rights

01:51:48.560 | over it because I saw how proprietary rights were holding things back. In the late '50s,

01:51:58.640 | people at IBM developed a language called Fortran. They could have kept it proprietary. They could

01:52:05.120 | have said, "Only IBM can use this language. Everybody else has to." But they didn't. They

01:52:11.280 | said, "Anybody who can translate Fortran into the language of their machines is allowed to

01:52:20.000 | make Fortran compilers, too." On the other hand, in the typography industry, I had seen

01:52:28.560 | a lot of languages that were developed for composing pages. Each manufacturer had his own

01:52:37.680 | language for composing pages. That was holding everything back because people

01:52:43.600 | were tied to a particular manufacturer, and then a new equipment is invented a year later. But

01:52:50.880 | printing machines, they have to expect to amortize the cost over 20, 30 years.

01:52:55.600 | So you didn't want that for tech?

01:52:58.640 | I didn't need the income. I already had a good job. People were buying enough books that it would

01:53:18.880 | bring me plenty of supplemental income for everything my kids needed for education,

01:53:25.680 | whatever. So there was no reason for me to try to maximize income any further. Income is

01:53:32.720 | sort of a threshold function. If you don't have enough, you're starving. But if you get over the

01:53:39.520 | threshold, then you start thinking about philanthropy or else, or trying to take it

01:53:45.200 | with you. But anyway, my income was over the threshold. So I didn't need to keep it. And so,

01:53:56.240 | I specifically could see the advantage of making it open for everybody.

01:54:02.160 | Do you think most software should be open?

01:54:05.120 | So I think that people should charge for non-trivial software, but not for trivial software.

01:54:13.040 | Yeah, you give an example of, I think, Adobe Photoshop versus GIMP on Linux,

01:54:18.960 | as Photoshop has value.

01:54:21.680 | So it's definitely worth paying for all this stuff. I mean, well, they keep adding

01:54:31.520 | stuff that my wife and I don't care about, but somebody obviously does. But they have

01:54:41.920 | built in a fantastic undo feature, for example, in Photoshop, where you can go through a sequence

01:54:52.400 | of a thousand complicated steps on graphics, and it can take you back anywhere in that sequence.

01:54:58.400 | Yeah, that's a long history.

01:55:00.080 | With really beautiful algorithms. I mean, yeah, it's...

01:55:03.200 | Oh, that's interesting. I didn't think about what algorithm. It must be some kind of efficient

01:55:07.760 | representation.

01:55:08.400 | It's really, yeah, no. I mean, there's a lot of really subtle Nobel Prize class creation

01:55:15.680 | of intellectual property in there. And with patents, you get a limited time to... I mean,

01:55:29.440 | eventually, the idea of patents is that you publish so that it's not a trade secret.

01:55:37.040 | That said, you've said that I currently use Ubuntu Linux on a standalone laptop.

01:55:44.000 | It has no internet connection. I occasionally carry flash memory drives between the machine

01:55:50.160 | and the Macs that I use for network surfing and graphics. But I trust my family jewels

01:55:56.880 | only to Linux. Why do you love Linux?

01:56:00.880 | The version of Linux that I use is stable. Actually, I'm going to have to upgrade one

01:56:07.040 | of these days, but...

01:56:07.840 | To a newer version of Ubuntu?

01:56:10.320 | Yeah, I'll stick with Ubuntu. But right now, I'm running something that doesn't support

01:56:17.360 | a lot of the new software. The last stable... I don't remember the number, like 14. Anyway,

01:56:27.360 | it's quite... And I'm going to get a new computer. I'm getting new solid state memory instead of a

01:56:36.320 | hard disk.

01:56:36.800 | Yeah, the basics. Well, let me ask you, sticking on the topic of tech,

01:56:42.800 | when thinking about beautiful typography, what is your favorite letter, number, or symbol?

01:56:55.040 | I know, I know, ridiculous question, but is there a...

01:56:57.440 | Let me show you here.

01:56:59.440 | Look at the last page.

01:57:06.560 | The very end of the index.

01:57:12.320 | What is that?

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

01:57:21.680 | Did you say Dr. Seuss gave a name to that?

01:57:24.480 | Dr. Seuss, this is S-E-U-S-S. He wrote children's books in the '50s, '40s and '50s.

01:57:33.680 | Wait, are you talking about Cat in the Hat?

01:57:36.560 | Cat in the Hat, yeah. That's it, yeah.

01:57:39.680 | I like how you hit the spelling.

01:57:41.120 | On Beyond Zebra. Did it get to the Soviet Union?

01:57:46.080 | Yeah, Dr. Seuss did not come to the Soviet Union, but...

01:57:54.320 | Since you... Oh, actually, I think he did, actually, a little bit when we were...

01:57:58.240 | That was a book, maybe Cat in the Hat or Green Eggs and Ham, I think was used to learn English.

01:58:10.080 | Okay.

01:58:11.200 | So I think it made it in that way.

01:58:12.880 | Okay. I didn't like those as much as Bartholomew Cubbins, but I used to know

01:58:21.760 | Bartholomew Cubbins by heart when I was young.

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

01:58:28.800 | He has a name for it at the end of his book on Beyond Zebra.

01:58:31.920 | Who made it?

01:58:33.440 | He did.

01:58:34.720 | He did. So there's... It looks like a bunch of vines. Is that symbol existent?

01:58:43.120 | By the way, he made a movie in the early '50s. I don't remember the name of the movie now.

01:58:50.960 | You can probably find it easily enough. But it features dozens and dozens of pianos all playing

01:58:57.440 | together at the same time. But all the scenery is sort of based on the kind of artwork that

01:59:05.120 | was in his books and the fantasy based of Soosland or something. And I saw the movie

01:59:15.920 | only once or twice, but it's quite... I'd like to see it again.

01:59:20.400 | That's really fascinating that you gave them... They gave them shout out here.

01:59:26.960 | Okay. Is there some elegant basic symbol that you're attracted to?

01:59:32.160 | Something that gives you pleasure? Something used a lot? Pi?

01:59:39.600 | Pi, of course. I try to use pi as often as I can when I need a random example,

01:59:47.920 | because it doesn't have any known characters. So for instance, I don't have it here to show you,

01:59:59.440 | but do you know the game called Masyu? M-A-S-Y-U? No. It's a great recreation. I mean,

02:00:11.520 | Sudoku is easier to understand, but Masyu is more addictive. You have black and white stones like

02:00:21.280 | on a go board, and you have to draw a path that goes straight through a white stone and

02:00:28.800 | makes a right angle turn at the black stone. And it turns out to be really, really nice puzzle

02:00:36.160 | because it doesn't involve numbers, but it's visual, but it's really pleasant to play with.

02:00:43.760 | So I wanted to use it as example in art of computer programming. And I have

02:00:52.160 | exercise on how to design cool Masyu puzzles. You can find that on Wikipedia, certainly,

02:00:59.120 | as an example, M-A-S-Y-U. And so I decided I would take pi, the actual image of it, and I had pixels,

02:01:12.880 | and I would put a stone wherever it belongs in the letter pi, in the Greek letter pi.

02:01:20.080 | But the problem was find a way to make some of the stones white, some of the stones black,

02:01:26.400 | so that there's a unique solution to the Masyu puzzle. That was a good test case for my algorithm

02:01:33.680 | on how to design Masyu puzzles because I insisted in advance that the stones had to be placed in

02:01:40.400 | exactly the positions that make the letter pi, make a Greek letter pi. All right. That's cool.

02:01:48.720 | And it turned out there was a unique way to do that. And so pi is a source of examples where I

02:01:59.520 | can prove that I'm starting with something that isn't canned. And most recently, I was writing

02:02:07.680 | about something called graceful graphs. Graceful graphs is the following. You have a graph that has

02:02:16.880 | M edges to it. And you attach numbers to every vertex in the following way. So every time you

02:02:27.120 | have an edge between vertices, you take the difference between those numbers. And that

02:02:34.080 | difference has got to be, I'll tell you what edge it is. So one edge, two numbers will be one apart.

02:02:41.360 | There'll be another edge where the numbers are two apart. And so it's a great computer problem.

02:02:47.920 | Can you find a graceful way to label a graph? So I started with a graph that I use for

02:02:55.600 | an organic graph, not a mathematically symmetric graph or anything. And I take

02:03:04.160 | the 49 states of the United States. The edges go from one state to the next state. So for example,

02:03:12.000 | California, be next to Oregon, Nevada, Arizona. And I include District of Columbia. So I have 49.

02:03:24.400 | I can't get Alaska and Hawaii in there because they don't touch. You have to be able to drive

02:03:30.480 | from one to the other. So is there a graceful labeling of the United States? Each state gets

02:03:37.200 | a number. And then if California is number 30 and Oregon is number 11, that edge is going to be

02:03:44.480 | number 19. The difference between those. So is there a way to do this for all the states? And

02:03:52.160 | so I was thinking of having a contest for people to get it as graceful as they could.

02:04:00.960 | But my friend Tom Rukiki actually solved the problem by proving that. I mean, I was able to

02:04:08.400 | get it down within seven or something like that. He was able to get a perfect solution.

02:04:13.920 | The actual solution or to prove that a solution exists?

02:04:17.200 | More precisely, I had figured out a way to put labels on so that all the edges were labeled

02:04:25.440 | somewhere between one and 117. But there were some gaps in there because I should really have

02:04:32.240 | gone from one to 105 or whatever the number is. So I gave myself too much, a lot of slack. He did

02:04:40.880 | it without any slack whatsoever, perfect graceful labeling. And so I call out the contest because

02:04:49.520 | problems already solved and too easy in a sense because Tom was able to do it in an afternoon.

02:04:55.280 | He, sorry, he gave the algorithm or for this particular?

02:04:58.080 | For the United States.

02:05:00.800 | For the United States.

02:05:01.520 | This problem is incredibly hard. I mean-

02:05:04.960 | For the general.

02:05:05.600 | General.

02:05:05.920 | Okay. But it's like coloring.

02:05:08.320 | But it was very lucky that it worked for the United States.

02:05:10.560 | I think. But the theory is still very incomplete. But anyway, then Tom came back a couple of days

02:05:18.800 | later and he had been able to not only find a graceful labeling, but the label of Washington

02:05:26.000 | was 31. The label of Idaho was 41 following the digits of pi. Going across the topic,

02:05:38.080 | the United States, he has the digits of pi perfectly.

02:05:41.280 | Did he do it on purpose?

02:05:42.320 | He was able to still get a graceful labeling with that extra thing.

02:05:48.000 | What?

02:05:49.040 | Wow.

02:05:49.360 | Wow.

02:05:51.040 | It's a miracle. Okay. But I like to use pi in my book, you see, and this is the-

02:06:00.960 | All roads lead to pi.

02:06:04.560 | Yeah.

02:06:05.120 | Somehow often hidden in the middle of like the most difficult problems.

02:06:11.520 | Can I ask you about productivity?

02:06:15.440 | Productivity.

02:06:17.680 | Yeah. You said that, "My scheduling principle is to do the thing I hate most on my to-do list.

02:06:26.240 | By week's end, I'm very happy." Can you explain this process to a productive life?

02:06:32.800 | Oh, I see. But all the time I'm working on what I don't want to do, but still, I'm glad to have

02:06:41.120 | all those unpleasant tasks finished.

02:06:42.960 | Yes. Is that something you would advise to others?

02:06:46.720 | Yeah. I don't know how to say it. During the pandemic, I feel my productivity actually

02:06:54.880 | went down by half because I have to communicate by writing, which is slow. I don't like to send

02:07:07.600 | out a bad sentence, so I go through and reread what I've written and edit and fix it. So everything

02:07:14.320 | takes a lot longer when I'm communicating by text messages instead of just together with somebody

02:07:25.520 | in a room. It's also slower because the libraries are closed and stuff.

02:07:30.960 | But there's another thing about scheduling that I learned from my mother that I should

02:07:35.680 | probably tell you, and that is different from what people in robotics field do, which is called

02:07:42.880 | planning. So she had this principle that was, "See something that needs to be done and do it."

02:07:51.440 | Instead of saying, "I'm going to do this first, and I'm going to do this first," just, you know...

02:07:59.840 | Just do it.

02:08:03.040 | Oh, yeah. Pick this up, you know.

02:08:04.160 | But you're... At any one moment, there's a set of tasks that you can do, and you're saying a

02:08:10.480 | good heuristic is to do the one you want to do least.

02:08:15.040 | Right. The one I haven't got any good reason to... I'll never be able to do it any better than I am

02:08:24.320 | now. There are some things that I know, if I do something else first, I'll be able to do that one

02:08:32.560 | better. But there's some that are going to be harder because, you know, I've forgotten some of

02:08:39.280 | the groundwork that went into it or something like that. So I just finished a pretty tough part of

02:08:46.080 | the book, and so now I'm, you know, doing the parts that are more fun. But the other thing is,

02:08:56.240 | as I'm writing the book, of course, I want the reader to think that I'm happy all the time I'm

02:09:02.080 | writing the book. You know, it's upbeat. I can have humor. I can say, "This is cool." You know,

02:09:09.920 | "Wow." And this. I have to disguise the fact that it was painful in any way to come up with this.

02:09:18.240 | The road to that excitement is painful. Yeah, it's laden with pain. Okay. Is there...

02:09:23.840 | You've given some advice to people before, but can you...

02:09:30.880 | You give me too much credit, but anyway, this is my turn to say things that I believe. But

02:09:38.640 | I want to preface it by saying I also believe that other people do a lot of these things

02:09:48.320 | much better than I do, so I can only tell you my side of it.

02:09:53.120 | So can I ask you to give advice to young people today, to high school students,

02:10:01.120 | to college students, whether they're geeks or the other kind, about how to live a life

02:10:08.480 | they can be proud of, how to have a successful career, how to have a successful life?

02:10:16.240 | It's always the same as I've said before, I guess, not to do something because it's trendy,

02:10:25.280 | but it's something that you personally feel that you were called to do,

02:10:30.640 | rather than somebody else expects you to do. How do you know you're called to do something?

02:10:37.600 | You try it and it works or it doesn't work. I mean, you learn about yourself.

02:10:44.800 | Life is a binary search. You try something and you find out, oh yeah, I have a background that

02:10:49.280 | helped me with this, or maybe I could do this if I worked a little bit harder. But you try

02:10:57.920 | something else and you say, well, I have really no intuition for this and it looks like it doesn't

02:11:05.280 | have my name on it. Was there advice along the way that you got about what you should and shouldn't

02:11:13.360 | work on, or do you just try to listen to yourself? Yeah, I probably overreacted another way. When

02:11:19.280 | something, when I see everybody else going some way, I probably say, hmm, too much competition.

02:11:28.400 | But mostly I played with things that were interesting to me. And then later on I found,

02:11:40.320 | actually the most important thing I learned was how to be interested in almost anything.

02:11:44.640 | I mean, not to be bored. It hurts. It makes me very sad when I see kids talking to each other

02:11:52.480 | and they say, that was boring. And to me, a person should feel upset if he had to admit that he

02:12:07.200 | wasn't able to find something interesting. It's a skill. They're saying, I haven't learned how to

02:12:15.200 | enjoy life. I have to have somebody entertain me instead of...

02:12:20.000 | That's really interesting. It is a skill. David Foster Wallace, I really like the thing he says

02:12:28.320 | about this, which is the key to life is to be unboreable. And I do really like you saying that

02:12:35.120 | it's a skill, because I think that's really good advice, which is if you find something boring,

02:12:41.840 | that's not, I don't believe it's because it's boring. It's because you haven't developed the

02:12:50.640 | skill, how to find the beauty in it, how to find the fun in it. That's a really good point.

02:12:57.920 | Sometimes it's more difficult than others to do this. I mean, during the COVID,

02:13:05.040 | lots of days when I never saw another human being, but I still find other ways to...

02:13:14.560 | It still was a pretty fun time.

02:13:17.920 | Yeah. I came a few minutes early today and I walked around Foster City. I didn't know

02:13:28.080 | what was going on in Foster City. I saw some beautiful flowers at the nursery at Home Depot

02:13:33.360 | a few blocks away.

02:13:34.240 | Life is amazing. It's full of amazing things like this. Yeah. Sometimes I'll sit there and

02:13:43.040 | just stare at a tree. Nature is beautiful. Let me ask you the big ridiculous question. I don't think

02:13:49.680 | I asked you last time. So I have to ask this time in case you have a good answer. What is the meaning

02:13:55.200 | of life? Our existence here on earth, the whole thing. No, no, you can't. I will not allow you to

02:14:09.200 | try to escape answering this question. You have to answer definitively because there's surely,

02:14:16.560 | surely, Don Knuth, there must be an answer.

02:14:19.360 | What is the answer? Is it 42?

02:14:22.480 | Yes. Well, I don't think it's in numerical. That's the SDS.

02:14:26.000 | That was in Zen. Okay. But all right. So anyway, it's only for me, but I personally

02:14:37.040 | think of my belief that God exists, although I have no idea what that means. But I believe that there

02:14:49.280 | is something beyond human capabilities. It might be some AI, but whatever it is, but whatever. But

02:15:07.280 | I do believe that there is something that goes beyond the realm of human understanding,

02:15:17.680 | but that I can try to learn more about how to resonate with whatever that being would like me to

02:15:30.240 | do. So you think you can have occasional glimpses of that being? I strive for that. Not that I

02:15:40.960 | ever think I'm going to get close to it, but it's not for me. It's saying, what should I do

02:15:48.720 | that that being wants me to do? I'm trying to ask,

02:15:55.040 | I mean, does that being want me to be talking to Lex Friedman right now? And I said, yes. Okay.

02:16:06.640 | Thank you.

02:16:09.600 | Well, thank you. But what I'm trying to say is, I'm not trying to say, of all the

02:16:17.440 | strategies I could choose or something, which one? I try to do it not strategically, but I try to

02:16:26.160 | imagine that I'm following somebody's wishes.

02:16:32.560 | Even though you're not smart enough to...

02:16:36.160 | To know what they are.

02:16:37.280 | Yeah. That funny little dance.

02:16:39.600 | Well, I mean, this AI or whatever, it probably is smart enough to help to give me clues.

02:16:47.840 | And to make the whole journey from clue to clue a fun one.

02:16:56.160 | Yeah. I mean, as so many people have said, it's the journey, not the destination.

02:17:01.520 | And people live through crises, help each other. Things come up, history repeats itself.

02:17:10.880 | You try to say in the world today, is there any government that's working? I read history. I know

02:17:20.560 | that things were...

02:17:21.200 | They were a lot worse in many ways.

02:17:28.320 | There's a lot of bad things all the time. And I read about, I look at things and people had

02:17:36.080 | good ideas and they were working on great projects. And then I know that it didn't succeed,

02:17:41.760 | though, in the end. But the new insight I've gotten, actually, in that way was, I was reading...

02:17:48.240 | What book was I reading recently? It was by Ken Follett, and it was called The Man from St.

02:17:56.560 | Petersburg. But it was talking about the prequel to World War I. And Winston Churchill,

02:18:04.240 | according to this book, sees that Germany has been spending all its gold reserves

02:18:10.960 | building up a huge military. And there's no question that if Germany would attack England,

02:18:18.240 | that England would be wiped out. So he wants Russia to help to attack Germany from the other

02:18:26.800 | side, because Germany doesn't have enough of an army to be fighting two wars at one.

02:18:32.000 | Okay, now, then there's an anarchist in Russia, who sees that wars are

02:18:44.320 | something that leaders start, but actually people get killed. And so he wants to stop

02:18:52.720 | any alliance between England and Russia, because that would mean that thousands and thousands of

02:19:00.800 | people in Russia would be killed that wouldn't be otherwise killed. All right, and so his life's goal

02:19:10.480 | is to assassinate a Russian prince who's visiting England, because that will make,

02:19:17.120 | will mean the Tsar will not form the alliance. All right. So we have this

02:19:21.840 | question about what should the government do? Should it actually do something that will lead to,

02:19:30.240 | you know, is the war inevitable? Or is there a way to have peace? And it struck me that if I were

02:19:39.360 | in a position of responsibility for people's lives, in most cases, I wouldn't have any confidence that

02:19:47.680 | any of my decisions were good. That these questions are too hard, probably for any human

02:19:55.280 | being, but certainly for me. Well, I think coupling the not being sure that the decisions are right,

02:20:05.760 | so that that's actually a really good thing, coupled with the fact that you do have to make

02:20:11.440 | a decision and carry the burden of that. And ultimately, I have faith in human beings,

02:20:19.840 | in the great leaders to arise and help build a better world. I mean, that's the hope of democracy.

02:20:28.720 | Yeah, Ben, let's hope that we can enhance their abilities with algorithms.

02:20:35.680 | Well put, Don. It's such a huge honor. You've been an inspiration to me and to millions for

02:20:46.160 | such a long time. Thank you for spending your really valuable time with me. Once again,

02:20:52.000 | it's a huge honor. I really enjoyed this conversation.

02:20:55.840 | Thanks for listening to this conversation with Donald Knuth. To support this podcast,

02:21:00.160 | please check out our sponsors in the description. And now, let me leave you with some words from

02:21:05.280 | Don Knuth himself. Science is what we understand well enough to explain to a computer. Art is

02:21:12.880 | everything else we do. Thank you for listening. I hope to see you next time.

02:21:18.640 | Bye.

02:21:19.600 | Bye.

02:21:20.640 | Bye.

02:21:21.600 | Bye.

02:21:21.680 | [BLANK_AUDIO]

Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life | Lex Fridman Podcast #219

Chapters