Transcript
00:00:00 The following is a conversation with Donald Knuth, his second time on this podcast.
00:00:05 Don is a legendary computer scientist, Turing Award winner, father of algorithm analysis,
00:00:12 author of The Art of Computer Programming, creator of tech that led to late tech, and
00:00:19 one of the kindest and most fascinating human beings I’ve ever got a chance to talk to.
00:00:23 I wrote him a letter a long time ago, he responded, and the rest, as they say, is history.
00:00:30 We’ve interacted many times since then, and every time has been joyful and inspiring.
00:00:36 To support this podcast, please check out our sponsors in the description.
00:00:40 This is the Lex Friedman Podcast, and here is my conversation with Donald Knuth.
00:00:46 Don Knuth, your first large scale program, you wrote it in IBM 650 Assembler in the summer of 1957.
00:00:54 I wrote it in decimal machine language. I didn’t know about Assembler until a year later.
00:00:59 But the year, 1957, and the program is tic tac toe.
00:01:04 Yeah, I might have learned about Assembler later that summer, I probably did. In 1957,
00:01:09 hardly anybody had heard of Assemblers. You looked at the user manuals,
00:01:12 and how would you write a program for this machine? It would say 69, which meant load
00:01:21 the distributor, and then you would give the address of the number you wanted to load into
00:01:25 the distributor. Yesterday, my friend Doug Spicer at the Computer History Museum sent me a link to
00:01:34 something that just went on YouTube. It was IBM’s progress report from 1956, which is very
00:01:41 contemporary with 1957. In 1956, IBM had donated to Stanford University an IBM 650, one of the first
00:01:52 ones, when they showed a picture of the assembly line for IBM 650s, and they said, this is number
00:01:58 500 or something coming off the assembly line. I had never seen so many IBM 650s I did in this
00:02:05 movie that’s on YouTube now. It showed the picture from Stanford. They said, look, we donated one of
00:02:19 these to Stanford, one to MIT, and they mentioned one other college. In December of 1956, they
00:02:26 donated to my university, Case Tech. Anyway, they showed a picture then of a class session where a
00:02:36 guy was teaching programming, and on the blackboard, it said 69, 8,000. He was teaching them how to
00:02:45 write code for this IBM 650, which was in decimal numbers. The instructions were 10 decimal digits.
00:02:56 You had two digits that said what to do, four digits to say what to do it to, and four more
00:03:05 digits to say where to get your next instruction. And there’s a manual that describes what each of
00:03:10 the numbers mean. If the manual had been well written, I probably never would have gone into
00:03:16 computer science, but it was so badly written, I figured that I must have a talent for it because
00:03:22 I’m only a freshman and I could write a better manual. That’s what you did.
00:03:27 And so I started working at the computer center and wrote some manuals then. But this was the
00:03:41 way we did it. And my first program then was June of 1957. The Tic Tac Toe?
00:03:48 No, that was the second program. The first, the third program. The first program was
00:03:52 factoring a number. So you dial a number on the switches. I mean, you sat at this big mainframe
00:04:05 and you turn the dials, set a number, and then it would punch out the factors of that number
00:04:12 on cards. So that’s the input, is the number?
00:04:15 The input was, yeah, the input was a number, a tentative number. And the output was its factors.
00:04:26 And I wrote that program. I still have a copy of it somewhere.
00:04:34 How many lines of code? Do you remember?
00:04:36 Well, yeah, it started out as about 20, but then I kept having to debug it.
00:04:40 And I discovered debugging, of course, when I wrote my first program.
00:04:45 What does debugging look like on a program with just all numbers?
00:04:50 Well, you sit there and you, I don’t remember how I got it into the machine, but I think there was
00:04:55 a way to punch it on cards. So each instruction would be one card. Or maybe I could get seven
00:05:02 instructions on a card, eight instructions. I don’t know. But anyway, so I’m sitting there
00:05:06 at the console of the machine. I mean, I’m doing this at night when nobody else is around.
00:05:10 Of course.
00:05:11 And so you have one set of switches where you dial the number I’m inputting, but there’s another
00:05:17 switch that says, okay, now execute one instruction and show me what you did. Or there was another four
00:05:26 switches that say, stop if you get to that instruction. So I can say, now go until you
00:05:33 get there again and watch. So I could watch, it would take that number and it would divide it by
00:05:39 two. And if there’s no remainder, then okay, two is a factor. So then I work on it. But if not
00:05:48 divisible by two, divide by three. Keep trying until you know you’re at the end.
00:05:55 And you would find a bug if you were just surprised that something weird happened?
00:06:02 Well, certainly. I mean, first of all, I might have
00:06:05 tried to divide by one instead of two. You go off by one error, as people make all the time.
00:06:11 Yes.
00:06:11 But maybe I go to the wrong instruction. Maybe I left something in a register that I shouldn’t have
00:06:18 done. But the first bugs were pretty… Probably on the first night, I was able to get the factors
00:06:26 of 30 as equal to two, three, and five. Okay.
00:06:29 Sorry to interrupt. So you’re sitting there late at night.
00:06:36 Yeah.
00:06:36 So it feels like you spent many years late at night working on a computer.
00:06:42 Oh, yeah.
00:06:43 So what’s that like? So most of the world is sleeping. And you have to be there at night
00:06:49 because that’s when you get access to the computer.
00:06:51 Between my freshman and sophomore year, I didn’t need sleep. I used to do all nighters.
00:06:56 When I was in high school, I used to do the whole student newspaper every Monday night.
00:07:04 I would just stay up all night and it would be done on Tuesday morning.
00:07:12 I didn’t get ulcers and stuff like that until later.
00:07:18 I don’t know if you know Rodney Brooks.
00:07:19 Rod Brooks, of course.
00:07:20 Yeah. He told me a story that he really looked up to you. He was actually afraid of you.
00:07:29 Well, vice versa, I must say.
00:07:32 But he tells a story when you were working on tech that they screwed up something with
00:07:37 a machine. I think this might have been MIT. I don’t know. And you were waiting for them
00:07:42 to fix the machine so you can get back to work late at night.
00:07:47 That happened all the time.
00:07:49 He was really intimidated. He’s like, Dr. Knuth is not happy with this.
00:07:54 That’s interesting. But no, the machine at Stanford AI Lab was down an awful lot because
00:08:05 they had many talented programmers changing the operating system every day.
00:08:09 So the operating system was getting better every day, but it was also crashing.
00:08:14 So I wrote almost the entire manual for tech during downtime of that machine.
00:08:23 But that’s another story.
00:08:24 Well, he was saying it’s a hardware problem. They tried to fix it and they reinserted
00:08:30 something and smoke was everywhere.
00:08:32 Oh, wow. Well, that didn’t happen as often as the operating system.
00:08:38 It’s a funny story because he was saying there’s this tall Don Knuth that I look up to
00:08:44 and there was pressure to fix the computer. It’s funny.
00:08:51 The kind of things we remember that stick in our memory.
00:08:54 Well, okay. Yeah. Well, I could tell you a bunch of Rod Brooks stories too, but let’s
00:09:00 go back to the 650. So I’m debugging my first program and I had more bugs in it than a number
00:09:12 of lines of code. I mean, the number of lines of code kept growing. And let me explain.
00:09:17 So I had to punch the answers on cards. So suppose I’m factoring the number 30, then
00:09:26 I got to put two somewhere on the card. I got to put a three somewhere on the card.
00:09:31 I got to put a five somewhere on the card. And here’s my first program. I probably screwed up
00:09:37 and it fell off the edge of the card or something like that. But I didn’t realize that there are
00:09:44 some tentative numbers that have more than eight factors. And the card has only 80 columns. And so
00:09:53 I need 10 columns for every factor. So my first program didn’t take account for the fact that I
00:09:58 would have to punch more than one card. My first program just lined stuff up in memory and then
00:10:03 punched the card. So by the time I finished, I had to deal with lots of things. Also,
00:10:14 if you put a large prime number in there, my program might have sat there for 10 minutes.
00:10:20 The 650 was pretty slow. And so it would sit there spinning its wheels and you wouldn’t know
00:10:24 if it was in a loop or whatever. You said 10 digit?
00:10:26 10 digits. Yeah. So I think the largest is sort of 999999997 or something like that.
00:10:36 That would take me a while for that first one. Anyway, that was my first program.
00:10:40 Well, what was your goal with that program? Was there something you were hoping to find a large
00:10:46 prime maybe or the opposite? No, my goal was to see the lights flashing and understand how this
00:10:54 magical machine would be able to do something that took so long by hand. So what was your second
00:10:59 program? My second program was a converted number from binary to decimal or something like that. It
00:11:08 was much simpler. It didn’t have that many bugs in it. My third program was tic tac toe.
00:11:14 Yeah. And it had some machines. So the tic tac toe program is interesting on many levels,
00:11:20 but one of them is that it had some you can call machine learning in it.
00:11:26 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 changed from computer science to machine learning. But anyway, it was my first experience with
00:11:42 machine learning. Okay. So here we had… Yeah. How does the program… Well, first of all,
00:11:46 what is the problem you were solving? What is tic tac toe? What are we talking about? And then
00:11:54 how was it designed? Right. So you’ve got a three by three grid and each
00:12:03 can be in three states. It can be empty or it can have an X or an O. Yeah. All right. So three to
00:12:08 the ninth is a… Well, how big is it? I should know. But it’s 81 times three. So anyway, eight
00:12:26 is like two to the third. And so that would be like two to the sixth. But that would be 64.
00:12:35 Then you have to… Anyway, I love how you’re doing the calculation. So it’s a lot of… Anyway,
00:12:41 the three comes from the fact that it’s either empty, an X or an O. Right. And the 650 was a
00:12:49 machine that had only two thousand ten digit words. You go from zero zero zero zero to one
00:13:00 nine nine nine and that’s it. And each word you have a ten digit number. So that’s not many bits.
00:13:09 I mean, I got to have… In order to have a memory of every position I’ve seen,
00:13:14 I need three to the ninth bits. Okay. But it was a decimal machine too. It didn’t have bits.
00:13:21 But it did have strange instruction where if you had a ten digit number, but all the digits were
00:13:29 either eight or nine, you’d be eight, nine, nine, eight or something like that. You could make a
00:13:38 test whether it was eight or nine. That was one of the strange things IBM engineers put into the
00:13:43 machine. I have no idea why. Well, hardly ever used. But anyway, I needed one digit for every
00:13:51 position I’d seen. Zero meant it was a bad position. Nine meant it was good position.
00:13:57 And I think I started out at five or six. But if you win a game, then you increase the value of
00:14:06 that position for you, but you decrease it for your opponent. But I had that much total memory
00:14:18 for every possible position was one digit. And I had a total of 20,000 digits, which had to also
00:14:25 include my program and all the logic and everything, including how to ask the user what the moves are
00:14:34 and things like this. So I think I had to work it out. Every position in tic tac toe is equivalent
00:14:41 to roughly eight others because you can rotate the board, which gives you a factor of four,
00:14:49 and you can also flip it over. And that’s another factor too. So I might have needed only three to
00:14:55 the ninth over eight positions plus a little bit. But anyway, that was a part of the program to
00:15:05 squeeze it into this tiny… So you tried to find an efficient representation that took
00:15:11 account for that kind of rotation. I had to, otherwise I couldn’t do the learning.
00:15:18 But I had three parts to my tic tac toe program. And I called it brain one, brain two, and brain
00:15:24 three. So brain one just played at random. It’s your turn. Okay. You got to put an X somewhere.
00:15:39 It has to go in an empty space, but that’s it. Okay. Choose one and play it. Brain two
00:15:48 had a canned routine. And I think it also… Maybe it assumed you were the first player,
00:15:59 or maybe it allowed you to be first. I think you’re allowed to be either first or second,
00:16:03 but had a canned built in strategy known to be optimum for tic tac toe. Before I forget,
00:16:09 by the way, I learned many years later that Charles Babbage had thought about programming
00:16:18 tic tac toe for his dream machine that he was never able to finish.
00:16:23 Wow. So that was the program he thought about.
00:16:26 More than 100 years ago. He did that. Okay. And I had, however, been influenced by a
00:16:37 demonstration at the Museum of Science and Industry in Chicago. It’s like Boston Science
00:16:42 Museum. I think Bell Labs had prepared a special exhibit about telephones and relay technology,
00:16:50 and they had a tic tac toe playing machine as part of that exhibit. So that had been one of my…
00:17:00 Something I’d seen before I was a freshman in college and inspired me to see if I could
00:17:05 write a program for it. Okay. So anyway, I had brain one, random, knowing nothing. Brain two,
00:17:13 knowing everything. Then brain three was the learning one. And I could play brain one against
00:17:22 brain one, brain one against brain two, and so on. And so you could also play against the user,
00:17:28 against the live users. So I started going, the learning thing, and I said, okay, take two random
00:17:37 people just playing tic tac toe knowing nothing. And after about… I forget the number now, but
00:17:49 it converged after about 600 games to a safe draw. The way my program learned was actually,
00:17:57 it learned how not to make mistakes. It didn’t try to do anything for winning,
00:18:04 it just tried to say not losing. So that was probably because of the way I designed the
00:18:10 learning thing. I could have had a different reinforcement function that would reward brilliant
00:18:18 play. And if I took a novice against a skilled player, it was able to learn how to play a good
00:18:29 game. And that was really my… But after I finished that, I felt I understood programming.
00:18:38 Yeah. Did a curiosity and interest in learning systems persist for you?
00:18:48 So why did you want brain three to learn? Yeah. I think naturally, we’re talking about
00:18:58 Rod Brooks. He was teaching all kinds of very small devices to learn stuff. If a leaf drops
00:19:08 off of a tree, he was saying something, well, it learns if there’s wind or not.
00:19:17 But I mean, he pushed that a little bit too far. But he said he could probably train some little
00:19:22 mini bugs to scour out dishes if he had enough financial support. I don’t know.
00:19:28 Can I ask you about that? He also mentioned that during those years, there was discussion
00:19:39 inspired by Turing about computation, of what is computation.
00:19:45 Yeah. I never thought about any stuff like that. That was way too philosophical. I was a freshman
00:20:00 after all. I was pretty much a machine.
00:20:07 So it’s almost like, yeah, I got you. It’s a tinkering mindset, not a philosophical mindset.
00:20:12 Yeah. It was just exciting to me to be able to control something, but not to say, am I solving
00:20:21 a big problem or something like that? Or is this a step for humankind? No, no way.
00:20:28 When did you first start thinking about computation in the big sense? Like the
00:20:34 universal Turing machine? I had to take classes on computability when I was a senior. So we read
00:20:47 this book by Martin Davis. Yeah, this is cool stuff. But I learned about it because I needed
00:20:53 to pass the exams. But I didn’t invent any of that boring stuff. But I had great fun playing
00:21:00 with the machine. I wrote programs because it was fun to write programs and get this.
00:21:11 I mean, it was like watching miracles happen.
00:21:15 You mentioned in an interview that when reading a program, you can tell when the author of the
00:21:22 program changed. How the heck can you do that? Like, what makes a distinct style for a programmer,
00:21:31 do you think? You know, there’s different Hemingway has a style of writing versus James Joyce or
00:21:39 something. Yeah, those are pretty easy to imitate. But it’s the same with music and whatever.
00:21:45 During the pandemic, I spent a lot more time playing the piano. And I found something that
00:21:55 I’d had when I was taking lessons before I was a teenager. And it was Yankee Doodle
00:22:05 who played in the style of… You had Beethoven and you had Debussy and Chopin, and the last one
00:22:16 was Gershwin. And I played over and over again. I thought it was so brilliant. But it was so easy.
00:22:26 But also to appreciate how this author, Mario, somebody or other, had been able to reverse
00:22:35 engineer the styles of those composers. But now, specifically to your question, I mean, there would
00:22:43 be… It was pretty obvious in this program I was reading. It was a compiler and it had been written
00:22:53 by a team at Carnegie Mellon. And I have no idea which program was responsible for it. But you
00:23:03 would get to a part where the guy would just not know how to move things between registers very
00:23:09 efficiently. And so everything that could be done in one instruction would take three or something
00:23:16 like that. That would be a pretty obvious change in style. But there were also flashes of brilliance
00:23:23 where you could do in one instruction. Normally, I used two because you knew enough about the way
00:23:29 the machine worked that you could accomplish two goals in one step. So it was mostly the
00:23:37 brilliance of the concept more than the semicolons or the use of short sentences versus long sentences
00:23:45 or something like that. So you would see the idea in the code and you could see the different style
00:23:50 of thinking expressed in the code. Right. It was stylistic. I mean, I could identify authors by
00:23:57 their by the amount of technical aptitude they had, but not by the style in the sense of
00:24:07 rhythm or something like that. So if you think about Mozart, Beethoven, Bach,
00:24:11 if somebody looked at Don Knuth code, would they be able to tell that this
00:24:19 is a distinct style of thinking going on here? What do you think?
00:24:23 And what would be the defining characteristic of the style?
00:24:28 Well, my code now is literate programming. So it’s a combination of English and C mostly. But
00:24:37 if you just looked at the C part of it, you would also probably notice that I use a lot of global
00:24:46 variables that other people don’t. And I expand things in line more than instead of calling.
00:24:56 Anyway, I have different subset of C that I use.
00:25:00 Okay. But that’s a little bit stylistic.
00:25:03 But with literate programming, you alternate between English and C or whatever.
00:25:10 And by the way, people listening to this should look up literate programming. It’s
00:25:14 very interesting concept that you proposed and developed over the years.
00:25:21 Yeah. That’s the most significant thing, I think, to come out of the tech project is that I
00:25:32 realized that my programs were to be read by people and not just by computers and that typography
00:25:45 could massively enhance that. And so, I mean, they’re just wonderful. If they’re going to look
00:25:53 it up, they should also look up this book called Physically Based Rendering by Matt Farr and,
00:26:02 gosh, anyway, it got an Academy Award. But all the graphic effects you see in movies
00:26:13 are accomplished by algorithms. And the whole book is a literate program. It tells you not
00:26:19 only how you do all the shading and bring images in that you need for animation and
00:26:27 textures and so on, but you can run the code. And so, I find it an extension of how to teach
00:26:42 programming is by telling a story as part of the program.
00:26:47 So it works as a program, but it’s also readable by humans.
00:26:52 Yes. And especially by me a week later or a year later.
00:26:58 That’s a good test. If you yourself understand the code easily a week or a month or a year later.
00:27:06 Yeah. So it’s the greatest thing since sliced bread.
00:27:12 Programming or literate programming?
00:27:14 Literate programming.
00:27:15 Okay. You heard it here first. Okay. You dodged this question in an interview I listened to.
00:27:24 So let me ask you again here. What makes for a beautiful program?
00:27:30 What makes for a beautiful program?
00:27:31 Yeah. What are the characteristics you see? Like you just said, literate programming.
00:27:36 What are the characteristics you see in a program that make you sit back and say,
00:27:40 that’s pretty good? Well, the reason I didn’t answer is because there are dozens and dozens
00:27:47 of answers to that because you can define beauty, the same personal defined beauty,
00:27:54 different way from hour to hour. I mean, it depends on what you’re looking for.
00:27:59 At one level, it’s beautiful just if it works at all. At another level, it’s beautiful if it can
00:28:10 be understood easily. It’s beautiful if it’s literate programming. It’s beautiful. It makes
00:28:19 you laugh. I mean.
00:28:21 Yeah. So I’m with you. I think beauty, if it’s readable.
00:28:27 Readable, yeah.
00:28:28 Is if you understand what’s going on and also understand the elegance of thought behind it.
00:28:36 And then also, as you said, wit and humor. I was always, I remember having this conversation,
00:28:42 I had this conversation on Stack Overflow, whether humor is good in comments. And I think it is.
00:28:51 Whether humor is good in comments.
00:28:53 Like when you add comments in code, I always thought a little bit of humor is good.
00:29:00 It shows personality. It shows character, shows wit and fun and all those kinds of things
00:29:07 of the personality of the programmer.
00:29:08 Yeah. Okay. So a couple of days ago, I received a wonderful present from my former editor at
00:29:17 Aspen Wesley. He’s downsizing his house and he found that somebody at the company had
00:29:26 found all of their internal files about the art of computer programming from the 1960s
00:29:32 and they gave it to him before throwing it in the garbage. And then so he said,
00:29:39 oh yeah, he planned to keep it for posterity, but now he realized that posterity is
00:29:44 a bit too much for him to handle, so he sent it to me. And so I just received this big stack
00:29:55 of letters, some of which I had written to them, but many of which they had written to
00:30:02 early guinea pigs who were telling them whether they should publish or not.
00:30:06 You know, and one of the things was in the comments to volume one,
00:30:17 the major reader was Bob Floyd, who is my great co worker in the 60s, died early,
00:30:27 unfortunately. And he commented about the humor in it. So he ran it by me, you know,
00:30:38 says, you know, keep this joke in or not, you know. They also sent it out to focus group.
00:30:46 What do you think about humor in a book about computer programming?
00:30:50 What’s the conclusion?
00:30:51 And I stated my philosophy. It said, you know, the ideal thing is that it’s something where
00:31:00 the reader knows that there’s probably a joke here if you only understood it. And this is a
00:31:04 motivation to understand, to think about it a little bit. But anyway, it’s a very delicate
00:31:13 humor. I mean, it’s really each each century invents a different kind of humor, too. Different
00:31:21 cultures have different different kinds of humor. Yeah. Like we talked about Russia a little bit
00:31:27 offline. You know, there’s dark humor and, you know, when a country goes through something
00:31:34 difficult, that life and stuff like this. And, you know, and Jack Benny, I mean,
00:31:39 you know, Steve Allen wrote this book about humor, and it was the most boring book,
00:31:46 but he was one of my idols. But it’s called The Funny Men or something like that. But yeah. Okay.
00:31:54 So anyway, I think it’s important to know that this is part of life, and it should be fun and
00:32:00 not… And so, you know, I wrote this organ composition, which is based on the Bible,
00:32:08 but I didn’t refrain from putting little jokes in it also in the music.
00:32:14 It’s hidden in the music.
00:32:15 It’s there, yeah.
00:32:18 A little humor is okay?
00:32:19 Yeah. I mean, not egregious humor. So in this correspondence, you know, there were
00:32:27 things I said, yeah, I really shouldn’t have done that. But other ones I insisted on. And I’ve got
00:32:35 jokes in there that nobody has figured out yet. In fact, in volume two, I’ve got a cryptogram,
00:32:44 a message, enciphered. And in order to decipher it, you’re going to have to break an RSA key,
00:32:52 which is larger than people know how to break. And so, you know, if computers keep getting faster
00:32:59 and faster, then, you know, it might be a hundred years, but somebody will figure out what this
00:33:04 what this message is and they will laugh. I mean, I’ve got a joke in there.
00:33:09 So that one you really have to work for. I don’t know if you’ve heard about this.
00:33:15 Let me explain it. Maybe you’ll find it interesting. So OpenAI is a company that
00:33:22 does AI work, and they have this language model. It’s a neural network that can generate
00:33:28 language pretty well. But they also have, on top of that, developed something called OpenAI Codex.
00:33:38 And together with GitHub, they developed a system called OpenAI Copilot.
00:33:43 Let me explain what it does. There’s echoes of literate programming in it. So what you do
00:33:50 is you start writing code and it completes the code for you. So, for example, you start,
00:33:57 let’s go to your factoring program. You start, you write in JavaScript and Python and any language
00:34:04 that it trained on. You start, you write the first line and some comments, like what this
00:34:11 code does, and it generates the function for you. And it does an incredibly good job.
00:34:17 Like, it’s not provably right, but it often does a really good job of completing the code for you.
00:34:23 I see. But how do you know whether it did a good job or not?
00:34:26 Yeah.
00:34:27 You could see a lot of examples where it did a good job.
00:34:31 And so it’s not a thing that generates code for you.
00:34:34 Yeah, exactly.
00:34:35 It starts, it gives you, so it puts the human in the seat of fixing
00:34:42 issues versus writing from scratch. Do you find that kind of idea at all interesting?
00:34:48 Every year, we’re going to be losing more and more control over what machines are doing.
00:34:53 And people are saying, well, when I was a professor at Caltech in the 60s, we had this
00:35:03 guy who talked a good game. He could give inspiring lectures and you’d think, well,
00:35:13 thrilling things he was talking about. An hour later, you’d say, well, what did he say?
00:35:16 Yeah. But he really felt that it didn’t matter whether computers got the right answer or not,
00:35:23 it just mattered whether it made you happy or not. In other words, if your boss paid for it,
00:35:30 then you had a job, you could take care of your wife.
00:35:35 Happiness is more important than truth.
00:35:38 Exactly. He didn’t believe in truth, but he was a philosopher.
00:35:40 Yes, I like it. And somehow you see…
00:35:47 We’re going that way. So many more things are taken over by saying, well, this seems to work.
00:35:55 When there is a competing interest involved, neither side understands
00:36:00 why the decision is being made. We realize now that it’s bad, but consider what happens
00:36:09 5 or 10 years down the line when things get even more further detached. Each thing is based on
00:36:17 something from the previous year.
00:36:20 Yeah. So you start to lose… The more you automate,
00:36:23 the more you start to lose track of some deep human things.
00:36:26 Exponentially.
00:36:28 Exponentially. So that’s the dark side. The positive side is the more you automate,
00:36:36 the more you let humans do what humans do best. So maybe programming…
00:36:43 Maybe humans should focus on a small part of programming that requires that genius,
00:36:48 the magic of the human mind, and the mess you let the machine generate.
00:36:55 That’s the positive, but of course, it does come with the darkness of automation.
00:37:01 What’s better? Correctness?
00:37:02 I’m never going to try to write a book about that.
00:37:06 I’m never going to recommend to any of my students to work for them.
00:37:10 Sure. So you’re on the side of correctness, not beauty, not happiness.
00:37:14 I’m on the side of understanding.
00:37:17 Understanding.
00:37:18 And I think these things are really marvelous if what they do is all of a sudden we have a better
00:37:25 medical diagnosis or it’ll help guide some scientific experiment or something like curing
00:37:34 diseases or whatever. But when it affects people’s lives in a serious way… If you’re writing code,
00:37:46 oh yeah, this is great. This will make a slaughter bot.
00:37:50 I see. So you have to be very careful. Right now it seems like fun and games.
00:37:59 It’s useful to write a little JavaScript program that helps you with the website.
00:38:04 But like you said, one year passes, two years passes, five years, and you forget.
00:38:10 You start building on top of it, and then all of a sudden you have autonomous weapon systems.
00:38:14 Well, we’re all dead. It doesn’t matter in that sense.
00:38:21 Well, in the end, this whole thing ends anyway.
00:38:28 There is a heat death of the universe predicted, but I’m trying to postpone that for a little bit.
00:38:38 Well, it’d be nice that at the end, as we approach the heat death of the universe,
00:38:42 there’s still some kind of consciousness there to appreciate it. Hopefully human consciousness.
00:38:51 I’ll settle for 10 to the 10th year, some finite number. But things like this might be the reason
00:38:59 we don’t pick up any signals from extraterrestrials. They don’t want anything to do with us.
00:39:06 Oh, because they, because they, they, they invented it too.
00:39:14 So you, you do have a little bit of worry on the existential threats of AI and automation.
00:39:23 So like, like removing the human from the picture, et cetera. Yeah.
00:39:26 Um, people have more, more potential to do harm now than by far than they did a hundred years ago.
00:39:36 But are you optimistic about the humans are good at creating destructive things,
00:39:42 but also humans are good at solving problems. Yeah. I mean, there’s half empty and half full,
00:39:46 you know, so I can go. So let me, let me put it this way because,
00:39:54 because it’s the only way I can be optimistic, but, but, but, but think of, um, of, uh,
00:40:05 things that have changed because of civilization, you know, they don’t occur just in nature.
00:40:11 So just, uh, just imagine the room we’re in, for example. Okay. Some, you know, we’ve got pencils,
00:40:19 we’ve got books, we’ve got tables, we’ve got microphones, your clothing, food,
00:40:25 all these things were added. Somebody invented them one by one and millions of things, uh,
00:40:34 that we inherit. Okay. Um, and, uh, it’s inconceivable that, that so many millions
00:40:40 of billions of things, uh, wouldn’t have problems and we get it all right. Um, and each one
00:40:48 would have no negative effects and so on. So it, it’s very amazing that as much works as does work.
00:40:58 It’s, it’s, it’s incredibly amazing. And actually that’s the source of my optimism as well,
00:41:06 including for artificial intelligence. So we, we drive over bridges. We, uh, we use all kinds
00:41:15 of technology. We don’t know how it works. And there’s millions of brilliant people involved in
00:41:20 building a small part of that and it doesn’t go wrong and it works. And I mean that it, it works
00:41:27 and it doesn’t go, go wrong often enough for us to suffer. And we can identify things that
00:41:34 aren’t working and try to improve on them. In a suboptimal, often suboptimal way. Oh, absolutely.
00:41:42 But it’s, but the, but the, the kind of things that I know how to improve require human beings
00:41:50 to be rational. And I, I’m losing my confidence that human beings are rational. Yeah. Yeah. Now
00:41:57 here you go again with the worst case, uh, worst case analysis. Um, they may not be rational, but
00:42:04 they’re, um, they’re, they’re clever and, uh, beautiful in their own kind of way. I tend to
00:42:12 think that most people, um, have the desire and the capacity to be good to each other and love
00:42:20 will ultimately win out. Like if they’re given the opportunity, that’s where they lean. In the Art
00:42:27 of Computer Programming, you wrote, the real problem is that programmers have spent far too
00:42:32 much time worrying about efficiency in the wrong places. And at the wrong times, premature
00:42:38 optimization is the root of all evil in parentheses, or at least most of it in programming. Can you,
00:42:46 uh, explain this idea? Uh, what’s the wrong time? What is the wrong place for optimization? So
00:42:54 so first of all, the word optimization, I started out writing software, uh, and optimization was,
00:43:04 I was a compiler writer. So optimization meant, uh, making the, uh, making a better translation
00:43:12 so that it would run faster on a, on a machine. So an optimized program is just like, you know,
00:43:17 you, you, you run a program and you set the optimization level, uh, for, uh, to the compiler.
00:43:24 So that’s one word for optimization. Um, and at that time I, I happened to be looking in an
00:43:31 unabridged dictionary, uh, for some reason or other, and I came to the word optimizer.
00:43:37 So what’s the meaning of the word optimize? And it says to view with optimism.
00:43:44 And you look in Webster’s dictionary of English language in 19, early 1960s,
00:43:50 that’s what optimize meant. Okay. Um, now, so people started doing cost optimization,
00:43:58 other kinds of things, uh, uh, you know, whole sub fields of, of, uh, algorithms and economics
00:44:06 and whatever are based on what they call optimization now. But, uh, but to me optimization
00:44:13 when I was saying that was saying, uh, changing a program to make it more, uh, tuned to the machine.
00:44:21 And I found out that, uh, when a person writes a program, uh, he or she tends to think that
00:44:33 the parts that were hardest to write are going to be hardest for the computer to execute.
00:44:37 So maybe I have 10 pages of code, but I had to work a week writing this page. I mentally think
00:44:47 that when the computer gets to that page, it’s going to slow down. It’s going to say, oh, I
00:44:53 don’t understand what I’m doing. I better, I better be more careful. Anyway, this is of course silly,
00:44:58 but it’s, it’s, it’s something that we, that we, that we don’t know when we write a piece of code.
00:45:04 We don’t know what, what, whether the computer is actually going to be executing that code
00:45:09 very much. So, so people had, had a very poor understanding of, of what the computer was
00:45:17 actually doing. Uh, I made one test where, where we studied a Fortran compiler and it was spending
00:45:25 more than 80% of its time reading the comments card. Um, but as a programmer, we were really
00:45:32 concerned about how fast it could take a complicated expression that had lots of
00:45:36 levels of parentheses and, and, and, and convert that into something. But that was just, you know,
00:45:43 less than 1% of the, so if we optimize that, uh, we didn’t know what we were doing, but, but,
00:45:52 but if we knew that it was spending 80% of his time on the comments card, you know, in 10 minutes,
00:45:57 we could, we could make the, the, the compiler run more than twice as fast.
00:46:01 And you could only do that once you’ve completed the program and then you empirically study where.
00:46:05 I had some kind of profiling that I knew what was important. Yeah.
00:46:10 So you don’t think this applies generally? I mean, there’s something that rings true to this
00:46:15 across all of them. I’m glad that it applied generally, but it was,
00:46:18 it was only my good luck. I said it, but you know, but I did, but I said it in a limited context
00:46:24 and I, and, and I’m glad if it makes people think about stuff because I, but it applies
00:46:32 in another sense too, that is sometimes I will do optimization in a way that does help
00:46:43 the actual running time, but makes the program impossible to change next week.
00:46:49 Right. Because I’ve changed my data structure or something that, that made it less adaptable.
00:46:56 So one of the great principles of computer science is, is, is laziness or whatever you call it,
00:47:04 late binding. You know, don’t hold off decisions when you can. And, and, and, you know, and we
00:47:14 understand now quantitatively how valuable that is.
00:47:18 What do you mean we understand? So you mean from a…
00:47:22 People, people have written thesis about how you can, how late binding will, will improve the,
00:47:29 I mean, you know, just in time manufacturing or whatever, you can make, you can defer a decision
00:47:36 instead of doing your advanced planning and say, I’m going to allocate 30% to this and 50%.
00:47:41 So in all kinds of domains, there’s an optimality to laziness in many cases.
00:47:45 Decision is not made in advance. So instead you, you, you design in order to be flexible to change
00:47:53 with the, with the way the wind is blowing. Yeah. But so the reason that line resonated
00:48:00 with a lot of people is because there’s something about the programmer’s mind
00:48:06 that wants, that enjoys optimization. So it’s a constant struggle to balance laziness and late
00:48:15 binding with the desire to optimize. The elegance of a well optimized code
00:48:23 is something that’s compelling to programming. Yeah. It’s another concept of beauty.
00:48:31 Let me ask you a weird question. So Roger Penrose has talked about computation computers
00:48:39 and he proposed that the way the human mind discovers mathematical ideas is something more
00:48:49 than a computer. That, that a universal Turing machine cannot do everything that a human mind
00:48:57 can do. Now this includes discovering mathematical ideas and it also includes, he’s written a book
00:49:05 about it, Consciousness. So I don’t know if you know Roger, but my, my daughter’s kids played
00:49:12 with his kids in Oxford. Nice. So do you think there is such a limit to the computer? Do you
00:49:19 think consciousness is more than a computation? Do you think the human mind, the way it thinks
00:49:26 is more than a computation? I mean, I can say yes or no, but, but, but I don’t, I have no reason. I
00:49:35 mean. So you don’t find it useful to have an intuition in one way or the other? Like when
00:49:40 you think about algorithms, isn’t it useful to think about the limits? Unanswerable question in
00:49:46 my opinion is, is no better than anybody else. You think it’s unanswerable. So you don’t think
00:49:51 eventually science. How many angels can dance on the head of a, I mean, I don’t know. But angels.
00:49:58 Anyway, there, there are lots of things that are beyond, that we can speculate about, but
00:50:03 I don’t want somebody to say, oh yeah, Knuth said this and so he’s, he’s, he’s smart. And so,
00:50:08 so he, so that must be, I mean, I say it’s something that we’ll never know.
00:50:14 Oh, interesting. Okay. That’s a strong statement. I don’t, I personally think it’s something we
00:50:22 will know eventually. Like there’s no reason to me why the, the workings of the human mind
00:50:28 are not within the reach of science. That’s absolutely possible. And I’m not denying it.
00:50:34 Yeah. But right now you don’t have a good intuition. I mean, that’s also possible,
00:50:38 you know, that an AI, you know, created the universe, you know, intelligent design has all
00:50:45 been done by an AI. This is, I mean, all of these things are, but, but, but you’re asking me to,
00:50:52 to pronounce on it. And I don’t have any expertise. I’m a teacher that passes on knowledge,
00:50:58 but I don’t, but I don’t know the fact that I, that I vote yes or no on.
00:51:05 Well, you do have expertise as a human, not as a, not as a teacher or a scholar of computer science.
00:51:14 I mean, that’s ultimately the realm of where the discussion of human thought.
00:51:18 Yeah. Well, I know where.
00:51:19 And consciousness is.
00:51:21 I know where, where Penrose is coming from. He, I’m sure he has no,
00:51:26 I mean, he might even thought he proved it, but.
00:51:28 No, he doesn’t. He doesn’t prove it. He is following intuition.
00:51:32 But, but I mean, you have to ask John McCarthy. John McCarthy,
00:51:38 I think, were totally unimpressed by these statements.
00:51:43 So you don’t think, so even like the Turing paper on, on the Turing test that,
00:51:51 you know, starts by asking, can machines think?
00:51:53 Oh.
00:51:54 You don’t think these kind of, Turing doesn’t like that question.
00:51:59 Yeah. I don’t consider it important, let’s just put it that way.
00:52:04 Because it’s, it’s in the category of things that it would be nice to know,
00:52:10 but I think it’s beyond knowledge. And so I don’t, I’m more interested in knowing
00:52:16 about the Riemann hypothesis or something.
00:52:20 So when you say, it’s an interesting statement, beyond knowledge.
00:52:24 Yeah.
00:52:24 I think what you mean is it’s not sufficiently well, it’s not even known well enough to be
00:52:31 able to formalize it in order to ask a clear question.
00:52:35 Yeah.
00:52:36 And so that’s why it’s beyond knowledge, but that doesn’t mean it’s not
00:52:40 eventually going to be formalized.
00:52:41 Yeah. Yeah. Maybe consciousness will be understood some, someday.
00:52:46 The last time I checked, it was still 200 years away.
00:52:51 I mean, I haven’t been specializing in this by any means, but I went to lectures about it 20
00:52:57 years ago when I was, there was a symposium at the American Academy in Cambridge. And it started out
00:53:05 by saying, essentially, everything that’s been written about consciousness is hogwash.
00:53:12 I tend to disagree with that a little bit.
00:53:18 So consciousness for the longest time still is in the realm of philosophy.
00:53:24 So it’s just conversations without any basis and understanding.
00:53:28 Still, I think once you start creating artificial intelligence systems that interact with humans
00:53:38 and they have personality, they have identity, you start flirting with the question of
00:53:45 consciousness, not from a philosophical perspective, but from an engineering perspective.
00:53:50 And then it starts becoming much more like, I feel like.
00:53:53 Yeah. Don’t misunderstand me. I certainly don’t disagree with that at all.
00:54:00 And even at these lectures that we had 20 years ago, there were neurologists pointing out that
00:54:08 human beings had actually decided to do something before they were conscious of making that
00:54:14 decision. I mean, they could tell that signals were being sent to their arms before they knew
00:54:24 that things like this are true. And Les Valiant has an architecture for the brain. And more recently,
00:54:34 Christos Papadimitriou in the Academy of Science Proceedings a year ago with two other people,
00:54:44 but I know Christos very well. And he’s got this model of this architecture by which
00:54:54 you could create things that correlate well with experiments that are done on consciousness.
00:55:02 And he actually has a machine language in which you can write code and test hypotheses.
00:55:17 And so we might have a big breakthrough. My personal feeling is that consciousness is the
00:55:24 best model I’ve heard of to explain the miracle of consciousness is that somehow inside of our
00:55:39 brains, we’re having a continual survival for the fittest competition. And I’m speaking to you,
00:55:49 and I’m speaking to you, all the possible things I might be wanting to say are all in there and
00:55:56 there’s like a voting going on. Yeah, right. And one of them is winning and that’s affecting
00:56:04 the next sentence and so on. And there was this book, Machine Intelligence or something?
00:56:11 On Intelligence?
00:56:12 On Intelligence, yeah. Bill Atkinson was a total devotee of that book.
00:56:21 Well, I like whether it’s consciousness or something else, I like the storytelling part
00:56:27 that it feels like for us humans, it feels like there’s a concrete story. It’s almost
00:56:34 like literary programming. I don’t know what the programming is going on on the inside,
00:56:38 but I’m getting a nice story here about what happened. And it feels like I’m in control and
00:56:44 I’m getting a nice clear story. But it’s also possible there’s a computation going on that’s
00:56:49 really messy. There’s a bunch of different competing ideas. And in the end, it just kind
00:56:54 of generates a story for you, a consistent story for you to believe. And that makes it all nice.
00:57:01 Yeah. And so I prefer to talk about things that I have some expertise in than things
00:57:08 which I’m only on the sideline.
00:57:14 So there’s a tricky thing. I don’t know if you have any expertise in this.
00:57:18 You might be a little bit on the sideline. It’d be interesting to ask though.
00:57:21 What are your thoughts on Cellular Automata and the Game of Life?
00:57:25 Have you ever played with those kind of little games?
00:57:28 I think the Game of Life is wonderful and shows all kinds of stuff about how things can evolve
00:57:43 without the creator understanding anything more than the power of learning in a way. But to me,
00:57:51 the most important thing about the Game of Life is how it focused for me what it meant to have
00:58:01 free will or not. Because the Game of Life is obviously totally deterministic. And I find it
00:58:11 hard to believe that anybody who’s ever had children cannot believe in free will. On the
00:58:17 other hand, this makes it crystal clear. John Conway said he wondered whether it was immoral
00:58:30 to shut the computer off after he got into a particularly interesting play of the Game of Life.
00:58:36 Wow. Yeah. So to me, the reason I love the Game of Life is exactly as you said,
00:58:43 a clear illustration that from simple initial conditions with simple rules,
00:58:49 you know exactly how the system is operating, it’s deterministic. And yet, if you allow yourself to
00:58:58 lose that knowledge a little bit enough to see the bigger organisms that emerge,
00:59:06 and then all of a sudden they seem conscious. They seem, not conscious, but living.
00:59:10 If the universe is finite, we’re all living in the Game of Life, just slowed down. I mean,
00:59:18 it sped up a lot.
00:59:21 But do you think technically some of the ideas that you used for analysis of algorithms can be
00:59:28 used to analyze the Game of Life? Can we make sense of it? Or is it too weird?
00:59:32 Yeah. I mean, I’ve got a dozen exercises in volume four, fascicle six, that actually work
00:59:43 rather well for that purpose. Bill Gospers came up with the algorithm that allows Golly to run
00:59:57 thousands and thousands of times faster. You know the website called Golly? G O L L Y?
01:00:04 It simulates the cellular automata, like Game of Life?
01:00:07 Yeah, you got to check it out.
01:00:10 Can I ask you about John Conway?
01:00:12 Yes. In fact, I’m just reading now the issue of mathematical intelligence that came in last
01:00:19 week. It’s a whole issue devoted to remembrance of him.
01:00:28 Did you know him?
01:00:30 I slept overnight in his house several times.
01:00:35 Yeah.
01:00:36 He recently passed away.
01:00:38 Yeah, he died a year ago, May, I think it was, of COVID.
01:00:46 What are some memories of him, of his work, that stand out for you? On a technical level,
01:00:58 did any of his work inspire you? On a personal level, did he himself inspire you in some way?
01:01:06 Absolutely, all of those things. But let’s see, when did I first meet him? I guess I first met
01:01:11 him at Oxford in 1967 when I was… Okay, that’s a long time ago.
01:01:17 Yeah, you were minus 20 years old or something, I don’t know, 1967. But there was a conference where
01:01:28 I think I was speaking about something known as the Knuth Bendix algorithm now, but he gave a
01:01:37 famous talk about knots. And I didn’t know at the time, but anyway, that talk had now…
01:01:47 The source of thousands and thousands of papers since then. And he was reported on something that
01:01:54 he had done in high school almost 10 years earlier before this conference, but he never published it.
01:02:04 And he climaxed his talk by building some knots. You have these little plastic things that you
01:02:13 can stick together. It’s something like Lego, but easier. And so he made a whole bunch of knots
01:02:23 in front of the audience and so on and then disassembled it. So it was a dramatic lecture
01:02:29 before he had learned how to give even more dramatic lectures later.
01:02:33 Were you at that lecture?
01:02:37 And I was there, yeah, because I was at the same conference. For some reason, I happened to be in
01:02:46 Calgary the same day that he was visiting Calgary. And it was the spring of 72, I’m pretty sure.
01:02:56 And we had lunch together and he wrote down during the lunch on a napkin all of the facts about
01:03:08 what he called numbers. And he covered the napkin with the theorems about his
01:03:17 idea of numbers. And I thought it was incredibly beautiful. And later in 1972, my sabbatical year
01:03:31 began and I went to Norway. And in December of that year, in the middle of the night,
01:03:39 the thought came to me, you know, Conway’s theory about numbers would be a great thing to teach
01:03:46 students how to invent research and what the joys are of research. And I had also read a book in
01:03:57 dialogue by Alfred Renyi, kind of a Socratic thing where the two characters were talking
01:04:06 to each other about mathematics. And so at the end, in the morning, I woke up my wife and said,
01:04:16 Jill, I think I want to write a book about Conway’s theory. And, you know, I’m supposed
01:04:27 to be writing the Art of Computer Program and doing all this other stuff, but I really want
01:04:32 to write this other book. And so we made this plan. But I said, I thought I could write it in a week.
01:04:40 And we made the plan then. So in January, I rented a room in a hotel in downtown Oslo.
01:04:47 We were in sabbatical in Norway. And I rented the hotel in downtown Oslo and did nothing else
01:04:56 except write up Conway’s theory. And I changed the name to Surreal Numbers. And so this book
01:05:02 is now published as Surreal Numbers. And, you know, we figured out, we’d always wonder what
01:05:11 would be like to have a fair enough hotel room. So we figured out that she would visit me twice
01:05:16 during the week. Things like this, you know, we would try to sneak in. This hotel was run by a
01:05:24 mission organization. These ladies were probably very strict, but anyway. So, and it’s a wild week
01:05:34 in every way. But the thing is, I had lost that. I had lost that napkin in which he wrote the
01:05:38 theory, but I looked for it, but I couldn’t find it. So I tried to recreate from memory what he
01:05:46 had told me at that lunch in Calgary. And as I wrote the book, I was going through exactly what
01:05:55 I, what the characters in the book were supposed to be doing. So I start with the two axioms that
01:06:01 start out the whole thing and everything is defined, flows from that, but you have to discover
01:06:06 why. And every mistake that I make as I’m trying to discover it, my characters make too. And so
01:06:15 it’s a long, long story. But I worked through this week and it was one of the most intense
01:06:25 weeks of my life and I described it in other places. But anyway, after six days, I finished it
01:06:36 and on the seventh day I rested and I sent to my secretary to type it. It was flowing as I was
01:06:44 writing it faster than I could think almost. But after I finished and tried to write a letter to
01:06:54 my secretary telling her how to type it, I couldn’t write anymore. You gave it everything.
01:06:59 The muse had left me completely. Can you explain how that week could have happened? Like why?
01:07:05 That seems like such a magical week of productivity. I have no idea. But anyway,
01:07:08 there was some… It was almost as if I was channeling. So the book was typed,
01:07:15 they sent it to Conway and he said, well, Don, you got the one axiom wrong.
01:07:24 Is there a difference between less than or equal and not greater than? The opposite of being
01:07:32 greater than and less than or equal. But anyway, technically it can make a difference when you’re
01:07:38 developing a logical theory. And the way I had chosen was harder to do than John’s original.
01:07:47 And we visited him at his house in Cambridge in April. We took a boat actually from Norway
01:07:53 over to across the channel and so on and stayed with him for some days. And we talked
01:08:01 about all kinds of things he had. He had puzzles that I’d never heard of before. He had a great way
01:08:12 to solve the game of solitaire. Many of the common interests that he’d never written them up.
01:08:19 But anyway, then in the summertime, I took another week off and went to a
01:08:25 Conway place in the mountains of Norway and rewrote the book using the correct axiom.
01:08:34 So that was the most intensive connection with Conway. After that…
01:08:40 It started with a napkin.
01:08:41 It started with a napkin. But we would run into each other. The next really…
01:08:50 And I was giving lectures in Montreal. I was giving a series of seven lectures about the
01:09:02 topic called Stable Marriages. And he arrived in Montreal between my sixth and seventh lecture.
01:09:11 And we met at a party. And I started telling him about the topic I was doing. And he sat and
01:09:20 thought about it. He came up with a beautiful theory to show that the… I mean, in technical
01:09:26 terms, it’s that the set of all stable marriages forms a lattice. And there was a simple way to
01:09:34 find the greatest lower bound of two stable pairings and least upper bound of two stable
01:09:41 marriage. And so I could use it in my lecture the next day. And he came up with this theorem
01:09:46 during the party. And it’s a distributive lattice. It added greatly to the theory of stable matching.
01:09:59 So you mentioned your wife, Jill. You mentioned stable marriage. Can you tell the story of how
01:10:07 you two met? So we celebrated 60 years of wedded bliss last month. And we met because I was dating
01:10:17 her roommate. This was my sophomore year, her freshman year. I was dating her roommate. And
01:10:24 I wanted her advice on strategy or something like this. And anyway, I found I enjoyed her advice
01:10:33 better than her. I enjoyed her roommate. You guys were majoring the same thing?
01:10:39 No, no, no. Because I read something about working on a computer in grad school on a difficult
01:10:46 computer science topic. So she’s an artist and I’m a geek.
01:10:55 What was she doing with a computer science book? Was it the manual that she was reading?
01:11:01 What was she reading? I wrote the manual that she had to take a
01:11:05 class in computer science. So you’re the tutor?
01:11:10 No, no. There were terrible times trying to learn certain concepts, but I learned art from her.
01:11:23 And so we worked together occasionally in design projects. But every year we write a Christmas card
01:11:32 and we each have to compromise our own notions of beauty.
01:11:40 When did you fall in love with her? That day that I asked her about her roommate.
01:11:48 I don’t mind telling these things, depending on how far you go.
01:11:59 I promise not to go too far.
01:12:05 Let me tell you this. I never really enjoyed kissing until I found how she did it.
01:12:13 Wow. And 60 years.
01:12:20 Is there a secret you can say in terms of stable marriages, of how you stayed together so long?
01:12:27 The topic stable marriage, by the way, is a technical term.
01:12:33 Yes. It’s a joke, Don.
01:12:36 But two different people will have to learn how to compromise and work together and
01:12:48 you’re going to have ups and downs and crises and so on. And so as long as you don’t
01:12:56 set your expectation on having 24 hours of bliss, then there’s a lot of hope for stability.
01:13:04 But if you decide that there’s going to be no frustration, then…
01:13:13 So you’re going to have to compromise on your notions of beauty when you write Christmas cards.
01:13:18 That’s it.
01:13:21 You mentioned that Richard Feynman was someone you looked up to.
01:13:25 Yeah.
01:13:26 Probably you’ve met him in Caltech.
01:13:28 Well, we knew each other, yeah, at Caltech, for sure, yeah.
01:13:35 You are one of the seminal personalities of computer science. He’s one for physics.
01:13:43 Is there specific things you picked up from him by way of inspiration?
01:13:49 So we used to go to each other’s lectures.
01:13:51 But if I saw him sitting in the front row, it would throw me for a loop, actually. I would
01:13:59 miss a few sentences. What unique story do I have? I often refer to his time in Brazil
01:14:11 where he essentially said they were teaching all the physics students the wrong way. They were just
01:14:18 learning how to pass exams and not learning any physics. And he said, if you want me to prove it,
01:14:27 here, I’ll turn any page of this textbook and I’ll tell you what’s wrong with this page. And
01:14:32 he did so. And the textbook had been written by his host, and he was a great teacher. And he
01:14:39 had previously asked his host if he was supposed to tell the truth. But anyway, it epitomizes the
01:14:47 way education goes wrong in all kinds of fields and has to periodically be brought back from a
01:15:00 process of giving credentials to a process of giving knowledge.
01:15:10 That’s probably a story that continues to this day in a bunch of places where it’s too easy for
01:15:19 educational institutions to fall into credentialism versus inspirationalism.
01:15:26 I don’t know if those are words, but sort of understanding versus just giving a little
01:15:36 plaque.
01:15:39 It’s very much like what we were talking about. If you want to be able to believe
01:15:45 the answer, a computer is doing that. One of the things Bob Floyd showed me in the 60s,
01:15:51 there was a… He loved this cartoon. There were two guys standing in front of… In those days,
01:15:59 a computer was a big thing. And the first guy says to the other guy, he said,
01:16:04 this machine can do in one second what it would take a million people to do in a hundred years.
01:16:12 And the other guy says, oh, so how do you know it’s right?
01:16:14 That’s a good line.
01:16:21 Is there some interesting distinction between physics and math to you?
01:16:26 Have you looked at physics much? Speaking of Richard Feynman,
01:16:31 the difference between the physics community, the physics way of thinking, the physics intuition
01:16:36 versus the theoretical computer science, the mathematical sciences,
01:16:40 do you see that as a gap? Are they strongly overlapping?
01:16:44 It’s quite different, in my opinion. I started as a physics major and I switched into math.
01:16:52 And probably the reason was that I could get A plus on the physics exam, but I never had any
01:16:59 idea why I would have been able to come up with the problems that were on those exams.
01:17:05 But in math, I knew why the teacher set those problems and I thought of other problems that
01:17:13 I could set, too. And I believe it’s quite a different mentality.
01:17:20 It has to do with your philosophy of geekdom?
01:17:23 No, it’s… I mean, some of my computer scientist friends are really good at physics and others are
01:17:30 really good at physics and others are not. And I’m really good at algebra, but not at geometry.
01:17:39 Talk about different parts of mathematics. So there are different kinds of physics,
01:17:44 but physicists think of things in terms of waves. And I can think of things in terms of waves,
01:17:51 but it’s like a dog walking on hind legs if I’m thinking about it.
01:17:54 So you basically like to see the world in discrete ways and then physics is more continuous.
01:18:02 Yeah. I’m not sure if Turing would have been a great physicist. I think he was a pretty good
01:18:10 chemist, but I don’t know. But anyway, I see things… I believe that computer science is
01:18:19 largely driven by people who have brains who are good at resonating with certain kinds of concepts.
01:18:34 And like quantum computers, it takes a different kind of brain.
01:18:37 Yeah, that’s interesting. Yeah. Well, quantum computers is almost like at the intersection
01:18:42 in terms of brain between computer science and physics because it involves both at least at this
01:18:50 time. But there is like the physicists I’ve known, they have incredibly powerful intuition.
01:18:59 And I mean, statistical mechanics. So I study statistical mechanics and I mean,
01:19:08 random processes are related to algorithms in a lot of ways. But there’s lots of different
01:19:15 flavors of physics as there are different flavors of mathematics as well. But the thing is that I
01:19:23 don’t see… Well, actually, when they talk to physicists, they use a completely different
01:19:30 language than when they’re writing expository papers. And so I didn’t understand quantum
01:19:36 mechanics at all from reading about it in Scientific American. But when I read how they
01:19:42 describe it to each other, talking about eigenvalues and various mathematical terms that
01:19:50 made sense, then it made sense to me. But Hawking said that every formula you put in a book,
01:19:58 you lose half of your readers. And so he didn’t put any formulas in the book. So I couldn’t
01:20:02 understand his book at all. You could say you understood it, but I really didn’t.
01:20:10 Well, Feynman also spoke in this way. So Feynman, I think, prided himself on really strong
01:20:17 intuition. But at the same time, he was hiding all the really good, the deep computation he was
01:20:23 doing. So there was one thing that I was never able to… I wish I’d had more time to work out
01:20:32 with him. But I guess I could describe it for you. There’s something that got my name attached to it
01:20:39 called Knuth arrow notation. But it’s a notation for very large numbers. And so I find out that
01:20:48 somebody invented it in the 1830s. It’s fairly easy to understand anyway. So you start with
01:20:56 x plus x plus x plus x n times, and you can call that xn. So xn is multiplication. Then you take x
01:21:08 times x times x times x n times. That gives you exponentiation, x to the nth power. So that’s one
01:21:17 arrow. So xn with no arrows is multiplication. Arrow n is x to the nth power.
01:21:25 Yeah. So just to clarify for the… So x times x times x n times is obviously xn.
01:21:36 x plus x plus x n times.
01:21:39 Oh, yeah. Okay. And then multiplication is x to the n. And then here the arrow is when you’re
01:21:47 doing the same kind of repetitive operation for the exponential.
01:21:51 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 x to the x to the x to the x n times power. So in other words, if it’s two double arrow three,
01:22:08 that would be two to the two to the two. So that would be two to the fourth power. That’d be 16.
01:22:15 Okay. So that’s the double arrow. And now you can do a triple arrow, of course, and so on.
01:22:28 And I had this paper called, well, essentially big numbers. You try to impress your friend,
01:22:38 but by saying a number they’ve never thought of before. And I gave a special name for it
01:22:47 and designed a font for it that has script k and so on. But it really is 10, I think,
01:22:53 like 10 quadruple arrow three or something like that. And I claim that that number is so mind
01:23:00 boggling that you can’t comprehend how large it is. But anyway, I talked to Feynman about this,
01:23:07 and he said, oh, let’s just use double arrow. But instead of taking integers, let’s consider
01:23:15 complex numbers. I mean, okay, x arrow arrow two, that means x to the x. But what about x
01:23:27 double arrow 2.5? Well, that’s not too hard to figure out. That’s interpolate between those.
01:23:34 But what about x double arrow i or 1 plus i or some complex number?
01:23:42 And so he claimed that there was no analytic function that would do the job.
01:23:54 But I didn’t know how he could claim that that wasn’t true. And his next question was,
01:24:03 did then have a complex number of arrows?
01:24:09 Yeah. Okay.
01:24:10 Wow. Okay.
01:24:11 Okay. So that’s Feynman.
01:24:13 That’s Feynman.
01:24:14 Yeah.
01:24:16 Can you describe what the Knuth Morris Pratt algorithm does? And how did you come to develop
01:24:24 it? One of the many things that you’re known for and has your name attached to it.
01:24:28 Yeah. All right. So it should be actually Morris Pratt Knuth. But we decided to use
01:24:36 alphabetical order when we published the paper. The problem is something that everybody knows
01:24:42 now if they’re using a search engine. You have a large collection of text, and you want to know
01:24:53 if the word Knuth appears anywhere in the text, let’s say, or some other word that’s less
01:25:01 interesting than Knuth. But anyway. That’s the most interesting word.
01:25:05 Like Morris or something. Like Morris, right.
01:25:07 So anyway, we have a large piece of text, and it’s all one long, one dimensional thing. First
01:25:16 letter, second letter, et cetera, et cetera, et cetera. And so you’d like to be able to do this
01:25:24 quickly. And the obvious way is let’s say we’re looking for Morris. Okay. So we would go through
01:25:33 and wait till we get to letter M. Then we look at the next word, and sure enough, it’s an O,
01:25:39 and then an R. But then, too bad, the next letter is E. So we missed out on Morris. And so we go
01:25:52 back and start looking for another. So that’s the obvious way to do it. All right. And Jim Morris
01:26:01 noticed there was a more clever way to do it. The obvious way would have started… Let’s say
01:26:10 we found that letter M had character position 1000. So it would have started next at character
01:26:16 position 1001. But he said, no, look, we already read the O and the R, and we know that they aren’t
01:26:26 Ms. So we can start… We don’t have to read those over again. And this gets pretty tricky when
01:26:37 the word isn’t Morris, but it’s more like abracadabra, where you have patterns that
01:26:43 are occurring. Like repeating patterns at the beginning, at the middle, at the end.
01:26:49 Right. So he worked it out, and he put it into the system software at Berkeley, I think it was,
01:26:57 where he was writing some… Berkeley Unix, I think, was some routine that was supposed to
01:27:03 find occurrences of patterns in text. But he didn’t explain it. And so he found out that several
01:27:14 months later, somebody had looked at it, didn’t look right, and so they ripped it out. So he had
01:27:20 this algorithm, but it didn’t make it through because it wasn’t understood. Nobody knew about
01:27:28 this particularly. Von Pratt also had independently discovered it a year or two later. I forget why.
01:27:39 I think Von was studying some technical problem about palindromes or something like that. He
01:27:48 wasn’t really… Von wasn’t working on text searching, but he was working on an abstract
01:27:56 problem that was related. Well, at that time, Steve Cook was professor at Berkeley, and
01:28:04 it was the greatest mistake that Berkeley CS department made was not to give him tenure.
01:28:13 So Steve went to Toronto. But I knew Steve while he was at Berkeley,
01:28:20 and he had come up with a very peculiar theorem about a technical concept called a stack automaton.
01:28:29 And a stack automaton is a machine that can’t do everything a Turing machine can do, but it
01:28:38 can only look at something at the top of a stack, or it can put more things on the stack, or it can
01:28:44 take things off of the stack. It can’t remember a long string of symbols, but it can remember them
01:28:51 in reverse order. So if you tell a stack automaton A, B, C, D, E, it can tell you afterwards E, D,
01:29:00 C, B, A. It doesn’t have any other memory except this one thing that it can see. And Steve Cook
01:29:08 proved this amazing thing that says if a stack automaton can recognize a language where the
01:29:16 strings of the language are length n in any amount of time whatsoever, so the stack automaton might
01:29:24 use a zillion steps, a regular computer can recognize that same language in time n log n.
01:29:30 So Steve had a way of transforming a computation that goes on and on and on and on
01:29:38 using different data structures into something that you can do on a regular computer
01:29:43 fast. The stack automaton goes slow, but somehow the fact that it can do it at all
01:29:53 means that there has to be a fast way. So I thought this was a pretty cool theorem.
01:29:59 And so I tried it out on a problem where I knew a stack automaton could do it,
01:30:08 but I couldn’t figure out a fast way to do it on a regular computer. I thought it was a pretty
01:30:12 good programmer, but by golly, I couldn’t think of any way to recognize this language efficiently.
01:30:22 So I went through Steve Cook’s construction. I filled my blackboard with everything that
01:30:29 stack automaton did. I wrote down, and then I tried to see patterns in that.
01:30:37 And how did he convert that into a computer program on a regular machine? And finally,
01:30:44 I psyched it out. What was the thing I was missing so that I could say, oh yeah, this is what I
01:30:52 should do in my program. And now I have an efficient program. And so I would never have
01:31:01 thought about that if I hadn’t had his theorem, which was a purely abstract thing.
01:31:09 So you used this theorem to try to intuit how to use the stack automaton for the string matching
01:31:16 problem. Yeah. So the problem I had started with was not the string matching problem,
01:31:23 but then I realized that the string matching problem was another thing which could be done
01:31:28 by a stack automaton. And so when I looked at what that told me, then I had a nice algorithm for this
01:31:36 string matching problem. And it told me exactly what I should remember as I’m going through the
01:31:44 string. And I worked it out, and I wrote this little paper called Automata Theory Can Be Useful.
01:31:52 And the reason was that it was first, I mean, I had been reading all kinds of papers about
01:31:56 automata theory, but it never improved my programming for everyday problems. It was
01:32:04 something that you published in journals, and it was interesting stuff. But here was a case
01:32:11 where I couldn’t figure out how to write the program. I had a theorem from automata theory.
01:32:16 Then I knew how to write the program. So this was, for me, a change in life. I started to say,
01:32:25 maybe I should learn more about automata theory. And I showed this note to Vaughn Pratt,
01:32:32 and he said, that’s similar to something I was working on. And Jim Morris was at Berkeley,
01:32:41 too, at the time. Anyway, he’s had an illustrious career, but I haven’t kept track of Jim. But Vaughn
01:32:49 is my colleague at Stanford and my student later. But this was before Vaughn was still a graduate
01:32:58 student and hadn’t come to Stanford yet. So we found out that we’d all been working on the
01:33:02 same thing. So it was our algorithm. We each discovered it independently, but each of us
01:33:07 had discovered a different part of the elephant, a different aspect of it. And so we could put our
01:33:15 things together with my job to write the paper. How did the elephant spring to life?
01:33:23 Spring to life was because I had drafted this paper, automata theory.
01:33:30 Oh. It can be useful, which was seen by Vaughn and then by Jim. And then we combined,
01:33:36 because maybe they had also been thinking of writing something up about it.
01:33:40 About specifically the string match problem in a period.
01:33:48 Let me ask a ridiculous question. Last time we talked, you told me what the most beautiful
01:33:54 algorithm is, actually, for strongly connected graphs. What is the hardest problem, puzzle,
01:34:03 idea in computer science for you personally that you had to work through? Just something that was
01:34:09 just the hardest thing that I’ve ever been involved with. I don’t know how to answer
01:34:17 questions like that, but in this case, it’s pretty clear because it’s called the birth of
01:34:29 the giant component. So now let me explain that because this actually gets into physics too.
01:34:35 And it gets into something called Bose Einstein statistics. But anyway, it’s got some interesting
01:34:44 stories and it’s connected with Berkeley again. So start with the idea of a random graph.
01:34:52 Now, here we just say we have N points that are totally unconnected and there’s no geometry
01:35:02 involved. There’s no saying some points are further apart than others. All points are exactly
01:35:09 alike. And let’s say we have 100 points and we number them from 0 to 99.
01:35:19 Now let’s take pi, the digits of pi, so two at a time. So we had 31, 41, 59, 26. We can
01:35:31 look, go through pi. And so we take the first two, 31, 41, and let’s put a connection between
01:35:41 0.31 and 0.41. That’s an edge in the graph. Then we take 59, 26 and make another edge.
01:35:52 And the graph gets bigger, gets more and more connected as we add these things one at a time.
01:36:00 So we started out with N points and we add M edges. Each edge is completely, we forgot about
01:36:10 edges we had before. We might get an edge twice. We might get an edge from a point to itself even.
01:36:16 Maybe pi is going to have a run of four digits in there. But anyway, we’re evolving a graph at
01:36:26 random. And a magical thing happens when the number of edges is like 0.49 N, so maybe N is a
01:36:40 million and I have 490,000 edges. Then almost all the time, it consists of isolated trees,
01:36:55 not even any loops.
01:36:58 It’s a very small number of edges so far.
01:37:01 A little less than half N.
01:37:03 N, right.
01:37:04 A little less than half N. But if I had 0.51 edges, so a little more than half N.
01:37:12 So a million points, 510,000 edges. Now it probably has
01:37:24 one component that’s much bigger than the others. And we call that the giant component.
01:37:30 So can you clarify? First of all, is there a name for this kind of random,
01:37:37 super cool pi random graph?
01:37:41 Well, I call it the pi graph. No, no, the pi graph is actually, my pi graph is based on
01:37:51 binary representation of pi, not the decimal representation of pi. But anyway, let’s suppose
01:37:59 I was rolling dice instead. So it doesn’t have to be pi?
01:38:07 The point is, every step, choose totally at random one of those endpoints,
01:38:13 choose totally at random another one of those endpoints, make that an edge. That’s the process.
01:38:21 So there’s nothing magical about pi?
01:38:23 No, no, I was sort of saying pi is sort of random that nobody knows the pattern in.
01:38:29 Exactly, got it.
01:38:31 But I could have just as well drawn straws or something. This was a concept invented by
01:38:39 Erdos and Renyi, and they call it the evolution of random graphs. And if you start out with
01:38:45 a large number N, and you repeat this process, all of a sudden a big bang happens at one half N.
01:38:52 There’ll be two points together, then maybe we’ll have three. And then maybe branch out a little
01:39:01 bit. But they’ll all be separate until we get to one half N. And we pass one half N, and all of a
01:39:08 sudden there’s substance to it. There’s a big clump of stuff that’s all joined together.
01:39:16 So it’s almost like a phase transition of some kind.
01:39:19 It’s exactly. It’s a phase transition, but it’s a double phase transition. It turns out
01:39:27 that there’s actually two things going on at once at this phase transition, which is very
01:39:34 remarkable about it. So a lot of the most important algorithms are based on random
01:39:40 processes. And so I want to understand random processes now. So there are data structures that
01:39:46 sort of grow this way. Okay, so Dick Karp, one of the leading experts on randomized algorithms,
01:39:56 had his students looking at this at Berkeley. And we heard a rumor that the students had
01:40:02 found something interesting happening. The students are generating this,
01:40:08 or simulating this random evolution of graphs. And they’re taking snapshots every so often to
01:40:17 take a look at what the graph is. And the rumor was that every time they looked,
01:40:23 there was only one component that had loops in it, almost always. They do a million experiments,
01:40:30 and only three or four times did they ever happen to see a loop at this point.
01:40:35 I mean, no, more than one component with a loop. So they watch it until the graph gets
01:40:43 completely full. So it starts out totally empty and gets more and more edges all the time.
01:40:52 And so, okay, certainly a loop comes along once. But now all the loops stay somehow joined to that
01:40:59 one. There never were two guys with loops in these experiments. So anyway, almost always,
01:41:12 certainly not always, but with very high probability this seemed to be true.
01:41:19 So we heard about this rumor at Stanford, and we said, if that’s true, then a lot more must also
01:41:26 be true. So there’s a whole theory out there waiting to be discovered that we haven’t ever
01:41:31 thought about. So let’s take a look at it. And so we looked closer and we found out, no, actually,
01:41:37 it’s not true. But in fact, it’s almost true. Namely, there’s a very short interval of time
01:41:46 when it’s true. And if you don’t happen to look at it during that short interval of time,
01:41:51 then you miss it. So in other words, there’ll be a period where there are two or three
01:42:00 components that have loops, but they join together pretty soon.
01:42:05 Okay. So if you don’t have a real fast shutter speed, you’re going to miss that instant.
01:42:15 So separate loops don’t exist for long.
01:42:18 That’s it. Yeah. I started looking at this to make it quantitative. And the basic problem was
01:42:25 to slow down the Big Bang so that I could watch it happening. I think I can explain it actually
01:42:32 in fairly elementary terms, even without writing a formula, like Hawking would do.
01:42:38 And so let’s watch the evolution. And at first, these edges are coming along and they’re just
01:42:47 making things without loops, which we call trees. So then all of a sudden, a loop first appears.
01:42:54 So at that point, I have one component that has a loop. Now, I say that the complexity of a
01:43:01 component is the number of edges minus the number of vertices. So if I have a loop, I have like a
01:43:10 loop of length five, it has five edges and five vertices. Or I could put a tail on that and that
01:43:19 would be another edge, another vertex.
01:43:21 It’s like a zero, one, two complexity kind of thing.
01:43:24 So if the complexity is zero, we have one loop, I call it a cycle or I call it a cyclic
01:43:32 component. So a cyclic component looks like a wheel to which you attach fibers or trees.
01:43:45 They go branching, but there are no more loops. There’s only one loop and everything else
01:43:49 feeds into that loop. And that has complexity zero. But a tree itself has complexity minus one
01:43:57 because it might have 10 vertices and nine edges to tie them together. So nine minus 10 is minus
01:44:06 one. So complexity minus one is a tree. It’s got to be connected. That’s what I mean by a
01:44:14 component. It’s got to be connected. So if I have 10 things connected, I have to have nine edges.
01:44:21 Can you clarify why when complexity can go above zero, I’m a little confused why.
01:44:28 Right. So the complexity plus one is the number of loops. So if complexity is zero,
01:44:34 I have one loop. If complexity is one, that means I have one more edge than I have vertices. So I
01:44:43 might have like 11 edges and 10 vertices. So we call that a bicycle because it’s got two loops
01:44:53 in it. It’s got to have two loops in it. Well, but why can’t it be trees just going off of the loop?
01:45:02 I would need more edges then. Oh, right. Right. Okay. I got it. So every time I get another loop,
01:45:08 I get another excess of edges over vertices. I got you. Okay. So in other words,
01:45:15 we start out and after I have one loop, I have one component that has a cycle in it.
01:45:23 Now the next step, according to the rumor, would be that at the next step, I would have a bicycle
01:45:31 in the evolution of almost all graphs. It would go from cycle to bicycle. But in fact,
01:45:39 there’s a certain probability it goes from cycle to two different cycles.
01:45:48 And I worked out the probability was something like five out of 24.
01:45:52 That’s pretty high.
01:45:53 Right. It was substantial. But still, soon they’re going to merge together almost. Okay.
01:46:02 That’s so cool.
01:46:03 But then it splits again after you have either two or one, one. The next step is you either have
01:46:11 three or you have two, one or you have one, one, one. Okay. And so I worked out the probability
01:46:17 for those transitions. And I worked it out up to the first five transitions. And I had these
01:46:28 strange numbers, five 24s. And I stayed up all night and about 3 a.m. I had the numbers computed
01:46:35 and I looked at them. The denominator was something like 23023. The probability was
01:46:49 something over 23023. I don’t know how you worked that out.
01:46:53 But I had a formula that I could calculate the probability. And I could find the limiting
01:46:58 probability as n goes to infinity. And it turned out to be this number. But the denominator was
01:47:04 230. And I looked at the denominator and I said, wait a minute. This number factors because
01:47:11 1001 is equal to 7 times 11 times 13. I had learned that in my first computer program.
01:47:17 So 23023 is 7 times 11 times 13 times 23. That’s not a random number. There has to be a reason
01:47:31 why those small primes appear in the denominator. So all of a sudden that suggested another way of
01:47:41 looking at the problem where small prime factors would occur. So that said, oh, yeah, let me take
01:47:50 the logarithm of this formula. And sure enough, it’s going to simplify. And it happened. So I
01:47:59 and I wouldn’t have noticed it except for this factorization. OK, so I go to bed and I say,
01:48:05 oh, OK, this is this looks like I’m slowing down the Big Bang. I can figure out what’s going on
01:48:09 here. And the next day it turned out Bill Gates comes to Stanford to visit. They’re trying to
01:48:17 sell him on donating money for a new computer science building. And they gave me an appointment
01:48:25 to talk to Bill and I wrote down on the blackboard this evolutionary diagram going from one to two,
01:48:33 five twenty fourths in all this business. And I wrote it down. And anyway, at the end of the day,
01:48:40 he was discussing people with the development office and he said, boy, I was really impressed
01:48:46 with what Professor Knuth said about this giant component. And and so, you know, I love this story
01:48:56 because it shows that theoretical computer science is really worthwhile. Does Bill have you ever
01:49:03 talked to Bill Gates about it since then? Yeah, that’s a cool that’s a cool little moment in
01:49:09 history. But anyway, he happened to visit on exactly the day after I had I had found this
01:49:17 pattern and that allowed me to crack the problem so that I could develop the theory some more and
01:49:25 understand what’s happening in the big. But because I could I could now write down explicit formulas
01:49:33 for stuff. And so it would work not only the first few steps, but also they’ll study the
01:49:39 whole process. And and I worked further and further and I with two authors, co authors,
01:49:45 and we finally figured out that the probability that the rumor was true. In other words,
01:49:53 look at the evolution of a random graph going from zero to complete and say, what’s the probability
01:50:02 that at every point in time, there was only one component with a cycle? We started with this
01:50:09 rumor saying there’s only one site, there’s only one component with a cycle. And so the rumor was
01:50:16 it’s 100%. Rumor was that was 100%. It turned out the actual numbers is like 87%. I should remember
01:50:26 the number but I don’t but I don’t have it with me. But but anyway, but but the but the number it
01:50:33 turned out to be like 12 over pi squared or eight over pi. Anyway, it was a nice it related to pi.
01:50:42 Yeah. And we could never have done that with it. But so that’s the hardest problem I ever
01:50:48 solved in my life was to prove that this probability is it was proven. The probability
01:50:54 was proven. Yeah, I was able to prove this that this and this should shed light on a whole bunch
01:51:01 of other things about random graphs. That was sort of the major thing we were after.
01:51:07 That’s super cool. What was the connection to physics that you mentioned?
01:51:11 Well, Bose Einstein statistics is a study of how molecules bond together
01:51:18 without geometry. You created the tech typesetting system and released it as open source.
01:51:33 Just on that little aspect, why did you release it as open source? What is your vision for open source?
01:51:42 Okay, well that the word open source didn’t exist at that time. But we but I didn’t want
01:51:47 proprietary rights over it. Because I saw how proprietary rights were holding things back.
01:51:56 In the late 50s, people at IBM developed the language called Fortran. They could have
01:52:03 kept it proprietary. They could have said only IBM can use this language. Everybody else has to.
01:52:09 But they didn’t. They said anybody who can translate Fortran into the language of their
01:52:18 machines is allowed to make Fortran compilers. On the other hand, in the typography industry,
01:52:28 I had seen a lot of languages that were developed for composing pages.
01:52:34 And each manufacturer had his own language for composing pages. And that was holding everything
01:52:41 back because people were tied to a particular manufacturer. And then a new equipment is invented
01:52:48 a year later. But printing machines, they have to expect to amortize the cost over 20, 30 years.
01:52:55 So you didn’t want that for tech?
01:52:57 That for tech. I didn’t need the income. I already had a good job. And my books were,
01:53:14 people were buying enough books that it would bring me plenty of supplemental income for
01:53:23 everything my kids needed for education and whatever. So there was no reason for me to try
01:53:28 to maximize income any further. Income is sort of a threshold function. If you don’t have enough,
01:53:36 you’re starving. But if you get over the threshold, then you start thinking about
01:53:41 philanthropy or else you’re trying to take it with you. But anyway, my income was over the
01:53:51 threshold. So I didn’t need to keep it. And so I specifically could see the advantage of
01:54:00 making it open for everybody.
01:54:02 Do you think most software should be open?
01:54:06 So I think that people should charge for non trivial software, but not for trivial software.
01:54:13 Yeah, you give an example of, I think, Adobe Photoshop versus GIMP on Linux as Photoshop has
01:54:21 value.
01:54:22 So it’s definitely worth paying for all this stuff. I mean, well, they keep adding stuff that
01:54:33 my wife and I don’t care about, but they have built in a fantastic undo feature, for example,
01:54:47 in Photoshop where you can go through a sequence of a thousand complicated steps on graphics and
01:54:54 then it can take you back anywhere in that sequence with really beautiful algorithms.
01:55:03 Oh, that’s interesting. I didn’t think about what algorithm. It must be some kind of efficient
01:55:08 representation.
01:55:08 Yeah, no. I mean, there’s a lot of really subtle Nobel Prize class creation of intellectual
01:55:16 property in there. And with patents, you get a limited time to, I mean, eventually the
01:55:30 idea of patents is that you publish so that it’s not a trade secret.
01:55:37 That said, you’ve said that I currently use Ubuntu Linux on a standalone laptop. It has
01:55:45 no internet connection. I occasionally carry flash memory drives between the machine and
01:55:50 the Macs that I use for network surfing and graphics, but I trust my family jewels only
01:55:57 to Linux. Why do you love Linux?
01:56:00 The version of Linux that I use is stable. Actually, I’m going to have to upgrade one
01:56:07 of these days, but…
01:56:08 To a newer version of Ubuntu?
01:56:10 Yeah, I’ll stick with Ubuntu, but right now I’m running something that doesn’t support
01:56:18 a lot of the new software. The last stable, I don’t remember the number, like 14. Anyway,
01:56:26 it’s quite… And I’m going to get a new computer. I’m getting new solid state memory instead
01:56:35 of a hard disk.
01:56:36 Yeah, the basics. Well, let me ask you, sticking on the topic of tech, when thinking about
01:56:47 beautiful typography, what is your favorite letter, number, or symbol? I know, I know.
01:56:56 Ridiculous question, but is there some…
01:56:57 Let me show you here.
01:56:59 Look at the last page.
01:57:11 The very end of the index.
01:57:15 What is that?
01:57:17 There’s a book by Dr. Seuss called On Beyond Zebra, and he gave a name to that.
01:57:22 Did you say Dr. Seuss gave a name to that?
01:57:24 Dr. Seuss, this is S, E, U, S, S, E. He wrote children’s books in the 50s, 40s and 50s.
01:57:34 Wait, you’re talking about Cat in the Hat, Dr. Seuss?
01:57:36 Cat in the Hat, yeah. That’s it, yeah.
01:57:39 I like how you had the spell there.
01:57:41 On Beyond Zebra, did it get to Soviet Union?
01:57:46 No, Dr. Seuss did not come to the Soviet Union, but since you… Oh, actually, I think it did
01:57:56 actually a little bit when we were… That was a book, maybe Cat in the Hat or Green Eggs and Ham,
01:58:07 I think was used to learn English.
01:58:10 Oh, okay.
01:58:11 So I think it made it in that way.
01:58:12 Well, my… Okay, I didn’t like those as much as Bartholomew Cubbins, but I used to know
01:58:21 Bartholomew Cubbins by heart when I was young.
01:58:24 So what the heck is this symbol we’re looking at? There’s so much going on.
01:58:28 He has a name for it at the end of his book On Beyond Zebra.
01:58:32 Who made it?
01:58:34 He did.
01:58:34 He did. So there’s… It looks like a bunch of vines.
01:58:39 Well, is that symbol exist in fact?
01:58:41 By the way, he made a movie in the early 50s. I don’t remember the name of the movie now.
01:58:49 You can probably find it easily enough, but it features dozens and dozens of
01:58:54 pianos all playing together at the same time. But all the scenery is sort of based on the kind
01:59:02 of artwork that was in his books and the fantasy, you know, based of Seussland or something.
01:59:14 And I saw the movie only once or twice, but it’s quite… I’d like to see it again.
01:59:22 That’s really fascinating that you gave him… They gave him a shout out here.
01:59:26 Okay. Is there some elegant basic symbol that you’re attracted to? Something that
01:59:34 gives you pleasure? Something you use a lot? Pi?
01:59:39 Pi, of course. I try to use pi as often as I can when I need a random example
01:59:47 because it doesn’t have any known characters. So for instance, I don’t have it here to show you,
01:59:59 but do you know the game called Masyu? M A S Y U?
02:00:06 No.
02:00:08 It’s a great recreation. I mean, Sudoku is easier to understand, but Masyu
02:00:15 is more addictive. You have black and white stones, like on a go board, and you have to
02:00:24 draw a path that goes straight through a white stone and makes a right angle turn at the black
02:00:30 stone. And it turns out to be a really nice puzzle because it doesn’t involve numbers.
02:00:39 It’s visual, but it’s really pleasant to play with. So I wanted to use it as an example in
02:00:48 art of computer programming, and I have exercises on how to design cool Masyu puzzles. You can find
02:00:57 on Wikipedia certainly as an example, M A S Y U. And so I decided I would take pi, the actual image
02:01:10 of it, and it had pixels, and I would put a stone wherever it belongs in the Greek letter pi.
02:01:20 But the problem was, find a way to make some of the stones white, some of the stones black,
02:01:26 so that there’s a unique solution to the Masyu puzzle. That was a good test case for my algorithm
02:01:33 on how to design Masyu puzzles because I insisted in advance that the stones had to be placed in
02:01:40 exactly the positions that make the letter pi, make a Greek letter pi. And it turned out there
02:01:49 was a unique way to do that. And so pi is a source of examples where I can prove that I’m starting
02:02:01 with something that isn’t canned. And most recently, I was writing about something called
02:02:08 graceful graphs. Graceful graphs is the following. You have a graph that has M edges to it,
02:02:20 and you attach numbers to every vertex in the following way. So every time you have an edge
02:02:27 between vertices, you take the difference between those numbers, and that difference
02:02:34 has got to be… I’ll tell you what edge it is. So one edge, two numbers will be one apart. There’ll
02:02:41 be another edge where the numbers are two apart. And so it’s a great computer problem. Can you
02:02:48 find a graceful way to label a graph? So I started with a graph that I use for
02:02:55 an organic graph, not a mathematically symmetric graph or anything. And I take 49 states of the
02:03:04 United States, the edges go from one state to the next state. So for example, California
02:03:12 be next to Oregon, Nevada, Arizona. And I include District of Columbia, so I have 49. I can’t get
02:03:24 Alaska and Hawaii in there because they don’t touch. You have to be able to drive from one to
02:03:30 the other. So is there a graceful labeling of the United States? Each state gets a number,
02:03:37 and then if California is number 30 and Oregon is number 11, that edge is going to be number 19,
02:03:45 the difference between those, okay? So is there a way to do this for all the states? And so I was
02:03:52 thinking of having a contest for people to get it as graceful as they could. But my friend,
02:04:02 Tom Rokicki, actually solved the problem by proving that, I mean, I was able to get it down
02:04:10 within seven or something like that. He was able to get a perfect solution.
02:04:14 The actual solution or to prove that a solution exists?
02:04:17 Well, more precisely, I had figured out a way to put labels on so that all the edges were labeled
02:04:25 somewhere between 1 and 117, but there were some gaps in there because I should really have gone
02:04:32 from 1 to 105 or whatever the number is. So I gave myself a lot of slack. He did it without
02:04:41 any slack whatsoever, a perfect graceful labeling. And so I called out the contest because the
02:04:49 problem’s already solved and too easy in a sense because Tom was able to do it in an afternoon.
02:04:55 Sorry, he gave the algorithm or for this particular…
02:04:59 For the United States.
02:05:00 For the United States.
02:05:01 This problem is incredibly hard. I mean…
02:05:05 For the general algorithm. But it was very lucky that it worked for the United States, I think.
02:05:13 The theory is still very incomplete. But anyway, then Tom came back a couple of days later and he
02:05:19 had been able to not only find a graceful labeling, but the label of Washington was 31,
02:05:26 and the label of Idaho was 41, following the digits of pi. Going across the top edge of the
02:05:38 United States, he has the digits of pi perfectly.
02:05:41 Did he do it on purpose?
02:05:43 He was able to still get a graceful labeling with that extra thing.
02:05:48 What? Wow.
02:05:50 Wow.
02:05:51 And it’s a miracle, okay? But I like to use pi in my book, you see.
02:06:02 All roads lead to pi. Somehow often hidden in the middle of the most difficult problems.
02:06:12 Can I ask you about productivity?
02:06:16 Productivity.
02:06:17 Yeah, you said that, quote, my scheduling principle is to do the thing I hate most
02:06:25 on my to do list. By week’s end, I’m very happy. Can you explain this process to a productive life?
02:06:33 Oh, I see. Well, but all the time I’m working on what I don’t want to do,
02:06:39 but still, I’m glad to have all those unpleasant tasks finished.
02:06:42 Yes. Is that something you would advise to others?
02:06:46 Well, yeah, I don’t know how to say it. During the pandemic, I feel my productivity actually
02:06:54 went down by half because I have to communicate by writing, which is slow. I don’t like to send
02:07:07 out a bad sentence. So I go through and reread what I’ve written and edit and fix it. So everything
02:07:14 takes a lot longer when I’m communicating by text messages instead of just together with somebody
02:07:25 in a room. And it’s also slower because the libraries are closed and stuff.
02:07:31 But there’s another thing about scheduling that I learned from my mother that I should
02:07:35 probably tell you, and that is it’s different from what people in the robotics field do,
02:07:42 which is called planning. So she had this principle that was,
02:07:49 see something that needs to be done and do it.
02:07:54 Instead of saying, I’m going to do this first and do this first, just pick this up.
02:08:03 But at any one moment, there’s a set of tasks that you can do. And you’re saying a good heuristic
02:08:12 is to do the one you want to do least.
02:08:15 Right. The one I haven’t got any good reason,
02:08:20 that I’ll never be able to do it any better than I am now. There are some things that I know,
02:08:29 if I do something else first, then I’ll be able to do that one better.
02:08:32 Yeah.
02:08:33 But there are some that are going to be harder because I’ve forgotten some of the
02:08:40 groundwork that went into it or something like that. So I just finished a pretty tough part of
02:08:46 the book. And so now I’m doing the parts that are more fun. But the other thing is, as I’m
02:08:56 writing the book, of course, I want the reader to think that I’m happy all the time I’m writing
02:09:02 the book. It’s upbeat. I can have humor. I can say this is cool. And this, I have to disguise
02:09:14 the fact that it was painful in any way to come up with these.
02:09:18 The road to that excitement is painful. Yeah. It’s laden with pain. Okay. You’ve given some
02:09:25 advice to people before, but can you…
02:09:30 You give me too much credit. But anyway, this is my turn to say things that I believe. But
02:09:39 I want to preface it by saying I also believe that other people do these things much better
02:09:48 than I do. So I can only tell you my side of it.
02:09:52 Right. So can I ask you to give advice to young people today, to high school students,
02:10:01 to college students, whether they’re geeks or the other kind, about how to live a life
02:10:08 that they can be proud of, how to have a successful career, how to have a successful life?
02:10:13 It’s always the same as I’ve said before, I guess, not to do something because it’s
02:10:24 trendy, but something that you personally feel that you were called to do rather than
02:10:32 somebody else expects you to do. How do you know you’re called to do something?
02:10:37 If you try it and it works or it doesn’t work. I mean, you learn about yourself. Life is
02:10:45 a binary search. You try something and you find out, oh yeah, I have a background that
02:10:49 helped me with this. Or maybe I could do this if I worked a little bit harder. But you try
02:10:57 something else and you say, well, I have really no intuition for this and it looks like it
02:11:04 doesn’t have my name on it. Was there advice along the way that you got about what you
02:11:12 should and shouldn’t work on? Or do you just try to listen to yourself? Yeah, I probably
02:11:18 overreact another way. When I see everybody else going some way, I probably say, hmm,
02:11:27 not too much competition. But mostly I played with things that were interesting to me and
02:11:37 then later on I found, oh, actually the most important thing I learned was how to be interested
02:11:43 in almost anything. I mean, not to be bored. It makes me very sad when I see kids talking
02:11:51 to each other and they say, that was boring. And to me, a person should feel upset if he
02:12:06 had to admit that he wasn’t able to find something interesting. It’s a skill they
02:12:13 think, I haven’t learned how to enjoy life. I have to have somebody entertain me instead of…
02:12:20 Right. That’s really interesting. It is a skill. David Foster Wallace, I really like
02:12:27 the thing he says about this, which is the key to life is to be unborable. And I do really like
02:12:34 you saying that it’s a skill because I think that’s a really good advice, which is if you
02:12:40 find something boring, that’s not… I don’t believe it’s because it’s boring. It’s because
02:12:49 you haven’t developed a skill. I haven’t learned how to…
02:12:51 How to find the beauty in that, how to find the fun in it. That’s a really good point.
02:12:58 Sometimes it’s more difficult than others to do this. I mean, during the COVID,
02:13:06 lots of days when I never saw another human being, but I still find other ways to…
02:13:14 It still was a pretty fun time.
02:13:18 Yeah. I came a few minutes early today and I walked around Foster City. I didn’t know
02:13:28 what was going on in Foster City. I saw some beautiful flowers at the nursery at Home Depot
02:13:33 a few blocks away.
02:13:34 Yeah. Life is amazing. It’s full of amazing things like this. Yeah. Sometimes I’ll sit
02:13:42 there and just stare at a tree. Nature is beautiful. Let me ask you the big ridiculous
02:13:48 question. I don’t think I asked you last time. So I have to ask this time in case you have
02:13:52 a good answer. What is the meaning of life? Our existence here on earth, the whole thing.
02:14:06 No, no, you can’t. I will not allow you to try to escape answering this question.
02:14:11 You have to answer definitively because surely, surely, Don Knuth, there must be an answer.
02:14:19 What is the answer? Is it 42?
02:14:22 Yes. Well, I don’t think it’s a numerical. That’s the SDS.
02:14:26 That was in Zen and… All right. So anyway, it’s only for me, but I personally
02:14:37 think of my belief that God exists, although I have no idea what that means. But I believe
02:14:48 that there is something beyond human capabilities. It might be some AI, but whatever it is. But
02:15:06 whatever. But I do believe that there is something that goes beyond the realm of human understanding,
02:15:17 but that I can try to learn more about how to resonate with whatever that being would
02:15:29 like me to do. So you think you can have occasional glimpses
02:15:34 of that being? I strive for that. Not that I ever think
02:15:42 I’m going to get close to it, but it’s not for me. It’s saying, what should I do that
02:15:49 that being wants me to do? I’m trying to ask, does that being want me to be talking to Lex
02:16:03 Friedman right now? And I said, yes. Okay. Thank you.
02:16:09 Well, thank you. What I’m trying to say is, of all the strategies I could choose or something,
02:16:22 I try to do it not strategically, but I try to imagine that I’m following somebody’s wishes.
02:16:33 Even though you’re not smart enough to know what they are.
02:16:37 Yeah. It’s that funny little dance. Well, I mean, this AI or whatever,
02:16:43 probably is smart enough to help to give me clues.
02:16:51 And to make the whole journey from clue to clue a fun one.
02:16:56 Yeah. As so many people have said, it’s the journey, not the destination.
02:17:00 And people live through crises, help each other. Things come up, history repeats itself.
02:17:12 You try to say, in the world today, is there any government that’s working? I read history. I know
02:17:20 that things were… They were a lot worse in many ways.
02:17:28 There’s a lot of bad things all the time. And I read about… I look at things and people had
02:17:36 good ideas and they were working on great projects. And then I know that it didn’t succeed, though,
02:17:42 in the end. But the new insight I’ve gotten actually in that way was… I was reading…
02:17:50 What book was I reading recently? It was by Ken Follett and it was called The Man from
02:17:56 St. Petersburg. But it was talking about the prequel to World War I. And Winston Churchill,
02:18:05 according to this book, sees that Germany has been spending all its gold reserves
02:18:11 building up a huge military. And there’s no question that if Germany would attack England,
02:18:18 that England would be wiped out. So he wants Russia to help to attack Germany from the other side,
02:18:27 because Germany doesn’t have enough of an army to be fighting two wars at one.
02:18:33 Okay. Now, then there’s an anarchist in Russia who sees that wars are something that leaders
02:18:45 start, but actually people get killed. And so he wants to stop any alliance between England and
02:18:56 Russia, because that would mean that thousands and thousands of people of Russia would be killed
02:19:03 that wouldn’t be otherwise killed. All right. And so his life’s goal is to assassinate a Russian
02:19:13 prince who’s visiting England, because that will mean the Tsar will not form the alliance. All
02:19:20 right. So we have this question about what should the government do? Should it actually do something
02:19:29 that will lead to… Is the war inevitable or is there a way to have peace? And it struck me that
02:19:37 if I were in a position of responsibility for people’s lives, in most cases, I wouldn’t have
02:19:46 any confidence that any of my decisions were good. That these questions are too hard, probably for
02:19:54 any human being, but certainly for me. Well, I think coupling the not being sure that the
02:20:04 decisions are right. So that’s actually a really good thing, coupled with the fact that you do have
02:20:11 to make a decision and carry the burden of that. And ultimately I have faith in human beings and
02:20:20 the great leaders to arise and help build a better world. I mean, that’s the hope of democracy.
02:20:27 Yeah, Ben, let’s hope that we can enhance their abilities with algorithms.
02:20:40 Well put, Don. It’s such a huge honor. You’ve been an inspiration to me and to millions for
02:20:46 such a long time. Thank you for spending your really valuable time with me. Once again,
02:20:52 it’s a huge honor. I really enjoyed this conversation.
02:20:54 Thanks for listening to this conversation with Donald Knuth. To support this podcast,
02:21:00 please check out our sponsors in the description. And now let me leave you with some words from
02:21:05 Don Knuth himself. Science is what we understand well enough to explain to a computer. Art is
02:21:12 everything else we do. Thank you for listening and hope to see you next time.