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

Lex Fridman (03:27.920)

And so I started working at the computer center and wrote some manuals then. But this was the

Lex Fridman (03:41.600)

way we did it. And my first program then was June of 1957. The Tic Tac Toe?

Donald Knuth (03:48.320)

No, that was the second program. The first, the third program. The first program was

Donald Knuth (03:52.800)

factoring a number. So you dial a number on the switches. I mean, you sat at this big mainframe

Lex Fridman (04:05.120)

and you turn the dials, set a number, and then it would punch out the factors of that number

Lex Fridman (04:12.400)

on cards. So that's the input, is the number?

Donald Knuth (04:15.440)

The input was, yeah, the input was a number, a tentative number. And the output was its factors.

Lex Fridman (04:26.560)

And I wrote that program. I still have a copy of it somewhere.

Lex Fridman (04:34.320)

How many lines of code? Do you remember?

Donald Knuth (04:36.080)

Well, yeah, it started out as about 20, but then I kept having to debug it.

Lex Fridman (04:40.960)

And I discovered debugging, of course, when I wrote my first program.

Lex Fridman (04:45.280)

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

Donald Knuth (04:50.800)

Well, you sit there and you, I don't remember how I got it into the machine, but I think there was

Donald Knuth (04:55.840)

a way to punch it on cards. So each instruction would be one card. Or maybe I could get seven

Donald Knuth (05:02.560)

instructions on a card, eight instructions. I don't know. But anyway, so I'm sitting there

Donald Knuth (05:06.320)

at the console of the machine. I mean, I'm doing this at night when nobody else is around.

Lex Fridman (05:10.400)

Of course.

Lex Fridman (05:11.680)

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

Donald Knuth (05:17.520)

switch that says, okay, now execute one instruction and show me what you did. Or there was another four

Donald Knuth (05:26.560)

switches that say, stop if you get to that instruction. So I can say, now go until you

Donald Knuth (05:33.200)

get there again and watch. So I could watch, it would take that number and it would divide it by

Donald Knuth (05:39.920)

two. And if there's no remainder, then okay, two is a factor. So then I work on it. But if not

Donald Knuth (05:48.160)

divisible by two, divide by three. Keep trying until you know you're at the end.

Lex Fridman (05:55.680)

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

Lex Fridman (06:02.720)

Well, certainly. I mean, first of all, I might have

Donald Knuth (06:05.200)

tried to divide by one instead of two. You go off by one error, as people make all the time.

Lex Fridman (06:11.040)

Yes.

Lex Fridman (06:11.520)

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

Donald Knuth (06:18.800)

done. But the first bugs were pretty... Probably on the first night, I was able to get the factors

Donald Knuth (06:26.480)

of 30 as equal to two, three, and five. Okay.

Lex Fridman (06:29.200)

Sorry to interrupt. So you're sitting there late at night.

Donald Knuth (06:36.000)

Yeah.

Lex Fridman (06:36.400)

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

Donald Knuth (06:42.480)

Oh, yeah.

Lex Fridman (06:43.280)

So what's that like? So most of the world is sleeping. And you have to be there at night

Donald Knuth (06:49.280)

because that's when you get access to the computer.

Donald Knuth (06:51.520)

Between my freshman and sophomore year, I didn't need sleep. I used to do all nighters.

Donald Knuth (06:56.320)

When I was in high school, I used to do the whole student newspaper every Monday night.

Lex Fridman (07:04.800)

I would just stay up all night and it would be done on Tuesday morning.

Donald Knuth (07:12.560)

I didn't get ulcers and stuff like that until later.

Lex Fridman (07:18.000)

I don't know if you know Rodney Brooks.

Donald Knuth (07:19.760)

Rod Brooks, of course.

Donald Knuth (07:20.880)

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

Donald Knuth (07:29.360)

Well, vice versa, I must say.

Lex Fridman (07:32.400)

But he tells a story when you were working on tech that they screwed up something with

Donald Knuth (07:37.680)

a machine. I think this might have been MIT. I don't know. And you were waiting for them

Lex Fridman (07:42.800)

to fix the machine so you can get back to work late at night.

Donald Knuth (07:47.760)

That happened all the time.

Lex Fridman (07:49.440)

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

Donald Knuth (07:54.000)

That's interesting. But no, the machine at Stanford AI Lab was down an awful lot because

Lex Fridman (08:05.760)

they had many talented programmers changing the operating system every day.

Lex Fridman (08:09.840)

So the operating system was getting better every day, but it was also crashing.

Lex Fridman (08:14.480)

So I wrote almost the entire manual for tech during downtime of that machine.

Lex Fridman (08:23.280)

But that's another story.

Donald Knuth (08:24.400)

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

Donald Knuth (08:30.480)

something and smoke was everywhere.

Lex Fridman (08:32.080)

Oh, wow. Well, that didn't happen as often as the operating system.

Donald Knuth (08:38.480)

It's a funny story because he was saying there's this tall Don Knuth that I look up to

Lex Fridman (08:44.160)

and there was pressure to fix the computer. It's funny.

Donald Knuth (08:51.680)

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

Donald Knuth (08:54.080)

Well, okay. Yeah. Well, I could tell you a bunch of Rod Brooks stories too, but let's

Donald Knuth (09:00.160)

go back to the 650. So I'm debugging my first program and I had more bugs in it than a number

Donald Knuth (09:12.480)

of lines of code. I mean, the number of lines of code kept growing. And let me explain.

Lex Fridman (09:17.520)

So I had to punch the answers on cards. So suppose I'm factoring the number 30, then

Donald Knuth (09:26.080)

I got to put two somewhere on the card. I got to put a three somewhere on the card.

Donald Knuth (09:31.040)

I got to put a five somewhere on the card. And here's my first program. I probably screwed up

Lex Fridman (09:37.680)

and it fell off the edge of the card or something like that. But I didn't realize that there are

Donald Knuth (09:44.720)

some tentative numbers that have more than eight factors. And the card has only 80 columns. And so

Donald Knuth (09:53.200)

I need 10 columns for every factor. So my first program didn't take account for the fact that I

Donald Knuth (09:58.560)

would have to punch more than one card. My first program just lined stuff up in memory and then

Donald Knuth (10:03.920)

punched the card. So by the time I finished, I had to deal with lots of things. Also,

Donald Knuth (10:14.960)

if you put a large prime number in there, my program might have sat there for 10 minutes.

Donald Knuth (10:20.240)

The 650 was pretty slow. And so it would sit there spinning its wheels and you wouldn't know

Lex Fridman (10:24.000)

if it was in a loop or whatever. You said 10 digit?

Donald Knuth (10:26.800)

10 digits. Yeah. So I think the largest is sort of 999999997 or something like that.

Donald Knuth (10:36.240)

That would take me a while for that first one. Anyway, that was my first program.

Donald Knuth (10:40.960)

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

Donald Knuth (10:46.560)

prime maybe or the opposite? No, my goal was to see the lights flashing and understand how this

Donald Knuth (10:54.160)

magical machine would be able to do something that took so long by hand. So what was your second

Donald Knuth (10:59.440)

program? My second program was a converted number from binary to decimal or something like that. It

Donald Knuth (11:08.880)

was much simpler. It didn't have that many bugs in it. My third program was tic tac toe.

Donald Knuth (11:14.400)

Yeah. And it had some machines. So the tic tac toe program is interesting on many levels,

Lex Fridman (11:20.560)

but one of them is that it had some you can call machine learning in it.

Donald Knuth (11:26.800)

Yeah, that's right. I don't know how long it's going to be before the name of our field has

Donald Knuth (11:34.240)

changed from computer science to machine learning. But anyway, it was my first experience with

Donald Knuth (11:42.560)

machine learning. Okay. So here we had... Yeah. How does the program... Well, first of all,

Lex Fridman (11:46.880)

what is the problem you were solving? What is tic tac toe? What are we talking about? And then

Lex Fridman (11:54.880)

how was it designed? Right. So you've got a three by three grid and each

Donald Knuth (12:03.040)

can be in three states. It can be empty or it can have an X or an O. Yeah. All right. So three to

Donald Knuth (12:08.640)

the ninth is a... Well, how big is it? I should know. But it's 81 times three. So anyway, eight

Donald Knuth (12:26.400)

is like two to the third. And so that would be like two to the sixth. But that would be 64.

Donald Knuth (12:35.680)

Then you have to... Anyway, I love how you're doing the calculation. So it's a lot of... Anyway,

Donald Knuth (12:41.280)

the three comes from the fact that it's either empty, an X or an O. Right. And the 650 was a

Donald Knuth (12:49.680)

machine that had only two thousand ten digit words. You go from zero zero zero zero to one

Donald Knuth (13:00.720)

nine nine nine and that's it. And each word you have a ten digit number. So that's not many bits.

Donald Knuth (13:09.360)

I mean, I got to have... In order to have a memory of every position I've seen,

Donald Knuth (13:14.480)

I need three to the ninth bits. Okay. But it was a decimal machine too. It didn't have bits.

Lex Fridman (13:21.840)

But it did have strange instruction where if you had a ten digit number, but all the digits were

Donald Knuth (13:29.600)

either eight or nine, you'd be eight, nine, nine, eight or something like that. You could make a

Donald Knuth (13:38.400)

test whether it was eight or nine. That was one of the strange things IBM engineers put into the

Donald Knuth (13:43.760)

machine. I have no idea why. Well, hardly ever used. But anyway, I needed one digit for every

Donald Knuth (13:51.840)

position I'd seen. Zero meant it was a bad position. Nine meant it was good position.

Lex Fridman (13:57.360)

And I think I started out at five or six. But if you win a game, then you increase the value of

Donald Knuth (14:06.400)

that position for you, but you decrease it for your opponent. But I had that much total memory

Donald Knuth (14:18.240)

for every possible position was one digit. And I had a total of 20,000 digits, which had to also

Donald Knuth (14:25.760)

include my program and all the logic and everything, including how to ask the user what the moves are

Lex Fridman (14:34.320)

and things like this. So I think I had to work it out. Every position in tic tac toe is equivalent

Donald Knuth (14:41.920)

to roughly eight others because you can rotate the board, which gives you a factor of four,

Lex Fridman (14:49.120)

and you can also flip it over. And that's another factor too. So I might have needed only three to

Donald Knuth (14:55.680)

the ninth over eight positions plus a little bit. But anyway, that was a part of the program to

Donald Knuth (15:05.520)

squeeze it into this tiny... So you tried to find an efficient representation that took

Donald Knuth (15:11.200)

account for that kind of rotation. I had to, otherwise I couldn't do the learning.

Lex Fridman (15:18.080)

But I had three parts to my tic tac toe program. And I called it brain one, brain two, and brain

Donald Knuth (15:24.880)

three. So brain one just played at random. It's your turn. Okay. You got to put an X somewhere.

Donald Knuth (15:39.440)

It has to go in an empty space, but that's it. Okay. Choose one and play it. Brain two

Donald Knuth (15:48.640)

had a canned routine. And I think it also... Maybe it assumed you were the first player,

Donald Knuth (15:59.200)

or maybe it allowed you to be first. I think you're allowed to be either first or second,

Lex Fridman (16:03.440)

but had a canned built in strategy known to be optimum for tic tac toe. Before I forget,

Donald Knuth (16:09.760)

by the way, I learned many years later that Charles Babbage had thought about programming

Donald Knuth (16:18.480)

tic tac toe for his dream machine that he was never able to finish.

Lex Fridman (16:23.760)

Wow. So that was the program he thought about.

Donald Knuth (16:26.400)

More than 100 years ago. He did that. Okay. And I had, however, been influenced by a

Donald Knuth (16:37.120)

demonstration at the Museum of Science and Industry in Chicago. It's like Boston Science

Donald Knuth (16:42.960)

Museum. I think Bell Labs had prepared a special exhibit about telephones and relay technology,

Lex Fridman (16:50.800)

and they had a tic tac toe playing machine as part of that exhibit. So that had been one of my...

Donald Knuth (17:00.160)

Something I'd seen before I was a freshman in college and inspired me to see if I could

Donald Knuth (17:05.120)

write a program for it. Okay. So anyway, I had brain one, random, knowing nothing. Brain two,

Donald Knuth (17:13.920)

knowing everything. Then brain three was the learning one. And I could play brain one against

Donald Knuth (17:22.080)

brain one, brain one against brain two, and so on. And so you could also play against the user,

Donald Knuth (17:28.800)

against the live users. So I started going, the learning thing, and I said, okay, take two random

Donald Knuth (17:37.520)

people just playing tic tac toe knowing nothing. And after about... I forget the number now, but

Donald Knuth (17:49.040)

it converged after about 600 games to a safe draw. The way my program learned was actually,

Lex Fridman (17:57.440)

it learned how not to make mistakes. It didn't try to do anything for winning,

Donald Knuth (18:04.800)

it just tried to say not losing. So that was probably because of the way I designed the

Donald Knuth (18:10.320)

learning thing. I could have had a different reinforcement function that would reward brilliant

Donald Knuth (18:18.080)

play. And if I took a novice against a skilled player, it was able to learn how to play a good

Donald Knuth (18:29.360)

game. And that was really my... But after I finished that, I felt I understood programming.

Lex Fridman (18:38.240)

Yeah. Did a curiosity and interest in learning systems persist for you?

Lex Fridman (18:48.880)

So why did you want brain three to learn? Yeah. I think naturally, we're talking about

Donald Knuth (18:58.320)

Rod Brooks. He was teaching all kinds of very small devices to learn stuff. If a leaf drops

Lex Fridman (19:08.000)

off of a tree, he was saying something, well, it learns if there's wind or not.

Lex Fridman (19:17.200)

But I mean, he pushed that a little bit too far. But he said he could probably train some little

Lex Fridman (19:22.480)

mini bugs to scour out dishes if he had enough financial support. I don't know.

Donald Knuth (19:28.000)

Can I ask you about that? He also mentioned that during those years, there was discussion

Lex Fridman (19:39.440)

inspired by Turing about computation, of what is computation.

Donald Knuth (19:45.680)

Yeah. I never thought about any stuff like that. That was way too philosophical. I was a freshman

Lex Fridman (1:00:04.480)

It simulates the cellular automata, like Game of Life?

Donald Knuth (1:00:07.680)

Yeah, you got to check it out.

Lex Fridman (1:00:10.480)

Can I ask you about John Conway?

Donald Knuth (1:00:12.640)

Yes. In fact, I'm just reading now the issue of mathematical intelligence that came in last

Lex Fridman (1:00:19.600)

week. It's a whole issue devoted to remembrance of him.

Lex Fridman (1:00:28.320)

Did you know him?

Lex Fridman (1:00:30.560)

I slept overnight in his house several times.

Donald Knuth (1:00:35.680)

Yeah.

Lex Fridman (1:00:36.320)

He recently passed away.

Donald Knuth (1:00:38.800)

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

Lex Fridman (1:00:46.160)

What are some memories of him, of his work, that stand out for you? On a technical level,

Lex Fridman (1:00:58.240)

did any of his work inspire you? On a personal level, did he himself inspire you in some way?

Donald Knuth (1:01:06.480)

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

Donald Knuth (1:01:11.360)

him at Oxford in 1967 when I was... Okay, that's a long time ago.

Donald Knuth (1:01:17.120)

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

Donald Knuth (1:01:28.720)

I think I was speaking about something known as the Knuth Bendix algorithm now, but he gave a

Donald Knuth (1:01:37.760)

famous talk about knots. And I didn't know at the time, but anyway, that talk had now...

Donald Knuth (1:01:47.680)

The source of thousands and thousands of papers since then. And he was reported on something that

Donald Knuth (1:01:54.560)

he had done in high school almost 10 years earlier before this conference, but he never published it.

Lex Fridman (1:02:04.560)

And he climaxed his talk by building some knots. You have these little plastic things that you

Donald Knuth (1:02:13.760)

can stick together. It's something like Lego, but easier. And so he made a whole bunch of knots

Donald Knuth (1:02:23.200)

in front of the audience and so on and then disassembled it. So it was a dramatic lecture

Lex Fridman (1:02:29.200)

before he had learned how to give even more dramatic lectures later.

Lex Fridman (1:02:33.680)

Were you at that lecture?

Lex Fridman (1:02:37.920)

And I was there, yeah, because I was at the same conference. For some reason, I happened to be in

Donald Knuth (1:02:46.240)

Calgary the same day that he was visiting Calgary. And it was the spring of 72, I'm pretty sure.

Lex Fridman (1:02:56.400)

And we had lunch together and he wrote down during the lunch on a napkin all of the facts about

Lex Fridman (1:03:08.160)

what he called numbers. And he covered the napkin with the theorems about his

Donald Knuth (1:03:17.680)

idea of numbers. And I thought it was incredibly beautiful. And later in 1972, my sabbatical year

Donald Knuth (1:03:31.280)

began and I went to Norway. And in December of that year, in the middle of the night,

Donald Knuth (1:03:39.120)

the thought came to me, you know, Conway's theory about numbers would be a great thing to teach

Donald Knuth (1:03:46.480)

students how to invent research and what the joys are of research. And I had also read a book in

Donald Knuth (1:03:57.680)

dialogue by Alfred Renyi, kind of a Socratic thing where the two characters were talking

Donald Knuth (1:04:06.800)

to each other about mathematics. And so at the end, in the morning, I woke up my wife and said,

Donald Knuth (1:04:16.800)

Jill, I think I want to write a book about Conway's theory. And, you know, I'm supposed

Donald Knuth (1:04:27.440)

to be writing the Art of Computer Program and doing all this other stuff, but I really want

Donald Knuth (1:04:32.400)

to write this other book. And so we made this plan. But I said, I thought I could write it in a week.

Lex Fridman (1:04:40.400)

And we made the plan then. So in January, I rented a room in a hotel in downtown Oslo.

Donald Knuth (1:04:47.920)

We were in sabbatical in Norway. And I rented the hotel in downtown Oslo and did nothing else

Donald Knuth (1:04:56.160)

except write up Conway's theory. And I changed the name to Surreal Numbers. And so this book

Donald Knuth (1:05:02.960)

is now published as Surreal Numbers. And, you know, we figured out, we'd always wonder what

Donald Knuth (1:05:11.360)

would be like to have a fair enough hotel room. So we figured out that she would visit me twice

Donald Knuth (1:05:16.080)

during the week. Things like this, you know, we would try to sneak in. This hotel was run by a

Donald Knuth (1:05:24.400)

mission organization. These ladies were probably very strict, but anyway. So, and it's a wild week

Donald Knuth (1:05:34.320)

in every way. But the thing is, I had lost that. I had lost that napkin in which he wrote the

Donald Knuth (1:05:38.880)

theory, but I looked for it, but I couldn't find it. So I tried to recreate from memory what he

Donald Knuth (1:05:46.960)

had told me at that lunch in Calgary. And as I wrote the book, I was going through exactly what

Donald Knuth (1:05:55.600)

I, what the characters in the book were supposed to be doing. So I start with the two axioms that

Donald Knuth (1:06:01.440)

start out the whole thing and everything is defined, flows from that, but you have to discover

Donald Knuth (1:06:06.000)

why. And every mistake that I make as I'm trying to discover it, my characters make too. And so

Donald Knuth (1:06:15.680)

it's a long, long story. But I worked through this week and it was one of the most intense

Donald Knuth (1:06:25.760)

weeks of my life and I described it in other places. But anyway, after six days, I finished it

Lex Fridman (1:06:36.160)

and on the seventh day I rested and I sent to my secretary to type it. It was flowing as I was

Donald Knuth (1:06:44.720)

writing it faster than I could think almost. But after I finished and tried to write a letter to

Donald Knuth (1:06:54.080)

my secretary telling her how to type it, I couldn't write anymore. You gave it everything.

Lex Fridman (1:06:59.520)

The muse had left me completely. Can you explain how that week could have happened? Like why?

Donald Knuth (1:07:05.280)

That seems like such a magical week of productivity. I have no idea. But anyway,

Donald Knuth (1:07:08.640)

there was some... It was almost as if I was channeling. So the book was typed,

Lex Fridman (1:07:15.920)

they sent it to Conway and he said, well, Don, you got the one axiom wrong.

Donald Knuth (1:07:24.080)

Is there a difference between less than or equal and not greater than? The opposite of being

Donald Knuth (1:07:32.240)

greater than and less than or equal. But anyway, technically it can make a difference when you're

Donald Knuth (1:07:38.880)

developing a logical theory. And the way I had chosen was harder to do than John's original.

Lex Fridman (1:07:47.840)

And we visited him at his house in Cambridge in April. We took a boat actually from Norway

Donald Knuth (1:07:53.840)

over to across the channel and so on and stayed with him for some days. And we talked

Donald Knuth (1:08:01.920)

about all kinds of things he had. He had puzzles that I'd never heard of before. He had a great way

Donald Knuth (1:08:12.160)

to solve the game of solitaire. Many of the common interests that he'd never written them up.

Lex Fridman (1:08:19.680)

But anyway, then in the summertime, I took another week off and went to a

Donald Knuth (1:08:25.360)

Conway place in the mountains of Norway and rewrote the book using the correct axiom.

Lex Fridman (1:08:34.400)

So that was the most intensive connection with Conway. After that...

Donald Knuth (1:08:40.080)

It started with a napkin.

Lex Fridman (1:08:41.440)

It started with a napkin. But we would run into each other. The next really...

Lex Fridman (1:08:50.160)

And I was giving lectures in Montreal. I was giving a series of seven lectures about the

Donald Knuth (1:09:02.000)

topic called Stable Marriages. And he arrived in Montreal between my sixth and seventh lecture.

Lex Fridman (1:09:11.600)

And we met at a party. And I started telling him about the topic I was doing. And he sat and

Donald Knuth (1:09:20.560)

thought about it. He came up with a beautiful theory to show that the... I mean, in technical

Donald Knuth (1:09:26.240)

terms, it's that the set of all stable marriages forms a lattice. And there was a simple way to

Donald Knuth (1:09:34.400)

find the greatest lower bound of two stable pairings and least upper bound of two stable

Donald Knuth (1:09:41.200)

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

Donald Knuth (1:09:46.160)

during the party. And it's a distributive lattice. It added greatly to the theory of stable matching.

Lex Fridman (1:09:59.200)

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

Donald Knuth (1:10:07.360)

you two met? So we celebrated 60 years of wedded bliss last month. And we met because I was dating

Donald Knuth (1:10:17.440)

her roommate. This was my sophomore year, her freshman year. I was dating her roommate. And

Donald Knuth (1:10:24.480)

I wanted her advice on strategy or something like this. And anyway, I found I enjoyed her advice

Lex Fridman (1:10:33.120)

better than her. I enjoyed her roommate. You guys were majoring the same thing?

Donald Knuth (1:10:39.440)

No, no, no. Because I read something about working on a computer in grad school on a difficult

Donald Knuth (1:10:46.880)

computer science topic. So she's an artist and I'm a geek.

Lex Fridman (1:10:55.520)

What was she doing with a computer science book? Was it the manual that she was reading?

Lex Fridman (1:11:01.920)

What was she reading? I wrote the manual that she had to take a

Lex Fridman (1:11:05.840)

class in computer science. So you're the tutor?

Donald Knuth (1:11:10.480)

No, no. There were terrible times trying to learn certain concepts, but I learned art from her.

Lex Fridman (1:11:23.680)

And so we worked together occasionally in design projects. But every year we write a Christmas card

Lex Fridman (1:11:32.240)

and we each have to compromise our own notions of beauty.

Donald Knuth (1:11:40.720)

When did you fall in love with her? That day that I asked her about her roommate.

Donald Knuth (1:11:48.480)

I don't mind telling these things, depending on how far you go.

Lex Fridman (1:11:59.120)

I promise not to go too far.

Donald Knuth (1:12:05.280)

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

Lex Fridman (1:12:13.600)

Wow. And 60 years.

Lex Fridman (1:12:20.240)

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

Lex Fridman (1:12:27.360)

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

Donald Knuth (1:12:33.600)

Yes. It's a joke, Don.

Lex Fridman (1:12:36.480)

But two different people will have to learn how to compromise and work together and

Donald Knuth (1:12:48.080)

you're going to have ups and downs and crises and so on. And so as long as you don't

Donald Knuth (1:12:56.000)

set your expectation on having 24 hours of bliss, then there's a lot of hope for stability.

Lex Fridman (1:13:04.640)

But if you decide that there's going to be no frustration, then...

Lex Fridman (1:13:13.200)

So you're going to have to compromise on your notions of beauty when you write Christmas cards.

Donald Knuth (1:13:18.000)

That's it.

Lex Fridman (1:13:21.840)

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

Donald Knuth (1:13:25.600)

Yeah.

Lex Fridman (1:13:26.960)

Probably you've met him in Caltech.

Donald Knuth (1:13:28.800)

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

Donald Knuth (1:13:35.760)

You are one of the seminal personalities of computer science. He's one for physics.

Lex Fridman (1:13:43.280)

Is there specific things you picked up from him by way of inspiration?

Lex Fridman (1:13:49.440)

So we used to go to each other's lectures.

Lex Fridman (1:13:51.600)

But if I saw him sitting in the front row, it would throw me for a loop, actually. I would

Donald Knuth (1:13:59.360)

miss a few sentences. What unique story do I have? I often refer to his time in Brazil

Donald Knuth (1:14:11.600)

where he essentially said they were teaching all the physics students the wrong way. They were just

Donald Knuth (1:14:18.720)

learning how to pass exams and not learning any physics. And he said, if you want me to prove it,

Donald Knuth (1:14:27.200)

here, I'll turn any page of this textbook and I'll tell you what's wrong with this page. And

Donald Knuth (1:14:32.720)

he did so. And the textbook had been written by his host, and he was a great teacher. And he

Donald Knuth (1:14:39.440)

had previously asked his host if he was supposed to tell the truth. But anyway, it epitomizes the

Donald Knuth (1:14:47.040)

way education goes wrong in all kinds of fields and has to periodically be brought back from a

Donald Knuth (1:15:00.480)

process of giving credentials to a process of giving knowledge.

Donald Knuth (1:15:10.720)

That's probably a story that continues to this day in a bunch of places where it's too easy for

Donald Knuth (1:15:19.840)

educational institutions to fall into credentialism versus inspirationalism.

Donald Knuth (1:15:26.480)

I don't know if those are words, but sort of understanding versus just giving a little

Donald Knuth (1:15:36.080)

plaque.

Donald Knuth (1:15:39.360)

It's very much like what we were talking about. If you want to be able to believe

Donald Knuth (1:15:45.200)

the answer, a computer is doing that. One of the things Bob Floyd showed me in the 60s,

Donald Knuth (1:15:51.440)

there was a... He loved this cartoon. There were two guys standing in front of... In those days,

Donald Knuth (1:15:59.520)

a computer was a big thing. And the first guy says to the other guy, he said,

Donald Knuth (1:16:04.240)

this machine can do in one second what it would take a million people to do in a hundred years.

Lex Fridman (1:16:12.080)

And the other guy says, oh, so how do you know it's right?

Lex Fridman (1:16:14.640)

That's a good line.

Lex Fridman (1:16:21.600)

Is there some interesting distinction between physics and math to you?

Lex Fridman (1:16:26.160)

Have you looked at physics much? Speaking of Richard Feynman,

Donald Knuth (1:16:31.520)

the difference between the physics community, the physics way of thinking, the physics intuition

Lex Fridman (1:16:36.000)

versus the theoretical computer science, the mathematical sciences,

Lex Fridman (1:16:40.640)

do you see that as a gap? Are they strongly overlapping?

Donald Knuth (1:16:44.880)

It's quite different, in my opinion. I started as a physics major and I switched into math.

Lex Fridman (1:16:52.080)

And probably the reason was that I could get A plus on the physics exam, but I never had any

Donald Knuth (1:16:59.680)

idea why I would have been able to come up with the problems that were on those exams.

Lex Fridman (1:17:05.040)

But in math, I knew why the teacher set those problems and I thought of other problems that

Lex Fridman (1:17:13.520)

I could set, too. And I believe it's quite a different mentality.

Lex Fridman (1:17:20.400)

It has to do with your philosophy of geekdom?

Donald Knuth (1:17:23.920)

No, it's... I mean, some of my computer scientist friends are really good at physics and others are

Donald Knuth (1:17:30.720)

really good at physics and others are not. And I'm really good at algebra, but not at geometry.

Donald Knuth (1:17:39.840)

Talk about different parts of mathematics. So there are different kinds of physics,

Lex Fridman (1:17:44.800)

but physicists think of things in terms of waves. And I can think of things in terms of waves,

Lex Fridman (1:17:51.680)

but it's like a dog walking on hind legs if I'm thinking about it.

Lex Fridman (1:17:54.960)

So you basically like to see the world in discrete ways and then physics is more continuous.

Donald Knuth (1:18:02.800)

Yeah. I'm not sure if Turing would have been a great physicist. I think he was a pretty good

Donald Knuth (1:18:10.720)

chemist, but I don't know. But anyway, I see things... I believe that computer science is

Donald Knuth (1:18:19.680)

largely driven by people who have brains who are good at resonating with certain kinds of concepts.

Lex Fridman (1:18:34.480)

And like quantum computers, it takes a different kind of brain.

Donald Knuth (1:18:37.440)

Yeah, that's interesting. Yeah. Well, quantum computers is almost like at the intersection

Donald Knuth (1:18:42.640)

in terms of brain between computer science and physics because it involves both at least at this

Donald Knuth (1:18:50.960)

time. But there is like the physicists I've known, they have incredibly powerful intuition.

Lex Fridman (1:18:59.280)

And I mean, statistical mechanics. So I study statistical mechanics and I mean,

Donald Knuth (1:19:08.880)

random processes are related to algorithms in a lot of ways. But there's lots of different

Donald Knuth (1:19:15.600)

flavors of physics as there are different flavors of mathematics as well. But the thing is that I

Donald Knuth (1:19:23.200)

don't see... Well, actually, when they talk to physicists, they use a completely different

Donald Knuth (1:19:30.240)

language than when they're writing expository papers. And so I didn't understand quantum

Donald Knuth (1:19:36.640)

mechanics at all from reading about it in Scientific American. But when I read how they

Donald Knuth (1:19:42.720)

describe it to each other, talking about eigenvalues and various mathematical terms that

Donald Knuth (1:19:50.800)

made sense, then it made sense to me. But Hawking said that every formula you put in a book,

Donald Knuth (1:19:58.800)

you lose half of your readers. And so he didn't put any formulas in the book. So I couldn't

Donald Knuth (1:20:02.480)

understand his book at all. You could say you understood it, but I really didn't.

Donald Knuth (1:20:10.720)

Well, Feynman also spoke in this way. So Feynman, I think, prided himself on really strong

Donald Knuth (1:20:17.680)

intuition. But at the same time, he was hiding all the really good, the deep computation he was

Donald Knuth (1:20:23.440)

doing. So there was one thing that I was never able to... I wish I'd had more time to work out

Donald Knuth (1:20:32.000)

with him. But I guess I could describe it for you. There's something that got my name attached to it

Donald Knuth (1:20:39.520)

called Knuth arrow notation. But it's a notation for very large numbers. And so I find out that

Donald Knuth (1:20:48.720)

somebody invented it in the 1830s. It's fairly easy to understand anyway. So you start with

Donald Knuth (1:20:56.720)

x plus x plus x plus x n times, and you can call that xn. So xn is multiplication. Then you take x

Donald Knuth (1:21:08.560)

times x times x times x n times. That gives you exponentiation, x to the nth power. So that's one

Donald Knuth (1:21:17.600)

arrow. So xn with no arrows is multiplication. Arrow n is x to the nth power.

Donald Knuth (1:21:25.280)

Yeah. So just to clarify for the... So x times x times x n times is obviously xn.

Donald Knuth (1:21:36.400)

x plus x plus x n times.

Donald Knuth (1:21:39.200)

Oh, yeah. Okay. And then multiplication is x to the n. And then here the arrow is when you're

Donald Knuth (1:21:47.840)

doing the same kind of repetitive operation for the exponential.

Lex Fridman (1:21:51.760)

So I put in one arrow, and I get x to the nth power. Now I put in two arrows. And that takes

Donald Knuth (1:21:57.440)

x to the x to the x to the x n times power. So in other words, if it's two double arrow three,

Donald Knuth (1:22:08.480)

that would be two to the two to the two. So that would be two to the fourth power. That'd be 16.

Donald Knuth (1:22:15.840)

Okay. So that's the double arrow. And now you can do a triple arrow, of course, and so on.

Lex Fridman (1:22:28.720)

And I had this paper called, well, essentially big numbers. You try to impress your friend,

Lex Fridman (1:22:38.960)

but by saying a number they've never thought of before. And I gave a special name for it

Lex Fridman (1:22:47.360)

and designed a font for it that has script k and so on. But it really is 10, I think,

Donald Knuth (1:22:53.680)

like 10 quadruple arrow three or something like that. And I claim that that number is so mind

Donald Knuth (1:23:00.560)

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

Lex Fridman (1:23:07.120)

and he said, oh, let's just use double arrow. But instead of taking integers, let's consider

Donald Knuth (1:23:15.440)

complex numbers. I mean, okay, x arrow arrow two, that means x to the x. But what about x

Donald Knuth (1:23:27.600)

double arrow 2.5? Well, that's not too hard to figure out. That's interpolate between those.

Lex Fridman (1:23:34.880)

But what about x double arrow i or 1 plus i or some complex number?

Lex Fridman (1:23:42.960)

And so he claimed that there was no analytic function that would do the job.

Lex Fridman (1:23:54.640)

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

Lex Fridman (1:24:03.600)

did then have a complex number of arrows?

Lex Fridman (1:24:09.440)

Yeah. Okay.

Donald Knuth (1:24:10.400)

Wow. Okay.

Lex Fridman (1:24:11.200)

Okay. So that's Feynman.

Donald Knuth (1:24:13.680)

That's Feynman.

Lex Fridman (1:24:14.400)

Yeah.

Lex Fridman (1:24:16.080)

Can you describe what the Knuth Morris Pratt algorithm does? And how did you come to develop

Donald Knuth (1:24:24.080)

it? One of the many things that you're known for and has your name attached to it.

Donald Knuth (1:24:28.640)

Yeah. All right. So it should be actually Morris Pratt Knuth. But we decided to use

Donald Knuth (1:24:36.080)

alphabetical order when we published the paper. The problem is something that everybody knows

Donald Knuth (1:24:42.800)

now if they're using a search engine. You have a large collection of text, and you want to know

Donald Knuth (1:24:53.040)

if the word Knuth appears anywhere in the text, let's say, or some other word that's less

Donald Knuth (1:25:01.280)

interesting than Knuth. But anyway. That's the most interesting word.

Lex Fridman (1:25:05.040)

Like Morris or something. Like Morris, right.

Lex Fridman (1:25:07.440)

So anyway, we have a large piece of text, and it's all one long, one dimensional thing. First

Donald Knuth (1:25:16.480)

letter, second letter, et cetera, et cetera, et cetera. And so you'd like to be able to do this

Donald Knuth (1:25:24.240)

quickly. And the obvious way is let's say we're looking for Morris. Okay. So we would go through

Lex Fridman (1:25:33.840)

and wait till we get to letter M. Then we look at the next word, and sure enough, it's an O,

Lex Fridman (1:25:39.280)

and then an R. But then, too bad, the next letter is E. So we missed out on Morris. And so we go

Donald Knuth (1:25:52.880)

back and start looking for another. So that's the obvious way to do it. All right. And Jim Morris

Donald Knuth (1:26:01.440)

noticed there was a more clever way to do it. The obvious way would have started... Let's say

Donald Knuth (1:26:10.800)

we found that letter M had character position 1000. So it would have started next at character

Donald Knuth (1:26:16.880)

position 1001. But he said, no, look, we already read the O and the R, and we know that they aren't

Donald Knuth (1:26:26.560)

Ms. So we can start... We don't have to read those over again. And this gets pretty tricky when

Donald Knuth (1:26:37.840)

the word isn't Morris, but it's more like abracadabra, where you have patterns that

Donald Knuth (1:26:43.520)

are occurring. Like repeating patterns at the beginning, at the middle, at the end.

Donald Knuth (1:26:49.760)

Right. So he worked it out, and he put it into the system software at Berkeley, I think it was,

Donald Knuth (1:26:57.680)

where he was writing some... Berkeley Unix, I think, was some routine that was supposed to

Donald Knuth (1:27:03.600)

find occurrences of patterns in text. But he didn't explain it. And so he found out that several

Donald Knuth (1:27:14.320)

months later, somebody had looked at it, didn't look right, and so they ripped it out. So he had

Donald Knuth (1:27:20.960)

this algorithm, but it didn't make it through because it wasn't understood. Nobody knew about

Donald Knuth (1:27:28.560)

this particularly. Von Pratt also had independently discovered it a year or two later. I forget why.

Donald Knuth (1:27:39.360)

I think Von was studying some technical problem about palindromes or something like that. He

Donald Knuth (1:27:48.800)

wasn't really... Von wasn't working on text searching, but he was working on an abstract

Donald Knuth (1:27:56.320)

problem that was related. Well, at that time, Steve Cook was professor at Berkeley, and

Donald Knuth (1:28:04.480)

it was the greatest mistake that Berkeley CS department made was not to give him tenure.

Lex Fridman (1:28:13.120)

So Steve went to Toronto. But I knew Steve while he was at Berkeley,

Lex Fridman (1:28:20.800)

and he had come up with a very peculiar theorem about a technical concept called a stack automaton.

Lex Fridman (1:28:29.120)

And a stack automaton is a machine that can't do everything a Turing machine can do, but it

Donald Knuth (1:28:38.080)

can only look at something at the top of a stack, or it can put more things on the stack, or it can

Donald Knuth (1:28:44.560)

take things off of the stack. It can't remember a long string of symbols, but it can remember them

Donald Knuth (1:28:51.760)

in reverse order. So if you tell a stack automaton A, B, C, D, E, it can tell you afterwards E, D,

Donald Knuth (1:29:00.240)

C, B, A. It doesn't have any other memory except this one thing that it can see. And Steve Cook

Donald Knuth (1:29:08.320)

proved this amazing thing that says if a stack automaton can recognize a language where the

Donald Knuth (1:29:16.800)

strings of the language are length n in any amount of time whatsoever, so the stack automaton might

Donald Knuth (1:29:24.320)

use a zillion steps, a regular computer can recognize that same language in time n log n.

Lex Fridman (1:29:30.800)

So Steve had a way of transforming a computation that goes on and on and on and on

Donald Knuth (1:29:38.800)

using different data structures into something that you can do on a regular computer

Donald Knuth (1:29:43.360)

fast. The stack automaton goes slow, but somehow the fact that it can do it at all

Donald Knuth (1:29:53.280)

means that there has to be a fast way. So I thought this was a pretty cool theorem.

Lex Fridman (1:29:59.680)

And so I tried it out on a problem where I knew a stack automaton could do it,

Lex Fridman (1:30:08.320)

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

Donald Knuth (1:30:12.720)

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

Lex Fridman (1:30:22.880)

So I went through Steve Cook's construction. I filled my blackboard with everything that

Donald Knuth (1:30:29.920)

stack automaton did. I wrote down, and then I tried to see patterns in that.

Lex Fridman (1:30:37.520)

And how did he convert that into a computer program on a regular machine? And finally,

Donald Knuth (1:30:44.720)

I psyched it out. What was the thing I was missing so that I could say, oh yeah, this is what I

Donald Knuth (1:30:52.080)

should do in my program. And now I have an efficient program. And so I would never have

Donald Knuth (1:31:01.040)

thought about that if I hadn't had his theorem, which was a purely abstract thing.

Lex Fridman (1:31:09.120)

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

Donald Knuth (1:31:16.160)

problem. Yeah. So the problem I had started with was not the string matching problem,

Lex Fridman (1:31:23.600)

but then I realized that the string matching problem was another thing which could be done

Donald Knuth (1:31:28.720)

by a stack automaton. And so when I looked at what that told me, then I had a nice algorithm for this

Donald Knuth (1:31:36.640)

string matching problem. And it told me exactly what I should remember as I'm going through the

Donald Knuth (1:31:44.320)

string. And I worked it out, and I wrote this little paper called Automata Theory Can Be Useful.

Lex Fridman (1:31:52.240)

And the reason was that it was first, I mean, I had been reading all kinds of papers about

Donald Knuth (1:31:56.720)

automata theory, but it never improved my programming for everyday problems. It was

Donald Knuth (1:32:04.880)

something that you published in journals, and it was interesting stuff. But here was a case

Donald Knuth (1:32:11.920)

where I couldn't figure out how to write the program. I had a theorem from automata theory.

Donald Knuth (1:32:16.960)

Then I knew how to write the program. So this was, for me, a change in life. I started to say,

Donald Knuth (1:32:25.200)

maybe I should learn more about automata theory. And I showed this note to Vaughn Pratt,

Lex Fridman (1:32:32.560)

and he said, that's similar to something I was working on. And Jim Morris was at Berkeley,

Donald Knuth (1:32:41.520)

too, at the time. Anyway, he's had an illustrious career, but I haven't kept track of Jim. But Vaughn

Donald Knuth (1:32:49.760)

is my colleague at Stanford and my student later. But this was before Vaughn was still a graduate

Donald Knuth (1:32:58.240)

student and hadn't come to Stanford yet. So we found out that we'd all been working on the

Donald Knuth (1:33:02.400)

same thing. So it was our algorithm. We each discovered it independently, but each of us

Donald Knuth (1:33:07.360)

had discovered a different part of the elephant, a different aspect of it. And so we could put our

Lex Fridman (1:33:15.520)

things together with my job to write the paper. How did the elephant spring to life?

Donald Knuth (1:33:23.520)

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

Donald Knuth (1:33:30.400)

Oh. It can be useful, which was seen by Vaughn and then by Jim. And then we combined,

Donald Knuth (1:33:36.560)

because maybe they had also been thinking of writing something up about it.

Lex Fridman (1:33:40.800)

About specifically the string match problem in a period.

Donald Knuth (1:33:48.480)

Let me ask a ridiculous question. Last time we talked, you told me what the most beautiful

Donald Knuth (1:33:54.080)

algorithm is, actually, for strongly connected graphs. What is the hardest problem, puzzle,

Donald Knuth (1:34:03.440)

idea in computer science for you personally that you had to work through? Just something that was

Donald Knuth (1:34:09.280)

just the hardest thing that I've ever been involved with. I don't know how to answer

Donald Knuth (1:34:17.600)

questions like that, but in this case, it's pretty clear because it's called the birth of

Donald Knuth (1:34:29.120)

the giant component. So now let me explain that because this actually gets into physics too.

Lex Fridman (1:34:35.600)

And it gets into something called Bose Einstein statistics. But anyway, it's got some interesting

Donald Knuth (1:34:44.560)

stories and it's connected with Berkeley again. So start with the idea of a random graph.

Donald Knuth (1:34:52.480)

Now, here we just say we have N points that are totally unconnected and there's no geometry

Donald Knuth (1:35:02.880)

involved. There's no saying some points are further apart than others. All points are exactly

Donald Knuth (1:35:09.840)

alike. And let's say we have 100 points and we number them from 0 to 99.

Donald Knuth (1:35:19.280)

Now let's take pi, the digits of pi, so two at a time. So we had 31, 41, 59, 26. We can

Donald Knuth (1:35:31.040)

look, go through pi. And so we take the first two, 31, 41, and let's put a connection between

Donald Knuth (1:35:41.440)

0.31 and 0.41. That's an edge in the graph. Then we take 59, 26 and make another edge.

Lex Fridman (1:35:52.560)

And the graph gets bigger, gets more and more connected as we add these things one at a time.

Lex Fridman (1:36:00.240)

So we started out with N points and we add M edges. Each edge is completely, we forgot about

Donald Knuth (1:36:10.720)

edges we had before. We might get an edge twice. We might get an edge from a point to itself even.

Donald Knuth (1:36:16.880)

Maybe pi is going to have a run of four digits in there. But anyway, we're evolving a graph at

Donald Knuth (1:36:26.080)

random. And a magical thing happens when the number of edges is like 0.49 N, so maybe N is a

Donald Knuth (1:36:40.080)

million and I have 490,000 edges. Then almost all the time, it consists of isolated trees,

Donald Knuth (1:36:55.440)

not even any loops.

Lex Fridman (1:36:58.640)

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

Donald Knuth (1:37:01.680)

A little less than half N.

Lex Fridman (1:37:03.680)

N, right.

Donald Knuth (1:37:04.720)

A little less than half N. But if I had 0.51 edges, so a little more than half N.

Lex Fridman (1:37:12.000)

So a million points, 510,000 edges. Now it probably has

Donald Knuth (1:37:24.080)

one component that's much bigger than the others. And we call that the giant component.

Lex Fridman (1:37:30.960)

So can you clarify? First of all, is there a name for this kind of random,

Lex Fridman (1:37:37.600)

super cool pi random graph?

Donald Knuth (1:37:41.200)

Well, I call it the pi graph. No, no, the pi graph is actually, my pi graph is based on

Donald Knuth (1:37:51.840)

binary representation of pi, not the decimal representation of pi. But anyway, let's suppose

Lex Fridman (1:37:59.360)

I was rolling dice instead. So it doesn't have to be pi?

Donald Knuth (1:38:07.040)

The point is, every step, choose totally at random one of those endpoints,

Donald Knuth (1:38:13.280)

choose totally at random another one of those endpoints, make that an edge. That's the process.

Lex Fridman (1:38:21.440)

So there's nothing magical about pi?

Donald Knuth (1:38:23.520)

No, no, I was sort of saying pi is sort of random that nobody knows the pattern in.

Donald Knuth (1:38:29.840)

Exactly, got it.

Lex Fridman (1:38:31.760)

But I could have just as well drawn straws or something. This was a concept invented by

Donald Knuth (1:38:39.760)

Erdos and Renyi, and they call it the evolution of random graphs. And if you start out with

Donald Knuth (1:38:45.680)

a large number N, and you repeat this process, all of a sudden a big bang happens at one half N.

Donald Knuth (1:38:52.960)

There'll be two points together, then maybe we'll have three. And then maybe branch out a little

Donald Knuth (1:39:01.680)

bit. But they'll all be separate until we get to one half N. And we pass one half N, and all of a

Donald Knuth (1:39:08.160)

sudden there's substance to it. There's a big clump of stuff that's all joined together.

Lex Fridman (1:39:16.240)

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

Donald Knuth (1:39:19.040)

It's exactly. It's a phase transition, but it's a double phase transition. It turns out

Donald Knuth (1:39:27.760)

that there's actually two things going on at once at this phase transition, which is very

Donald Knuth (1:39:34.080)

remarkable about it. So a lot of the most important algorithms are based on random

Donald Knuth (1:39:40.400)

processes. And so I want to understand random processes now. So there are data structures that

Donald Knuth (1:39:46.560)

sort of grow this way. Okay, so Dick Karp, one of the leading experts on randomized algorithms,

Donald Knuth (1:39:56.000)

had his students looking at this at Berkeley. And we heard a rumor that the students had

Donald Knuth (1:40:02.640)

found something interesting happening. The students are generating this,

Donald Knuth (1:40:08.080)

or simulating this random evolution of graphs. And they're taking snapshots every so often to

Donald Knuth (1:40:17.600)

take a look at what the graph is. And the rumor was that every time they looked,

Donald Knuth (1:40:23.600)

there was only one component that had loops in it, almost always. They do a million experiments,

Lex Fridman (1:40:30.000)

and only three or four times did they ever happen to see a loop at this point.

Donald Knuth (1:40:35.920)

I mean, no, more than one component with a loop. So they watch it until the graph gets

Donald Knuth (1:40:43.840)

completely full. So it starts out totally empty and gets more and more edges all the time.

Lex Fridman (1:40:52.400)

And so, okay, certainly a loop comes along once. But now all the loops stay somehow joined to that

Donald Knuth (1:40:59.200)

one. There never were two guys with loops in these experiments. So anyway, almost always,

Lex Fridman (1:41:12.400)

certainly not always, but with very high probability this seemed to be true.

Lex Fridman (1:41:19.200)

So we heard about this rumor at Stanford, and we said, if that's true, then a lot more must also

Donald Knuth (1:41:26.880)

be true. So there's a whole theory out there waiting to be discovered that we haven't ever

Donald Knuth (1:41:31.680)

thought about. So let's take a look at it. And so we looked closer and we found out, no, actually,

Donald Knuth (1:41:37.200)

it's not true. But in fact, it's almost true. Namely, there's a very short interval of time

Donald Knuth (1:41:46.240)

when it's true. And if you don't happen to look at it during that short interval of time,

Donald Knuth (1:41:51.840)

then you miss it. So in other words, there'll be a period where there are two or three

Donald Knuth (1:42:00.320)

components that have loops, but they join together pretty soon.

Donald Knuth (1:42:05.440)

Okay. So if you don't have a real fast shutter speed, you're going to miss that instant.

Lex Fridman (1:42:15.680)

So separate loops don't exist for long.

Donald Knuth (1:42:18.320)

That's it. Yeah. I started looking at this to make it quantitative. And the basic problem was

Donald Knuth (1:42:25.440)

to slow down the Big Bang so that I could watch it happening. I think I can explain it actually

Donald Knuth (1:42:32.880)

in fairly elementary terms, even without writing a formula, like Hawking would do.

Lex Fridman (1:42:38.720)

And so let's watch the evolution. And at first, these edges are coming along and they're just

Donald Knuth (1:42:47.600)

making things without loops, which we call trees. So then all of a sudden, a loop first appears.

Lex Fridman (1:42:54.640)

So at that point, I have one component that has a loop. Now, I say that the complexity of a

Donald Knuth (1:43:01.440)

component is the number of edges minus the number of vertices. So if I have a loop, I have like a

Donald Knuth (1:43:10.720)

loop of length five, it has five edges and five vertices. Or I could put a tail on that and that

Lex Fridman (1:43:19.840)

would be another edge, another vertex.

Donald Knuth (1:43:21.440)

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

Lex Fridman (1:43:24.880)

So if the complexity is zero, we have one loop, I call it a cycle or I call it a cyclic

Donald Knuth (1:43:32.880)

component. So a cyclic component looks like a wheel to which you attach fibers or trees.

Donald Knuth (1:43:45.840)

They go branching, but there are no more loops. There's only one loop and everything else

Donald Knuth (1:43:49.280)

feeds into that loop. And that has complexity zero. But a tree itself has complexity minus one

Donald Knuth (1:43:57.440)

because it might have 10 vertices and nine edges to tie them together. So nine minus 10 is minus

Donald Knuth (1:44:06.800)

one. So complexity minus one is a tree. It's got to be connected. That's what I mean by a

Donald Knuth (1:44:14.000)

component. It's got to be connected. So if I have 10 things connected, I have to have nine edges.

Lex Fridman (1:44:21.360)

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

Donald Knuth (1:44:28.880)

Right. So the complexity plus one is the number of loops. So if complexity is zero,

Donald Knuth (1:44:34.560)

I have one loop. If complexity is one, that means I have one more edge than I have vertices. So I

Donald Knuth (1:44:43.280)

might have like 11 edges and 10 vertices. So we call that a bicycle because it's got two loops

Lex Fridman (1:44:53.040)

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?

Donald Knuth (1:45:02.000)

I would need more edges then. Oh, right. Right. Okay. I got it. So every time I get another loop,

Donald Knuth (1:45:08.800)

I get another excess of edges over vertices. I got you. Okay. So in other words,

Donald Knuth (1:45:15.840)

we start out and after I have one loop, I have one component that has a cycle in it.

Donald Knuth (1:45:23.200)

Now the next step, according to the rumor, would be that at the next step, I would have a bicycle

Donald Knuth (1:45:31.520)

in the evolution of almost all graphs. It would go from cycle to bicycle. But in fact,

Donald Knuth (1:45:39.280)

there's a certain probability it goes from cycle to two different cycles.

Lex Fridman (1:45:48.800)

And I worked out the probability was something like five out of 24.

Donald Knuth (1:45:52.720)

That's pretty high.

Donald Knuth (1:45:53.520)

Right. It was substantial. But still, soon they're going to merge together almost. Okay.

Donald Knuth (1:46:02.480)

That's so cool.

Lex Fridman (1:46:03.600)

But then it splits again after you have either two or one, one. The next step is you either have

Donald Knuth (1:46:11.200)

three or you have two, one or you have one, one, one. Okay. And so I worked out the probability

Donald Knuth (1:46:17.920)

for those transitions. And I worked it out up to the first five transitions. And I had these

Donald Knuth (1:46:28.480)

strange numbers, five 24s. And I stayed up all night and about 3 a.m. I had the numbers computed

Lex Fridman (1:46:35.920)

and I looked at them. The denominator was something like 23023. The probability was

Donald Knuth (1:46:49.680)

something over 23023. I don't know how you worked that out.

Lex Fridman (1:46:53.280)

But I had a formula that I could calculate the probability. And I could find the limiting

Donald Knuth (1:46:58.640)

probability as n goes to infinity. And it turned out to be this number. But the denominator was

Donald Knuth (1:47:04.240)

230. And I looked at the denominator and I said, wait a minute. This number factors because

Donald Knuth (1:47:11.200)

1001 is equal to 7 times 11 times 13. I had learned that in my first computer program.

Lex Fridman (1:47:17.040)

So 23023 is 7 times 11 times 13 times 23. That's not a random number. There has to be a reason

Lex Fridman (1:47:31.040)

why those small primes appear in the denominator. So all of a sudden that suggested another way of

Donald Knuth (1:47:41.440)

looking at the problem where small prime factors would occur. So that said, oh, yeah, let me take

Donald Knuth (1:47:50.960)

the logarithm of this formula. And sure enough, it's going to simplify. And it happened. So I

Lex Fridman (1:47:59.840)

and I wouldn't have noticed it except for this factorization. OK, so I go to bed and I say,

Donald Knuth (1:48:05.280)

oh, OK, this is this looks like I'm slowing down the Big Bang. I can figure out what's going on

Donald Knuth (1:48:09.760)

here. And the next day it turned out Bill Gates comes to Stanford to visit. They're trying to

Donald Knuth (1:48:17.040)

sell him on donating money for a new computer science building. And they gave me an appointment

Donald Knuth (1:48:25.200)

to talk to Bill and I wrote down on the blackboard this evolutionary diagram going from one to two,

Donald Knuth (1:48:33.360)

five twenty fourths in all this business. And I wrote it down. And anyway, at the end of the day,

Donald Knuth (1:48:40.320)

he was discussing people with the development office and he said, boy, I was really impressed

Donald Knuth (1:48:46.400)

with what Professor Knuth said about this giant component. And and so, you know, I love this story

Donald Knuth (1:48:56.480)

because it shows that theoretical computer science is really worthwhile. Does Bill have you ever

Donald Knuth (1:49:03.200)

talked to Bill Gates about it since then? Yeah, that's a cool that's a cool little moment in

Donald Knuth (1:49:09.440)

history. But anyway, he happened to visit on exactly the day after I had I had found this

Donald Knuth (1:49:17.360)

pattern and that allowed me to crack the problem so that I could develop the theory some more and

Donald Knuth (1:49:25.920)

understand what's happening in the big. But because I could I could now write down explicit formulas

Donald Knuth (1:49:33.200)

for stuff. And so it would work not only the first few steps, but also they'll study the

Donald Knuth (1:49:39.840)

whole process. And and I worked further and further and I with two authors, co authors,

Lex Fridman (1:49:45.600)

and we finally figured out that the probability that the rumor was true. In other words,

Donald Knuth (1:49:53.600)

look at the evolution of a random graph going from zero to complete and say, what's the probability

Donald Knuth (1:50:02.800)

that at every point in time, there was only one component with a cycle? We started with this

Donald Knuth (1:50:09.200)

rumor saying there's only one site, there's only one component with a cycle. And so the rumor was

Donald Knuth (1:50:16.960)

it's 100%. Rumor was that was 100%. It turned out the actual numbers is like 87%. I should remember

Donald Knuth (1:50:26.160)

the number but I don't but I don't have it with me. But but anyway, but but the but the number it

Donald Knuth (1:50:33.440)

turned out to be like 12 over pi squared or eight over pi. Anyway, it was a nice it related to pi.

Donald Knuth (1:50:42.160)

Yeah. And we could never have done that with it. But so that's the hardest problem I ever

Donald Knuth (1:50:48.880)

solved in my life was to prove that this probability is it was proven. The probability

Donald Knuth (1:50:54.640)

was proven. Yeah, I was able to prove this that this and this should shed light on a whole bunch

Donald Knuth (1:51:01.280)

of other things about random graphs. That was sort of the major thing we were after.

Lex Fridman (1:51:07.600)

That's super cool. What was the connection to physics that you mentioned?

Donald Knuth (1:51:11.440)

Well, Bose Einstein statistics is a study of how molecules bond together

Donald Knuth (1:51:18.960)

without geometry. You created the tech typesetting system and released it as open source.

Lex Fridman (1:51:33.280)

Just on that little aspect, why did you release it as open source? What is your vision for open source?

Donald Knuth (1:51:42.160)

Okay, well that the word open source didn't exist at that time. But we but I didn't want

Donald Knuth (1:51:47.440)

proprietary rights over it. Because I saw how proprietary rights were holding things back.

Donald Knuth (1:51:56.720)

In the late 50s, people at IBM developed the language called Fortran. They could have

Donald Knuth (1:52:03.760)

kept it proprietary. They could have said only IBM can use this language. Everybody else has to.

Lex Fridman (1:52:09.440)

But they didn't. They said anybody who can translate Fortran into the language of their

Donald Knuth (1:52:18.160)

machines is allowed to make Fortran compilers. On the other hand, in the typography industry,

Lex Fridman (1:52:28.000)

I had seen a lot of languages that were developed for composing pages.

Lex Fridman (1:52:34.400)

And each manufacturer had his own language for composing pages. And that was holding everything

Donald Knuth (1:52:41.760)

back because people were tied to a particular manufacturer. And then a new equipment is invented

Donald Knuth (1:52:48.800)

a year later. But printing machines, they have to expect to amortize the cost over 20, 30 years.

Lex Fridman (1:52:55.680)

So you didn't want that for tech?

Donald Knuth (1:52:57.360)

That for tech. I didn't need the income. I already had a good job. And my books were,

Donald Knuth (1:53:14.640)

people were buying enough books that it would bring me plenty of supplemental income for

Donald Knuth (1:53:23.040)

everything my kids needed for education and whatever. So there was no reason for me to try

Donald Knuth (1:53:28.640)

to maximize income any further. Income is sort of a threshold function. If you don't have enough,

Donald Knuth (1:53:36.480)

you're starving. But if you get over the threshold, then you start thinking about

Donald Knuth (1:53:41.680)

philanthropy or else you're trying to take it with you. But anyway, my income was over the

Donald Knuth (1:53:51.200)

threshold. So I didn't need to keep it. And so I specifically could see the advantage of

Lex Fridman (1:54:00.560)

making it open for everybody.

Lex Fridman (1:54:02.640)

Do you think most software should be open?

Lex Fridman (1:54:06.080)

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

Donald Knuth (1:54:13.040)

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

Lex Fridman (1:54:21.280)

value.

Lex Fridman (1:54:22.880)

So it's definitely worth paying for all this stuff. I mean, well, they keep adding stuff that

Donald Knuth (1:54:33.760)

my wife and I don't care about, but they have built in a fantastic undo feature, for example,

Donald Knuth (1:54:47.040)

in Photoshop where you can go through a sequence of a thousand complicated steps on graphics and

Donald Knuth (1:54:54.800)

then it can take you back anywhere in that sequence with really beautiful algorithms.

Donald Knuth (1:55:03.360)

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

Lex Fridman (1:55:08.000)

representation.

Donald Knuth (1:55:08.800)

Yeah, no. I mean, there's a lot of really subtle Nobel Prize class creation of intellectual

Donald Knuth (1:55:16.800)

property in there. And with patents, you get a limited time to, I mean, eventually the

Donald Knuth (1:55:30.640)

idea of patents is that you publish so that it's not a trade secret.

Donald Knuth (1:55:37.200)

That said, you've said that I currently use Ubuntu Linux on a standalone laptop. It has

Donald Knuth (1:55:45.200)

no internet connection. I occasionally carry flash memory drives between the machine and

Donald Knuth (1:55:50.320)

the Macs that I use for network surfing and graphics, but I trust my family jewels only

Lex Fridman (1:55:57.280)

to Linux. Why do you love Linux?

Donald Knuth (1:56:00.880)

The version of Linux that I use is stable. Actually, I'm going to have to upgrade one

Donald Knuth (1:56:07.120)

of these days, but...

Lex Fridman (1:56:08.400)

To a newer version of Ubuntu?

Donald Knuth (1:56:10.320)

Yeah, I'll stick with Ubuntu, but right now I'm running something that doesn't support

Donald Knuth (1:56:18.000)

a lot of the new software. The last stable, I don't remember the number, like 14. Anyway,

Donald Knuth (1:56:26.880)

it's quite... And I'm going to get a new computer. I'm getting new solid state memory instead

Lex Fridman (1:56:35.280)

of a hard disk.

Donald Knuth (1:56:36.800)

Yeah, the basics. Well, let me ask you, sticking on the topic of tech, when thinking about

Donald Knuth (1:56:47.280)

beautiful typography, what is your favorite letter, number, or symbol? I know, I know.

Donald Knuth (1:56:56.080)

Ridiculous question, but is there some...

Lex Fridman (1:56:57.760)

Let me show you here.

Donald Knuth (1:56:59.440)

Look at the last page.

Lex Fridman (1:57:11.120)

The very end of the index.

Lex Fridman (1:57:15.200)

What is that?

Lex Fridman (1:57:17.040)

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

Lex Fridman (1:57:22.240)

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

Donald Knuth (1:57:24.480)

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

Lex Fridman (1:57:34.960)

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

Lex Fridman (1:57:36.880)

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

Donald Knuth (1:57:39.760)

I like how you had the spell there.

Lex Fridman (1:57:41.120)

On Beyond Zebra, did it get to Soviet Union?

Donald Knuth (1:57:46.080)

No, Dr. Seuss did not come to the Soviet Union, but since you... Oh, actually, I think it did

Donald Knuth (1:57:56.640)

actually a little bit when we were... That was a book, maybe Cat in the Hat or Green Eggs and Ham,

Donald Knuth (1:58:07.520)

I think was used to learn English.

Lex Fridman (1:58:10.320)

Oh, okay.

Lex Fridman (1:58:11.280)

So I think it made it in that way.

Donald Knuth (1:58:12.960)

Well, my... Okay, I didn't like those as much as Bartholomew Cubbins, but I used to know

Donald Knuth (1:58:21.760)

Bartholomew Cubbins by heart when I was young.

Lex Fridman (1:58:24.720)

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

Donald Knuth (1:58:28.800)

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

Lex Fridman (1:58:32.800)

Who made it?

Donald Knuth (1:58:34.080)

He did.

Lex Fridman (1:58:34.720)

He did. So there's... It looks like a bunch of vines.

Lex Fridman (1:58:39.440)

Well, is that symbol exist in fact?

Donald Knuth (1:58:41.760)

By the way, he made a movie in the early 50s. I don't remember the name of the movie now.

Donald Knuth (1:58:49.040)

You can probably find it easily enough, but it features dozens and dozens of

Donald Knuth (1:58:54.560)

pianos all playing together at the same time. But all the scenery is sort of based on the kind

Donald Knuth (1:59:02.480)

of artwork that was in his books and the fantasy, you know, based of Seussland or something.

Lex Fridman (1:59:14.320)

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

Donald Knuth (1:59:22.400)

That's really fascinating that you gave him... They gave him a shout out here.

Donald Knuth (1:59:26.960)

Okay. Is there some elegant basic symbol that you're attracted to? Something that

Lex Fridman (1:59:34.960)

gives you pleasure? Something you use a lot? Pi?

Lex Fridman (1:59:39.600)

Pi, of course. I try to use pi as often as I can when I need a random example

Donald Knuth (1:59:47.920)

because it doesn't have any known characters. So for instance, I don't have it here to show you,

Lex Fridman (1:59:59.440)

but do you know the game called Masyu? M A S Y U?

Donald Knuth (20:00.560)

after all. I was pretty much a machine.

Lex Fridman (20:07.040)

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

Donald Knuth (20:12.720)

Yeah. It was just exciting to me to be able to control something, but not to say, am I solving

Donald Knuth (20:21.920)

a big problem or something like that? Or is this a step for humankind? No, no way.

Donald Knuth (20:28.240)

When did you first start thinking about computation in the big sense? Like the

Donald Knuth (20:34.400)

universal Turing machine? I had to take classes on computability when I was a senior. So we read

Donald Knuth (20:47.040)

this book by Martin Davis. Yeah, this is cool stuff. But I learned about it because I needed

Donald Knuth (20:53.360)

to pass the exams. But I didn't invent any of that boring stuff. But I had great fun playing

Donald Knuth (21:00.720)

with the machine. I wrote programs because it was fun to write programs and get this.

Lex Fridman (21:11.120)

I mean, it was like watching miracles happen.

Donald Knuth (21:15.360)

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

Donald Knuth (21:22.400)

program changed. How the heck can you do that? Like, what makes a distinct style for a programmer,

Lex Fridman (21:31.680)

do you think? You know, there's different Hemingway has a style of writing versus James Joyce or

Donald Knuth (21:39.280)

something. Yeah, those are pretty easy to imitate. But it's the same with music and whatever.

Donald Knuth (21:45.920)

During the pandemic, I spent a lot more time playing the piano. And I found something that

Donald Knuth (21:55.520)

I'd had when I was taking lessons before I was a teenager. And it was Yankee Doodle

Donald Knuth (22:05.600)

who played in the style of... You had Beethoven and you had Debussy and Chopin, and the last one

Donald Knuth (22:16.880)

was Gershwin. And I played over and over again. I thought it was so brilliant. But it was so easy.

Lex Fridman (22:26.080)

But also to appreciate how this author, Mario, somebody or other, had been able to reverse

Donald Knuth (22:35.120)

engineer the styles of those composers. But now, specifically to your question, I mean, there would

Donald Knuth (22:43.040)

be... It was pretty obvious in this program I was reading. It was a compiler and it had been written

Donald Knuth (22:53.840)

by a team at Carnegie Mellon. And I have no idea which program was responsible for it. But you

Donald Knuth (23:03.600)

would get to a part where the guy would just not know how to move things between registers very

Donald Knuth (23:09.920)

efficiently. And so everything that could be done in one instruction would take three or something

Donald Knuth (23:16.160)

like that. That would be a pretty obvious change in style. But there were also flashes of brilliance

Donald Knuth (23:23.840)

where you could do in one instruction. Normally, I used two because you knew enough about the way

Donald Knuth (23:29.280)

the machine worked that you could accomplish two goals in one step. So it was mostly the

Donald Knuth (23:37.280)

brilliance of the concept more than the semicolons or the use of short sentences versus long sentences

Donald Knuth (23:45.440)

or something like that. So you would see the idea in the code and you could see the different style

Donald Knuth (23:50.960)

of thinking expressed in the code. Right. It was stylistic. I mean, I could identify authors by

Donald Knuth (23:57.840)

their by the amount of technical aptitude they had, but not by the style in the sense of

Lex Fridman (24:07.040)

rhythm or something like that. So if you think about Mozart, Beethoven, Bach,

Donald Knuth (24:11.840)

if somebody looked at Don Knuth code, would they be able to tell that this

Lex Fridman (24:19.600)

is a distinct style of thinking going on here? What do you think?

Lex Fridman (24:23.360)

And what would be the defining characteristic of the style?

Donald Knuth (24:28.400)

Well, my code now is literate programming. So it's a combination of English and C mostly. But

Donald Knuth (24:37.680)

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

Donald Knuth (24:46.160)

variables that other people don't. And I expand things in line more than instead of calling.

Donald Knuth (24:56.240)

Anyway, I have different subset of C that I use.

Lex Fridman (25:00.080)

Okay. But that's a little bit stylistic.

Lex Fridman (25:03.120)

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

Lex Fridman (25:10.880)

And by the way, people listening to this should look up literate programming. It's

Donald Knuth (25:14.560)

very interesting concept that you proposed and developed over the years.

Donald Knuth (25:21.040)

Yeah. That's the most significant thing, I think, to come out of the tech project is that I

Donald Knuth (25:32.800)

realized that my programs were to be read by people and not just by computers and that typography

Donald Knuth (25:45.120)

could massively enhance that. And so, I mean, they're just wonderful. If they're going to look

Donald Knuth (25:53.760)

it up, they should also look up this book called Physically Based Rendering by Matt Farr and,

Donald Knuth (26:02.240)

gosh, anyway, it got an Academy Award. But all the graphic effects you see in movies

Donald Knuth (26:13.520)

are accomplished by algorithms. And the whole book is a literate program. It tells you not

Donald Knuth (26:19.120)

only how you do all the shading and bring images in that you need for animation and

Donald Knuth (26:27.360)

textures and so on, but you can run the code. And so, I find it an extension of how to teach

Lex Fridman (26:42.080)

programming is by telling a story as part of the program.

Lex Fridman (26:47.680)

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

Lex Fridman (26:52.480)

Yes. And especially by me a week later or a year later.

Donald Knuth (26:58.720)

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

Lex Fridman (27:06.320)

Yeah. So it's the greatest thing since sliced bread.

Lex Fridman (27:12.720)

Programming or literate programming?

Lex Fridman (27:14.640)

Literate programming.

Donald Knuth (27:15.520)

Okay. You heard it here first. Okay. You dodged this question in an interview I listened to.

Lex Fridman (27:24.960)

So let me ask you again here. What makes for a beautiful program?

Lex Fridman (27:30.240)

What makes for a beautiful program?

Donald Knuth (27:31.840)

Yeah. What are the characteristics you see? Like you just said, literate programming.

Lex Fridman (27:36.640)

What are the characteristics you see in a program that make you sit back and say,

Donald Knuth (27:40.960)

that's pretty good? Well, the reason I didn't answer is because there are dozens and dozens

Donald Knuth (27:47.280)

of answers to that because you can define beauty, the same personal defined beauty,

Lex Fridman (27:54.960)

different way from hour to hour. I mean, it depends on what you're looking for.

Donald Knuth (27:59.120)

At one level, it's beautiful just if it works at all. At another level, it's beautiful if it can

Donald Knuth (28:10.960)

be understood easily. It's beautiful if it's literate programming. It's beautiful. It makes

Donald Knuth (28:19.760)

you laugh. I mean.

Lex Fridman (28:21.280)

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

Donald Knuth (28:27.120)

Readable, yeah.

Donald Knuth (28:28.000)

Is if you understand what's going on and also understand the elegance of thought behind it.

Lex Fridman (28:36.160)

And then also, as you said, wit and humor. I was always, I remember having this conversation,

Donald Knuth (28:42.880)

I had this conversation on Stack Overflow, whether humor is good in comments. And I think it is.

Donald Knuth (28:51.040)

Whether humor is good in comments.

Donald Knuth (28:53.120)

Like when you add comments in code, I always thought a little bit of humor is good.

Donald Knuth (29:00.000)

It shows personality. It shows character, shows wit and fun and all those kinds of things

Lex Fridman (29:07.280)

of the personality of the programmer.

Donald Knuth (29:08.800)

Yeah. Okay. So a couple of days ago, I received a wonderful present from my former editor at

Donald Knuth (29:17.040)

Aspen Wesley. He's downsizing his house and he found that somebody at the company had

Donald Knuth (29:26.880)

found all of their internal files about the art of computer programming from the 1960s

Lex Fridman (29:32.240)

and they gave it to him before throwing it in the garbage. And then so he said,

Donald Knuth (29:39.920)

oh yeah, he planned to keep it for posterity, but now he realized that posterity is

Donald Knuth (29:44.400)

a bit too much for him to handle, so he sent it to me. And so I just received this big stack

Donald Knuth (29:55.760)

of letters, some of which I had written to them, but many of which they had written to

Lex Fridman (2:00:06.240)

No.

Donald Knuth (2:00:08.080)

It's a great recreation. I mean, Sudoku is easier to understand, but Masyu

Donald Knuth (2:00:15.200)

is more addictive. You have black and white stones, like on a go board, and you have to

Donald Knuth (2:00:24.240)

draw a path that goes straight through a white stone and makes a right angle turn at the black

Donald Knuth (2:00:30.880)

stone. And it turns out to be a really nice puzzle because it doesn't involve numbers.

Donald Knuth (2:00:39.120)

It's visual, but it's really pleasant to play with. So I wanted to use it as an example in

Donald Knuth (2:00:48.640)

art of computer programming, and I have exercises on how to design cool Masyu puzzles. You can find

Donald Knuth (2:00:57.840)

on Wikipedia certainly as an example, M A S Y U. And so I decided I would take pi, the actual image

Donald Knuth (2:01:10.000)

of it, and it had pixels, and I would put a stone wherever it belongs in the Greek letter pi.

Lex Fridman (2:01:20.080)

But the problem was, find a way to make some of the stones white, some of the stones black,

Lex Fridman (2:01:26.400)

so that there's a unique solution to the Masyu puzzle. That was a good test case for my algorithm

Donald Knuth (2:01:33.680)

on how to design Masyu puzzles because I insisted in advance that the stones had to be placed in

Donald Knuth (2:01:40.400)

exactly the positions that make the letter pi, make a Greek letter pi. And it turned out there

Donald Knuth (2:01:49.600)

was a unique way to do that. And so pi is a source of examples where I can prove that I'm starting

Donald Knuth (2:02:01.680)

with something that isn't canned. And most recently, I was writing about something called

Donald Knuth (2:02:08.560)

graceful graphs. Graceful graphs is the following. You have a graph that has M edges to it,

Lex Fridman (2:02:20.960)

and you attach numbers to every vertex in the following way. So every time you have an edge

Donald Knuth (2:02:27.680)

between vertices, you take the difference between those numbers, and that difference

Donald Knuth (2:02:34.480)

has got to be... I'll tell you what edge it is. So one edge, two numbers will be one apart. There'll

Donald Knuth (2:02:41.520)

be another edge where the numbers are two apart. And so it's a great computer problem. Can you

Lex Fridman (2:02:48.240)

find a graceful way to label a graph? So I started with a graph that I use for

Donald Knuth (2:02:55.600)

an organic graph, not a mathematically symmetric graph or anything. And I take 49 states of the

Donald Knuth (2:03:04.720)

United States, the edges go from one state to the next state. So for example, California

Donald Knuth (2:03:12.000)

be next to Oregon, Nevada, Arizona. And I include District of Columbia, so I have 49. I can't get

Donald Knuth (2:03:24.320)

Alaska and Hawaii in there because they don't touch. You have to be able to drive from one to

Donald Knuth (2:03:30.000)

the other. So is there a graceful labeling of the United States? Each state gets a number,

Lex Fridman (2:03:37.600)

and then if California is number 30 and Oregon is number 11, that edge is going to be number 19,

Donald Knuth (2:03:45.120)

the difference between those, okay? So is there a way to do this for all the states? And so I was

Donald Knuth (2:03:52.960)

thinking of having a contest for people to get it as graceful as they could. But my friend,

Donald Knuth (2:04:02.160)

Tom Rokicki, actually solved the problem by proving that, I mean, I was able to get it down

Lex Fridman (2:04:10.560)

within seven or something like that. He was able to get a perfect solution.

Lex Fridman (2:04:14.640)

The actual solution or to prove that a solution exists?

Donald Knuth (2:04:17.200)

Well, more precisely, I had figured out a way to put labels on so that all the edges were labeled

Donald Knuth (2:04:25.440)

somewhere between 1 and 117, but there were some gaps in there because I should really have gone

Donald Knuth (2:04:32.480)

from 1 to 105 or whatever the number is. So I gave myself a lot of slack. He did it without

Donald Knuth (2:04:41.280)

any slack whatsoever, a perfect graceful labeling. And so I called out the contest because the

Donald Knuth (2:04:49.600)

problem's already solved and too easy in a sense because Tom was able to do it in an afternoon.

Donald Knuth (2:04:55.680)

Sorry, he gave the algorithm or for this particular...

Lex Fridman (2:04:59.200)

For the United States.

Donald Knuth (2:05:00.800)

For the United States.

Lex Fridman (2:05:01.600)

This problem is incredibly hard. I mean...

Donald Knuth (2:05:05.040)

For the general algorithm. But it was very lucky that it worked for the United States, I think.

Donald Knuth (2:05:13.360)

The theory is still very incomplete. But anyway, then Tom came back a couple of days later and he

Donald Knuth (2:05:19.520)

had been able to not only find a graceful labeling, but the label of Washington was 31,

Lex Fridman (2:05:26.800)

and the label of Idaho was 41, following the digits of pi. Going across the top edge of the

Donald Knuth (2:05:38.560)

United States, he has the digits of pi perfectly.

Lex Fridman (2:05:41.280)

Did he do it on purpose?

Donald Knuth (2:05:43.360)

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

Lex Fridman (2:05:48.000)

What? Wow.

Donald Knuth (2:05:50.720)

Wow.

Lex Fridman (2:05:51.520)

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

Donald Knuth (2:06:02.800)

All roads lead to pi. Somehow often hidden in the middle of the most difficult problems.

Lex Fridman (2:06:12.560)

Can I ask you about productivity?

Donald Knuth (2:06:16.720)

Productivity.

Donald Knuth (2:06:17.680)

Yeah, you said that, quote, my scheduling principle is to do the thing I hate most

Lex Fridman (2:06:25.200)

on my to do list. By week's end, I'm very happy. Can you explain this process to a productive life?

Lex Fridman (2:06:33.440)

Oh, I see. Well, but all the time I'm working on what I don't want to do,

Lex Fridman (2:06:39.200)

but still, I'm glad to have all those unpleasant tasks finished.

Lex Fridman (2:06:42.960)

Yes. Is that something you would advise to others?

Donald Knuth (2:06:46.000)

Well, yeah, I don't know how to say it. During the pandemic, I feel my productivity actually

Donald Knuth (2:06:54.880)

went down by half because I have to communicate by writing, which is slow. I don't like to send

Donald Knuth (2:07:07.600)

out a bad sentence. So I go through and reread what I've written and edit and fix it. So everything

Donald Knuth (2:07:14.320)

takes a lot longer when I'm communicating by text messages instead of just together with somebody

Donald Knuth (2:07:25.600)

in a room. And it's also slower because the libraries are closed and stuff.

Lex Fridman (2:07:31.840)

But there's another thing about scheduling that I learned from my mother that I should

Donald Knuth (2:07:35.680)

probably tell you, and that is it's different from what people in the robotics field do,

Lex Fridman (2:07:42.320)

which is called planning. So she had this principle that was,

Donald Knuth (2:07:49.360)

see something that needs to be done and do it.

Donald Knuth (2:07:54.960)

Instead of saying, I'm going to do this first and do this first, just pick this up.

Lex Fridman (2:08:03.920)

But at any one moment, there's a set of tasks that you can do. And you're saying a good heuristic

Lex Fridman (2:08:12.400)

is to do the one you want to do least.

Donald Knuth (2:08:15.680)

Right. The one I haven't got any good reason,

Donald Knuth (2:08:20.960)

that I'll never be able to do it any better than I am now. There are some things that I know,

Donald Knuth (2:08:29.440)

if I do something else first, then I'll be able to do that one better.

Lex Fridman (2:08:32.800)

Yeah.

Lex Fridman (2:08:33.200)

But there are some that are going to be harder because I've forgotten some of the

Donald Knuth (2:08:40.160)

groundwork that went into it or something like that. So I just finished a pretty tough part of

Donald Knuth (2:08:46.080)

the book. And so now I'm doing the parts that are more fun. But the other thing is, as I'm

Donald Knuth (2:08:56.560)

writing the book, of course, I want the reader to think that I'm happy all the time I'm writing

Donald Knuth (2:09:02.320)

the book. It's upbeat. I can have humor. I can say this is cool. And this, I have to disguise

Lex Fridman (2:09:14.000)

the fact that it was painful in any way to come up with these.

Donald Knuth (2:09:18.240)

The road to that excitement is painful. Yeah. It's laden with pain. Okay. You've given some

Lex Fridman (2:09:25.520)

advice to people before, but can you...

Donald Knuth (2:09:30.320)

You give me too much credit. But anyway, this is my turn to say things that I believe. But

Donald Knuth (2:09:39.840)

I want to preface it by saying I also believe that other people do these things much better

Donald Knuth (2:09:48.800)

than I do. So I can only tell you my side of it.

Donald Knuth (2:09:52.160)

Right. So can I ask you to give advice to young people today, to high school students,

Donald Knuth (2:10:01.120)

to college students, whether they're geeks or the other kind, about how to live a life

Lex Fridman (2:10:08.560)

that they can be proud of, how to have a successful career, how to have a successful life?

Donald Knuth (2:10:13.840)

It's always the same as I've said before, I guess, not to do something because it's

Donald Knuth (2:10:24.720)

trendy, but something that you personally feel that you were called to do rather than

Lex Fridman (2:10:32.800)

somebody else expects you to do. How do you know you're called to do something?

Donald Knuth (2:10:37.520)

If you try it and it works or it doesn't work. I mean, you learn about yourself. Life is

Donald Knuth (2:10:45.200)

a binary search. You try something and you find out, oh yeah, I have a background that

Donald Knuth (2:10:49.280)

helped me with this. Or maybe I could do this if I worked a little bit harder. But you try

Donald Knuth (2:10:57.920)

something else and you say, well, I have really no intuition for this and it looks like it

Donald Knuth (2:11:04.960)

doesn't have my name on it. Was there advice along the way that you got about what you

Donald Knuth (2:11:12.560)

should and shouldn't work on? Or do you just try to listen to yourself? Yeah, I probably

Donald Knuth (2:11:18.000)

overreact another way. When I see everybody else going some way, I probably say, hmm,

Donald Knuth (2:11:27.120)

not too much competition. But mostly I played with things that were interesting to me and

Donald Knuth (2:11:37.600)

then later on I found, oh, actually the most important thing I learned was how to be interested

Donald Knuth (2:11:43.520)

in almost anything. I mean, not to be bored. It makes me very sad when I see kids talking

Donald Knuth (2:11:51.920)

to each other and they say, that was boring. And to me, a person should feel upset if he

Donald Knuth (2:12:06.320)

had to admit that he wasn't able to find something interesting. It's a skill they

Donald Knuth (2:12:13.600)

think, I haven't learned how to enjoy life. I have to have somebody entertain me instead of...

Donald Knuth (2:12:20.400)

Right. That's really interesting. It is a skill. David Foster Wallace, I really like

Donald Knuth (2:12:27.520)

the thing he says about this, which is the key to life is to be unborable. And I do really like

Donald Knuth (2:12:34.480)

you saying that it's a skill because I think that's a really good advice, which is if you

Donald Knuth (2:12:40.640)

find something boring, that's not... I don't believe it's because it's boring. It's because

Donald Knuth (2:12:49.360)

you haven't developed a skill. I haven't learned how to...

Lex Fridman (2:12:51.840)

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

Donald Knuth (2:12:58.000)

Sometimes it's more difficult than others to do this. I mean, during the COVID,

Donald Knuth (2:13:06.000)

lots of days when I never saw another human being, but I still find other ways to...

Donald Knuth (2:13:14.640)

It still was a pretty fun time.

Donald Knuth (2:13:18.000)

Yeah. I came a few minutes early today and I walked around Foster City. I didn't know

Lex Fridman (2:13:28.160)

what was going on in Foster City. I saw some beautiful flowers at the nursery at Home Depot

Lex Fridman (2:13:33.360)

a few blocks away.

Donald Knuth (2:13:34.400)

Yeah. Life is amazing. It's full of amazing things like this. Yeah. Sometimes I'll sit

Donald Knuth (2:13:42.800)

there and just stare at a tree. Nature is beautiful. Let me ask you the big ridiculous

Donald Knuth (2:13:48.880)

question. I don't think I asked you last time. So I have to ask this time in case you have

Donald Knuth (2:13:52.400)

a good answer. What is the meaning of life? Our existence here on earth, the whole thing.

Donald Knuth (2:14:06.080)

No, no, you can't. I will not allow you to try to escape answering this question.

Donald Knuth (2:14:11.600)

You have to answer definitively because surely, surely, Don Knuth, there must be an answer.

Lex Fridman (2:14:19.840)

What is the answer? Is it 42?

Lex Fridman (2:14:22.480)

Yes. Well, I don't think it's a numerical. That's the SDS.

Donald Knuth (2:14:26.000)

That was in Zen and... All right. So anyway, it's only for me, but I personally

Donald Knuth (2:14:37.040)

think of my belief that God exists, although I have no idea what that means. But I believe

Donald Knuth (2:14:48.800)

that there is something beyond human capabilities. It might be some AI, but whatever it is. But

Donald Knuth (2:15:06.080)

whatever. But I do believe that there is something that goes beyond the realm of human understanding,

Lex Fridman (2:15:17.680)

but that I can try to learn more about how to resonate with whatever that being would

Lex Fridman (2:15:29.600)

like me to do. So you think you can have occasional glimpses

Donald Knuth (2:15:34.640)

of that being? I strive for that. Not that I ever think

Donald Knuth (2:15:42.000)

I'm going to get close to it, but it's not for me. It's saying, what should I do that

Donald Knuth (2:15:49.040)

that being wants me to do? I'm trying to ask, does that being want me to be talking to Lex

Lex Fridman (2:16:03.200)

Friedman right now? And I said, yes. Okay. Thank you.

Donald Knuth (2:16:09.600)

Well, thank you. What I'm trying to say is, of all the strategies I could choose or something,

Donald Knuth (2:16:22.640)

I try to do it not strategically, but I try to imagine that I'm following somebody's wishes.

Donald Knuth (2:16:33.040)

Even though you're not smart enough to know what they are.

Lex Fridman (2:16:37.200)

Yeah. It's that funny little dance. Well, I mean, this AI or whatever,

Donald Knuth (2:16:43.760)

probably is smart enough to help to give me clues.

Lex Fridman (2:16:51.120)

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

Donald Knuth (2:16:56.080)

Yeah. As so many people have said, it's the journey, not the destination.

Lex Fridman (2:17:00.800)

And people live through crises, help each other. Things come up, history repeats itself.

Donald Knuth (2:17:12.640)

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

Lex Fridman (2:17:20.480)

that things were... They were a lot worse in many ways.

Donald Knuth (2:17:28.320)

There's a lot of bad things all the time. And I read about... I look at things and people had

Donald Knuth (2:17:36.080)

good ideas and they were working on great projects. And then I know that it didn't succeed, though,

Donald Knuth (2:17:42.000)

in the end. But the new insight I've gotten actually in that way was... I was reading...

Lex Fridman (2:17:50.160)

What book was I reading recently? It was by Ken Follett and it was called The Man from

Donald Knuth (2:17:56.320)

St. Petersburg. But it was talking about the prequel to World War I. And Winston Churchill,

Donald Knuth (2:18:05.040)

according to this book, sees that Germany has been spending all its gold reserves

Donald Knuth (2:18:11.680)

building up a huge military. And there's no question that if Germany would attack England,

Donald Knuth (2:18:18.240)

that England would be wiped out. So he wants Russia to help to attack Germany from the other side,

Donald Knuth (2:18:27.040)

because Germany doesn't have enough of an army to be fighting two wars at one.

Donald Knuth (2:18:33.040)

Okay. Now, then there's an anarchist in Russia who sees that wars are something that leaders

Donald Knuth (2:18:45.520)

start, but actually people get killed. And so he wants to stop any alliance between England and

Donald Knuth (2:18:56.160)

Russia, because that would mean that thousands and thousands of people of Russia would be killed

Donald Knuth (2:19:03.600)

that wouldn't be otherwise killed. All right. And so his life's goal is to assassinate a Russian

Donald Knuth (2:19:13.360)

prince who's visiting England, because that will mean the Tsar will not form the alliance. All

Donald Knuth (2:19:20.000)

right. So we have this question about what should the government do? Should it actually do something

Donald Knuth (2:19:29.440)

that will lead to... Is the war inevitable or is there a way to have peace? And it struck me that

Donald Knuth (2:19:37.920)

if I were in a position of responsibility for people's lives, in most cases, I wouldn't have

Donald Knuth (2:19:46.400)

any confidence that any of my decisions were good. That these questions are too hard, probably for

Donald Knuth (2:19:54.800)

any human being, but certainly for me. Well, I think coupling the not being sure that the

Donald Knuth (2:20:04.400)

decisions are right. So that's actually a really good thing, coupled with the fact that you do have

Donald Knuth (2:20:11.120)

to make a decision and carry the burden of that. And ultimately I have faith in human beings and

Donald Knuth (2:20:20.640)

the great leaders to arise and help build a better world. I mean, that's the hope of democracy.

Donald Knuth (2:20:27.920)

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

Donald Knuth (2:20:40.080)

Well put, Don. It's such a huge honor. You've been an inspiration to me and to millions for

Donald Knuth (2:20:46.160)

such a long time. Thank you for spending your really valuable time with me. Once again,

Lex Fridman (2:20:52.560)

it's a huge honor. I really enjoyed this conversation.

Donald Knuth (2:20:54.800)

Thanks for listening to this conversation with Donald Knuth. To support this podcast,

Donald Knuth (2:21:00.080)

please check out our sponsors in the description. And now let me leave you with some words from

Donald Knuth (2:21:05.200)

Don Knuth himself. Science is what we understand well enough to explain to a computer. Art is

Lex Fridman (2:21:12.880)

everything else we do. Thank you for listening and hope to see you next time.

Donald Knuth (30:02.000)

early guinea pigs who were telling them whether they should publish or not.

Lex Fridman (30:06.320)

You know, and one of the things was in the comments to volume one,

Donald Knuth (30:17.760)

the major reader was Bob Floyd, who is my great co worker in the 60s, died early,

Donald Knuth (30:27.920)

unfortunately. And he commented about the humor in it. So he ran it by me, you know,

Donald Knuth (30:38.960)

says, you know, keep this joke in or not, you know. They also sent it out to focus group.

Lex Fridman (30:46.480)

What do you think about humor in a book about computer programming?

Lex Fridman (30:50.240)

What's the conclusion?

Lex Fridman (30:51.520)

And I stated my philosophy. It said, you know, the ideal thing is that it's something where

Donald Knuth (31:00.320)

the reader knows that there's probably a joke here if you only understood it. And this is a

Donald Knuth (31:04.800)

motivation to understand, to think about it a little bit. But anyway, it's a very delicate

Donald Knuth (31:13.280)

humor. I mean, it's really each each century invents a different kind of humor, too. Different

Donald Knuth (31:21.600)

cultures have different different kinds of humor. Yeah. Like we talked about Russia a little bit

Donald Knuth (31:27.600)

offline. You know, there's dark humor and, you know, when a country goes through something

Donald Knuth (31:34.960)

difficult, that life and stuff like this. And, you know, and Jack Benny, I mean,

Donald Knuth (31:39.680)

you know, Steve Allen wrote this book about humor, and it was the most boring book,

Lex Fridman (31:46.000)

but he was one of my idols. But it's called The Funny Men or something like that. But yeah. Okay.

Lex Fridman (31:54.080)

So anyway, I think it's important to know that this is part of life, and it should be fun and

Donald Knuth (32:00.800)

not... And so, you know, I wrote this organ composition, which is based on the Bible,

Lex Fridman (32:08.560)

but I didn't refrain from putting little jokes in it also in the music.

Lex Fridman (32:14.320)

It's hidden in the music.

Donald Knuth (32:15.680)

It's there, yeah.

Lex Fridman (32:18.160)

A little humor is okay?

Donald Knuth (32:19.520)

Yeah. I mean, not egregious humor. So in this correspondence, you know, there were

Donald Knuth (32:27.280)

things I said, yeah, I really shouldn't have done that. But other ones I insisted on. And I've got

Donald Knuth (32:35.840)

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

Donald Knuth (32:44.800)

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

Donald Knuth (32:52.560)

which is larger than people know how to break. And so, you know, if computers keep getting faster

Lex Fridman (32:59.680)

and faster, then, you know, it might be a hundred years, but somebody will figure out what this

Lex Fridman (33:04.080)

what this message is and they will laugh. I mean, I've got a joke in there.

Lex Fridman (33:09.520)

So that one you really have to work for. I don't know if you've heard about this.

Donald Knuth (33:15.840)

Let me explain it. Maybe you'll find it interesting. So OpenAI is a company that

Donald Knuth (33:22.400)

does AI work, and they have this language model. It's a neural network that can generate

Donald Knuth (33:28.480)

language pretty well. But they also have, on top of that, developed something called OpenAI Codex.

Lex Fridman (33:38.640)

And together with GitHub, they developed a system called OpenAI Copilot.

Donald Knuth (33:43.680)

Let me explain what it does. There's echoes of literate programming in it. So what you do

Donald Knuth (33:50.720)

is you start writing code and it completes the code for you. So, for example, you start,

Donald Knuth (33:57.600)

let's go to your factoring program. You start, you write in JavaScript and Python and any language

Donald Knuth (34:04.480)

that it trained on. You start, you write the first line and some comments, like what this

Donald Knuth (34:11.200)

code does, and it generates the function for you. And it does an incredibly good job.

Donald Knuth (34:17.040)

Like, it's not provably right, but it often does a really good job of completing the code for you.

Lex Fridman (34:23.280)

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

Lex Fridman (34:26.880)

Yeah.

Donald Knuth (34:27.440)

You could see a lot of examples where it did a good job.

Lex Fridman (34:31.040)

And so it's not a thing that generates code for you.

Donald Knuth (34:34.400)

Yeah, exactly.

Lex Fridman (34:35.360)

It starts, it gives you, so it puts the human in the seat of fixing

Lex Fridman (34:42.720)

issues versus writing from scratch. Do you find that kind of idea at all interesting?

Donald Knuth (34:48.560)

Every year, we're going to be losing more and more control over what machines are doing.

Lex Fridman (34:53.360)

And people are saying, well, when I was a professor at Caltech in the 60s, we had this

Donald Knuth (35:03.760)

guy who talked a good game. He could give inspiring lectures and you'd think, well,

Lex Fridman (35:13.440)

thrilling things he was talking about. An hour later, you'd say, well, what did he say?

Donald Knuth (35:16.880)

Yeah. But he really felt that it didn't matter whether computers got the right answer or not,

Donald Knuth (35:23.520)

it just mattered whether it made you happy or not. In other words, if your boss paid for it,

Lex Fridman (35:30.800)

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

Donald Knuth (35:35.360)

Happiness is more important than truth.

Lex Fridman (35:38.000)

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

Donald Knuth (35:40.800)

Yes, I like it. And somehow you see...

Donald Knuth (35:47.040)

We're going that way. So many more things are taken over by saying, well, this seems to work.

Donald Knuth (35:55.440)

When there is a competing interest involved, neither side understands

Lex Fridman (36:00.880)

why the decision is being made. We realize now that it's bad, but consider what happens

Donald Knuth (36:09.360)

5 or 10 years down the line when things get even more further detached. Each thing is based on

Lex Fridman (36:17.920)

something from the previous year.

Donald Knuth (36:20.080)

Yeah. So you start to lose... The more you automate,

Lex Fridman (36:23.600)

the more you start to lose track of some deep human things.

Donald Knuth (36:26.800)

Exponentially.

Donald Knuth (36:28.160)

Exponentially. So that's the dark side. The positive side is the more you automate,

Donald Knuth (36:36.080)

the more you let humans do what humans do best. So maybe programming...

Donald Knuth (36:43.280)

Maybe humans should focus on a small part of programming that requires that genius,

Donald Knuth (36:48.640)

the magic of the human mind, and the mess you let the machine generate.

Donald Knuth (36:55.600)

That's the positive, but of course, it does come with the darkness of automation.

Lex Fridman (37:01.760)

What's better? Correctness?

Lex Fridman (37:02.800)

I'm never going to try to write a book about that.

Donald Knuth (37:06.480)

I'm never going to recommend to any of my students to work for them.

Lex Fridman (37:10.160)

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

Donald Knuth (37:14.160)

I'm on the side of understanding.

Lex Fridman (37:17.200)

Understanding.

Lex Fridman (37:18.240)

And I think these things are really marvelous if what they do is all of a sudden we have a better

Donald Knuth (37:25.840)

medical diagnosis or it'll help guide some scientific experiment or something like curing

Donald Knuth (37:34.560)

diseases or whatever. But when it affects people's lives in a serious way... If you're writing code,

Lex Fridman (37:46.080)

oh yeah, this is great. This will make a slaughter bot.

Donald Knuth (37:50.160)

I see. So you have to be very careful. Right now it seems like fun and games.

Donald Knuth (37:59.600)

It's useful to write a little JavaScript program that helps you with the website.

Lex Fridman (38:04.800)

But like you said, one year passes, two years passes, five years, and you forget.

Donald Knuth (38:10.000)

You start building on top of it, and then all of a sudden you have autonomous weapon systems.

Donald Knuth (38:14.560)

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

Lex Fridman (38:21.360)

Well, in the end, this whole thing ends anyway.

Donald Knuth (38:28.880)

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

Donald Knuth (38:38.160)

Well, it'd be nice that at the end, as we approach the heat death of the universe,

Donald Knuth (38:42.960)

there's still some kind of consciousness there to appreciate it. Hopefully human consciousness.

Donald Knuth (38:51.760)

I'll settle for 10 to the 10th year, some finite number. But things like this might be the reason

Donald Knuth (38:59.120)

we don't pick up any signals from extraterrestrials. They don't want anything to do with us.

Lex Fridman (39:06.160)

Oh, because they, because they, they, they invented it too.

Lex Fridman (39:14.480)

So you, you do have a little bit of worry on the existential threats of AI and automation.

Lex Fridman (39:23.120)

So like, like removing the human from the picture, et cetera. Yeah.

Donald Knuth (39:26.960)

Um, people have more, more potential to do harm now than by far than they did a hundred years ago.

Lex Fridman (39:36.160)

But are you optimistic about the humans are good at creating destructive things,

Lex Fridman (39:42.080)

but also humans are good at solving problems. Yeah. I mean, there's half empty and half full,

Lex Fridman (39:46.240)

you know, so I can go. So let me, let me put it this way because,

Donald Knuth (39:54.160)

because it's the only way I can be optimistic, but, but, but, but think of, um, of, uh,

Donald Knuth (40:05.280)

things that have changed because of civilization, you know, they don't occur just in nature.

Lex Fridman (40:11.840)

So just, uh, just imagine the room we're in, for example. Okay. Some, you know, we've got pencils,

Lex Fridman (40:19.920)

we've got books, we've got tables, we've got microphones, your clothing, food,

Donald Knuth (40:25.440)

all these things were added. Somebody invented them one by one and millions of things, uh,

Donald Knuth (40:34.080)

that we inherit. Okay. Um, and, uh, it's inconceivable that, that so many millions

Donald Knuth (40:40.320)

of billions of things, uh, wouldn't have problems and we get it all right. Um, and each one

Donald Knuth (40:48.960)

would have no negative effects and so on. So it, it's very amazing that as much works as does work.

Donald Knuth (40:58.880)

It's, it's, it's incredibly amazing. And actually that's the source of my optimism as well,

Donald Knuth (41:06.880)

including for artificial intelligence. So we, we drive over bridges. We, uh, we use all kinds

Donald Knuth (41:15.280)

of technology. We don't know how it works. And there's millions of brilliant people involved in

Donald Knuth (41:20.080)

building a small part of that and it doesn't go wrong and it works. And I mean that it, it works

Lex Fridman (41:27.040)

and it doesn't go, go wrong often enough for us to suffer. And we can identify things that

Donald Knuth (41:34.320)

aren't working and try to improve on them. In a suboptimal, often suboptimal way. Oh, absolutely.

Lex Fridman (41:42.240)

But it's, but the, but the, the kind of things that I know how to improve require human beings

Donald Knuth (41:50.800)

to be rational. And I, I'm losing my confidence that human beings are rational. Yeah. Yeah. Now

Donald Knuth (41:57.600)

here you go again with the worst case, uh, worst case analysis. Um, they may not be rational, but

Donald Knuth (42:04.160)

they're, um, they're, they're clever and, uh, beautiful in their own kind of way. I tend to

Donald Knuth (42:12.560)

think that most people, um, have the desire and the capacity to be good to each other and love

Donald Knuth (42:20.720)

will ultimately win out. Like if they're given the opportunity, that's where they lean. In the Art

Donald Knuth (42:27.440)

of Computer Programming, you wrote, the real problem is that programmers have spent far too

Donald Knuth (42:32.560)

much time worrying about efficiency in the wrong places. And at the wrong times, premature

Donald Knuth (42:38.400)

optimization is the root of all evil in parentheses, or at least most of it in programming. Can you,

Donald Knuth (42:46.880)

uh, explain this idea? Uh, what's the wrong time? What is the wrong place for optimization? So

Lex Fridman (42:54.880)

so first of all, the word optimization, I started out writing software, uh, and optimization was,

Donald Knuth (43:04.000)

I was a compiler writer. So optimization meant, uh, making the, uh, making a better translation

Lex Fridman (43:12.400)

so that it would run faster on a, on a machine. So an optimized program is just like, you know,

Donald Knuth (43:17.840)

you, you, you run a program and you set the optimization level, uh, for, uh, to the compiler.

Lex Fridman (43:24.320)

So that's one word for optimization. Um, and at that time I, I happened to be looking in an

Donald Knuth (43:31.120)

unabridged dictionary, uh, for some reason or other, and I came to the word optimizer.

Lex Fridman (43:37.360)

So what's the meaning of the word optimize? And it says to view with optimism.

Lex Fridman (43:44.800)

And you look in Webster's dictionary of English language in 19, early 1960s,

Donald Knuth (43:50.320)

that's what optimize meant. Okay. Um, now, so people started doing cost optimization,

Donald Knuth (43:58.560)

other kinds of things, uh, uh, you know, whole sub fields of, of, uh, algorithms and economics

Lex Fridman (44:06.640)

and whatever are based on what they call optimization now. But, uh, but to me optimization

Donald Knuth (44:13.600)

when I was saying that was saying, uh, changing a program to make it more, uh, tuned to the machine.

Lex Fridman (44:21.680)

And I found out that, uh, when a person writes a program, uh, he or she tends to think that

Donald Knuth (44:33.120)

the parts that were hardest to write are going to be hardest for the computer to execute.

Lex Fridman (44:37.200)

So maybe I have 10 pages of code, but I had to work a week writing this page. I mentally think

Donald Knuth (44:47.440)

that when the computer gets to that page, it's going to slow down. It's going to say, oh, I

Donald Knuth (44:53.360)

don't understand what I'm doing. I better, I better be more careful. Anyway, this is of course silly,

Lex Fridman (44:58.880)

but it's, it's, it's something that we, that we, that we don't know when we write a piece of code.

Donald Knuth (45:04.080)

We don't know what, what, whether the computer is actually going to be executing that code

Donald Knuth (45:09.200)

very much. So, so people had, had a very poor understanding of, of what the computer was

Donald Knuth (45:17.280)

actually doing. Uh, I made one test where, where we studied a Fortran compiler and it was spending

Donald Knuth (45:25.440)

more than 80% of its time reading the comments card. Um, but as a programmer, we were really

Donald Knuth (45:32.240)

concerned about how fast it could take a complicated expression that had lots of

Donald Knuth (45:36.400)

levels of parentheses and, and, and, and convert that into something. But that was just, you know,

Donald Knuth (45:43.760)

less than 1% of the, so if we optimize that, uh, we didn't know what we were doing, but, but,

Lex Fridman (45:52.080)

but if we knew that it was spending 80% of his time on the comments card, you know, in 10 minutes,

Donald Knuth (45:57.200)

we could, we could make the, the, the compiler run more than twice as fast.

Lex Fridman (46:01.040)

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

Donald Knuth (46:05.840)

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

Lex Fridman (46:10.080)

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

Donald Knuth (46:15.200)

across all of them. I'm glad that it applied generally, but it was,

Donald Knuth (46:18.080)

it was only my good luck. I said it, but you know, but I did, but I said it in a limited context

Lex Fridman (46:24.400)

and I, and, and I'm glad if it makes people think about stuff because I, but it applies

Donald Knuth (46:32.800)

in another sense too, that is sometimes I will do optimization in a way that does help

Donald Knuth (46:43.440)

the actual running time, but makes the program impossible to change next week.

Donald Knuth (46:49.520)

Right. Because I've changed my data structure or something that, that made it less adaptable.

Lex Fridman (46:56.080)

So one of the great principles of computer science is, is, is laziness or whatever you call it,

Donald Knuth (47:04.800)

late binding. You know, don't hold off decisions when you can. And, and, and, you know, and we

Donald Knuth (47:14.000)

understand now quantitatively how valuable that is.

Lex Fridman (47:18.560)

What do you mean we understand? So you mean from a...

Donald Knuth (47:22.160)

People, people have written thesis about how you can, how late binding will, will improve the,

Donald Knuth (47:29.440)

I mean, you know, just in time manufacturing or whatever, you can make, you can defer a decision

Donald Knuth (47:36.320)

instead of doing your advanced planning and say, I'm going to allocate 30% to this and 50%.

Lex Fridman (47:41.440)

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

Donald Knuth (47:45.920)

Decision is not made in advance. So instead you, you, you design in order to be flexible to change

Donald Knuth (47:53.600)

with the, with the way the wind is blowing. Yeah. But so the reason that line resonated

Donald Knuth (48:00.160)

with a lot of people is because there's something about the programmer's mind

Donald Knuth (48:06.560)

that wants, that enjoys optimization. So it's a constant struggle to balance laziness and late

Donald Knuth (48:15.600)

binding with the desire to optimize. The elegance of a well optimized code

Donald Knuth (48:23.840)

is something that's compelling to programming. Yeah. It's another concept of beauty.

Donald Knuth (48:31.520)

Let me ask you a weird question. So Roger Penrose has talked about computation computers

Lex Fridman (48:39.600)

and he proposed that the way the human mind discovers mathematical ideas is something more

Donald Knuth (48:49.360)

than a computer. That, that a universal Turing machine cannot do everything that a human mind

Donald Knuth (48:57.200)

can do. Now this includes discovering mathematical ideas and it also includes, he's written a book

Donald Knuth (49:05.120)

about it, Consciousness. So I don't know if you know Roger, but my, my daughter's kids played

Donald Knuth (49:12.240)

with his kids in Oxford. Nice. So do you think there is such a limit to the computer? Do you

Donald Knuth (49:19.840)

think consciousness is more than a computation? Do you think the human mind, the way it thinks

Donald Knuth (49:26.080)

is more than a computation? I mean, I can say yes or no, but, but, but I don't, I have no reason. I

Donald Knuth (49:35.360)

mean. So you don't find it useful to have an intuition in one way or the other? Like when

Donald Knuth (49:40.480)

you think about algorithms, isn't it useful to think about the limits? Unanswerable question in

Donald Knuth (49:46.400)

my opinion is, is no better than anybody else. You think it's unanswerable. So you don't think

Donald Knuth (49:51.520)

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

Donald Knuth (49:58.400)

Anyway, there, there are lots of things that are beyond, that we can speculate about, but

Donald Knuth (50:03.600)

I don't want somebody to say, oh yeah, Knuth said this and so he's, he's, he's smart. And so,

Lex Fridman (50:08.640)

so he, so that must be, I mean, I say it's something that we'll never know.

Donald Knuth (50:14.560)

Oh, interesting. Okay. That's a strong statement. I don't, I personally think it's something we

Donald Knuth (50:22.000)

will know eventually. Like there's no reason to me why the, the workings of the human mind

Donald Knuth (50:28.880)

are not within the reach of science. That's absolutely possible. And I'm not denying it.

Donald Knuth (50:34.080)

Yeah. But right now you don't have a good intuition. I mean, that's also possible,

Donald Knuth (50:38.640)

you know, that an AI, you know, created the universe, you know, intelligent design has all

Donald Knuth (50:45.280)

been done by an AI. This is, I mean, all of these things are, but, but, but you're asking me to,

Donald Knuth (50:52.640)

to pronounce on it. And I don't have any expertise. I'm a teacher that passes on knowledge,

Lex Fridman (50:58.960)

but I don't, but I don't know the fact that I, that I vote yes or no on.

Donald Knuth (51:05.440)

Well, you do have expertise as a human, not as a, not as a teacher or a scholar of computer science.

Donald Knuth (51:14.480)

I mean, that's ultimately the realm of where the discussion of human thought.

Lex Fridman (51:18.640)

Yeah. Well, I know where.

Lex Fridman (51:19.760)

And consciousness is.

Lex Fridman (51:21.040)

I know where, where Penrose is coming from. He, I'm sure he has no,

Donald Knuth (51:26.160)

I mean, he might even thought he proved it, but.

Lex Fridman (51:28.880)

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

Donald Knuth (51:32.320)

But, but I mean, you have to ask John McCarthy. John McCarthy,

Lex Fridman (51:38.240)

I think, were totally unimpressed by these statements.

Lex Fridman (51:43.600)

So you don't think, so even like the Turing paper on, on the Turing test that,

Lex Fridman (51:51.120)

you know, starts by asking, can machines think?

Donald Knuth (51:53.760)

Oh.

Lex Fridman (51:54.960)

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

Donald Knuth (51:59.520)

Yeah. I don't consider it important, let's just put it that way.

Lex Fridman (52:04.560)

Because it's, it's in the category of things that it would be nice to know,

Lex Fridman (52:10.080)

but I think it's beyond knowledge. And so I don't, I'm more interested in knowing

Lex Fridman (52:16.800)

about the Riemann hypothesis or something.

Lex Fridman (52:20.320)

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

Lex Fridman (52:24.320)

Yeah.

Donald Knuth (52:24.720)

I think what you mean is it's not sufficiently well, it's not even known well enough to be

Lex Fridman (52:31.200)

able to formalize it in order to ask a clear question.

Donald Knuth (52:35.920)

Yeah.

Lex Fridman (52:36.320)

And so that's why it's beyond knowledge, but that doesn't mean it's not

Donald Knuth (52:40.000)

eventually going to be formalized.

Lex Fridman (52:41.680)

Yeah. Yeah. Maybe consciousness will be understood some, someday.

Donald Knuth (52:46.080)

The last time I checked, it was still 200 years away.

Donald Knuth (52:51.120)

I mean, I haven't been specializing in this by any means, but I went to lectures about it 20

Donald Knuth (52:57.360)

years ago when I was, there was a symposium at the American Academy in Cambridge. And it started out

Donald Knuth (53:05.280)

by saying, essentially, everything that's been written about consciousness is hogwash.

Donald Knuth (53:12.960)

I tend to disagree with that a little bit.

Lex Fridman (53:18.240)

So consciousness for the longest time still is in the realm of philosophy.

Lex Fridman (53:24.640)

So it's just conversations without any basis and understanding.

Donald Knuth (53:28.960)

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

Lex Fridman (53:38.320)

and they have personality, they have identity, you start flirting with the question of

Donald Knuth (53:45.040)

consciousness, not from a philosophical perspective, but from an engineering perspective.

Lex Fridman (53:50.320)

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

Lex Fridman (53:53.920)

Yeah. Don't misunderstand me. I certainly don't disagree with that at all.

Lex Fridman (54:00.800)

And even at these lectures that we had 20 years ago, there were neurologists pointing out that

Donald Knuth (54:08.880)

human beings had actually decided to do something before they were conscious of making that

Donald Knuth (54:14.640)

decision. I mean, they could tell that signals were being sent to their arms before they knew

Donald Knuth (54:24.320)

that things like this are true. And Les Valiant has an architecture for the brain. And more recently,

Donald Knuth (54:34.480)

Christos Papadimitriou in the Academy of Science Proceedings a year ago with two other people,

Lex Fridman (54:44.640)

but I know Christos very well. And he's got this model of this architecture by which

Donald Knuth (54:54.720)

you could create things that correlate well with experiments that are done on consciousness.

Lex Fridman (55:02.720)

And he actually has a machine language in which you can write code and test hypotheses.

Lex Fridman (55:17.520)

And so we might have a big breakthrough. My personal feeling is that consciousness is the

Donald Knuth (55:24.960)

best model I've heard of to explain the miracle of consciousness is that somehow inside of our

Donald Knuth (55:39.440)

brains, we're having a continual survival for the fittest competition. And I'm speaking to you,

Lex Fridman (55:49.440)

and I'm speaking to you, all the possible things I might be wanting to say are all in there and

Donald Knuth (55:56.240)

there's like a voting going on. Yeah, right. And one of them is winning and that's affecting

Lex Fridman (56:04.880)

the next sentence and so on. And there was this book, Machine Intelligence or something?

Lex Fridman (56:11.840)

On Intelligence?

Lex Fridman (56:12.640)

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

Donald Knuth (56:21.280)

Well, I like whether it's consciousness or something else, I like the storytelling part

Donald Knuth (56:27.360)

that it feels like for us humans, it feels like there's a concrete story. It's almost

Donald Knuth (56:34.960)

like literary programming. I don't know what the programming is going on on the inside,

Lex Fridman (56:38.640)

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

Donald Knuth (56:44.080)

I'm getting a nice clear story. But it's also possible there's a computation going on that's

Donald Knuth (56:49.920)

really messy. There's a bunch of different competing ideas. And in the end, it just kind

Donald Knuth (56:54.560)

of generates a story for you, a consistent story for you to believe. And that makes it all nice.

Donald Knuth (57:01.680)

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

Donald Knuth (57:08.400)

which I'm only on the sideline.

Lex Fridman (57:14.480)

So there's a tricky thing. I don't know if you have any expertise in this.

Donald Knuth (57:18.560)

You might be a little bit on the sideline. It'd be interesting to ask though.

Lex Fridman (57:21.840)

What are your thoughts on Cellular Automata and the Game of Life?

Lex Fridman (57:25.680)

Have you ever played with those kind of little games?

Donald Knuth (57:28.800)

I think the Game of Life is wonderful and shows all kinds of stuff about how things can evolve

Donald Knuth (57:43.200)

without the creator understanding anything more than the power of learning in a way. But to me,

Donald Knuth (57:51.520)

the most important thing about the Game of Life is how it focused for me what it meant to have

Donald Knuth (58:01.840)

free will or not. Because the Game of Life is obviously totally deterministic. And I find it

Donald Knuth (58:11.600)

hard to believe that anybody who's ever had children cannot believe in free will. On the

Donald Knuth (58:17.360)

other hand, this makes it crystal clear. John Conway said he wondered whether it was immoral

Donald Knuth (58:30.160)

to shut the computer off after he got into a particularly interesting play of the Game of Life.

Donald Knuth (58:36.640)

Wow. Yeah. So to me, the reason I love the Game of Life is exactly as you said,

Lex Fridman (58:43.200)

a clear illustration that from simple initial conditions with simple rules,

Donald Knuth (58:49.040)

you know exactly how the system is operating, it's deterministic. And yet, if you allow yourself to

Donald Knuth (58:58.640)

lose that knowledge a little bit enough to see the bigger organisms that emerge,

Lex Fridman (59:06.240)

and then all of a sudden they seem conscious. They seem, not conscious, but living.

Donald Knuth (59:10.720)

If the universe is finite, we're all living in the Game of Life, just slowed down. I mean,

Donald Knuth (59:18.240)

it sped up a lot.

Lex Fridman (59:21.040)

But do you think technically some of the ideas that you used for analysis of algorithms can be

Lex Fridman (59:28.160)

used to analyze the Game of Life? Can we make sense of it? Or is it too weird?

Donald Knuth (59:32.960)

Yeah. I mean, I've got a dozen exercises in volume four, fascicle six, that actually work

Donald Knuth (59:43.360)

rather well for that purpose. Bill Gospers came up with the algorithm that allows Golly to run

Lex Fridman (59:57.120)

thousands and thousands of times faster. You know the website called Golly? G O L L Y?

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

唐纳德·克努斯谈编程、算法与生命游戏