Donald Knuth: Algorithms, TeX, Life, and The Art of Computer Programming

Lex Fridman (01:33.520)

The effort was worth it.

Donald Knuth (01:35.720)

I've been doing this podcast on the side

Lex Fridman (01:37.480)

for just over a year.

Donald Knuth (01:38.720)

Sometimes I had to sacrifice a bit of sleep,

Lex Fridman (01:41.280)

but always happy to do it and to be

Donald Knuth (01:43.160)

part of an amazing community of curious minds.

Lex Fridman (01:46.640)

Thank you for your kind words of support

Lex Fridman (01:48.960)

and for the interesting discussions,

Lex Fridman (01:50.600)

and I look forward to many more of those in 2020.

Donald Knuth (01:54.400)

This is the Artificial Intelligence Podcast.

Lex Fridman (01:57.440)

If you enjoy it, subscribe on YouTube,

Donald Knuth (01:59.800)

give it five stars on Apple Podcast, follow on Spotify,

Lex Fridman (02:03.160)

support on Patreon, or simply connect with me on Twitter

Donald Knuth (02:06.520)

at Lex Friedman, spelled F R I D M A N.

Lex Fridman (02:10.640)

I recently started doing ads at the end of the introduction.

Donald Knuth (02:13.600)

I'll do one or two minutes after introducing the episode

Lex Fridman (02:16.320)

and never any ads in the middle that break

Donald Knuth (02:18.320)

the flow of the conversation.

Lex Fridman (02:19.960)

I hope that works for you

Lex Fridman (02:21.360)

and doesn't hurt the listening experience.

Lex Fridman (02:23.720)

I provide timestamps for the start of the conversation

Donald Knuth (02:26.000)

that you can skip to, but it helps

Lex Fridman (02:28.080)

if you listen to the ad and support this podcast

Donald Knuth (02:31.000)

by trying out the product or service being advertised.

Lex Fridman (02:34.240)

This show is presented by Cash App,

Donald Knuth (02:36.560)

the number one finance app in the App Store.

Lex Fridman (02:39.120)

I personally use Cash App to send money to friends,

Lex Fridman (02:41.840)

but you can also use it to buy, sell,

Lex Fridman (02:44.200)

and deposit Bitcoin in just seconds.

Donald Knuth (02:46.600)

Cash App also has a new investing feature.

Lex Fridman (02:49.760)

You can buy fractions of a stock, say $1 worth,

Donald Knuth (02:52.720)

no matter what the stock price is.

Lex Fridman (02:54.960)

Broker services are provided by Cash App Investing,

Donald Knuth (02:57.800)

a subsidiary of Square and member SIPC.

Lex Fridman (03:01.520)

I'm excited to be working with Cash App

Donald Knuth (03:03.480)

to support one of my favorite organizations called First,

Lex Fridman (03:06.880)

best known for their first robotics and Lego competitions.

Donald Knuth (03:10.480)

They educate and inspire hundreds of thousands of students

Lex Fridman (03:14.200)

in over 110 countries and have a perfect rating

Donald Knuth (03:17.120)

on Charity Navigator, which means that donated money

Lex Fridman (03:19.840)

is used to maximum effectiveness.

Donald Knuth (03:23.240)

When you get Cash App from the App Store or Google Play

Lex Fridman (03:26.480)

and use code LexPodcast, you'll get $10

Lex Fridman (03:30.120)

and Cash App will also donate $10 to First,

Lex Fridman (03:32.920)

which again is an organization

Donald Knuth (03:34.800)

that I've personally seen inspire girls and boys

Lex Fridman (03:37.640)

to dream of engineering a better world.

Lex Fridman (03:40.600)

And now here's my conversation with Donald Knuth.

Lex Fridman (03:44.320)

In 1957 at Case Tech, you were once allowed

Donald Knuth (03:50.520)

to spend several evenings with a IBM 650 computer

Lex Fridman (03:55.640)

as you've talked about in the past

Lex Fridman (03:57.080)

and you fell in love with computing then.

Lex Fridman (04:00.480)

Can you take me back to that moment with the IBM 650?

Lex Fridman (04:06.040)

What was it that grabbed you about that computer?

Lex Fridman (04:09.160)

So the IBM 650 was this machine

Donald Knuth (04:14.080)

that, well, it didn't fill a room,

Lex Fridman (04:16.800)

but it was big and noisy.

Lex Fridman (04:20.400)

But when I first saw it, it was through a window

Lex Fridman (04:23.120)

and there were just a lot of lights flashing on it.

Lex Fridman (04:26.160)

And I was a freshman, I had a job with the statistics group

Lex Fridman (04:34.600)

and I was supposed to punch cards for data

Lex Fridman (04:38.800)

and then sort them on another machine,

Lex Fridman (04:40.440)

but then they got this new computer, came in

Lex Fridman (04:43.920)

and it had interesting lights, okay.

Lex Fridman (04:48.360)

So, well, but I had a key to the building

Lex Fridman (04:51.520)

so I could get in and look at it and got a manual for it.

Lex Fridman (04:55.840)

And my first experience was based on the fact

Donald Knuth (04:58.600)

that I could punch cards, basically,

Lex Fridman (05:00.400)

which is a big thing for the,

Lex Fridman (05:02.440)

but the IBM 650 was big in size,

Lex Fridman (05:06.480)

but incredibly small in power.

Donald Knuth (05:10.880)

In resources.

Lex Fridman (05:11.840)

In memory, it had 2,000 words of memory

Lex Fridman (05:16.920)

and a word of memory was 10 decimal digits plus a sign.

Lex Fridman (05:20.440)

And it would do, to add two numbers together,

Donald Knuth (05:24.000)

you could probably expect that would take,

Lex Fridman (05:28.120)

I'll say three milliseconds.

Donald Knuth (05:30.200)

So.

Lex Fridman (05:31.040)

It took pretty fast, the memory is the constraint,

Donald Knuth (05:33.600)

the memory is the problem.

Lex Fridman (05:34.720)

That was why it took three milliseconds,

Donald Knuth (05:36.960)

because it took five milliseconds for the drum to go around

Lex Fridman (05:40.240)

and you had to wait, I don't know, five cycle times.

Donald Knuth (05:45.120)

If you have an instruction, one position on the drum,

Lex Fridman (05:49.040)

then it would be ready to read the data for the instruction

Lex Fridman (05:51.640)

and go three notches.

Lex Fridman (05:55.720)

The drum is 50 cycles around and you go three cycles

Lex Fridman (05:59.800)

and you can get the data and then you can go

Lex Fridman (06:01.240)

another three cycles and get to your next instruction

Donald Knuth (06:04.520)

if the instruction is there, otherwise you spin

Lex Fridman (06:07.160)

until you get to the right place.

Lex Fridman (06:09.360)

And we had no random access memory whatsoever

Lex Fridman (06:13.040)

until my senior year.

Donald Knuth (06:14.480)

Senior year, we got 50 words of random access memory

Lex Fridman (06:17.400)

which were priceless and we would move stuff

Donald Knuth (06:20.600)

up to the random access memory in 60 word chunks

Lex Fridman (06:26.760)

and then we would start again.

Lex Fridman (06:28.080)

So subroutine wanted to go up there.

Lex Fridman (06:31.120)

Could you have predicted the future 60 years later

Lex Fridman (06:35.640)

of computing from then?

Lex Fridman (06:37.440)

You know, in fact, the hardest question I was ever asked

Lex Fridman (06:39.840)

was what could I have predicted?

Lex Fridman (06:44.600)

In other words, the interviewer asked me,

Lex Fridman (06:47.240)

she said, you know, what about computing has surprised you?

Lex Fridman (06:51.480)

And immediately I ran, I rattled off a couple dozen things

Lex Fridman (06:54.680)

and then she said, okay, so what didn't surprise?

Lex Fridman (06:57.360)

And I tried for five minutes to think of something

Donald Knuth (07:01.160)

that I would have predicted and I couldn't.

Lex Fridman (07:04.200)

But let me say that this machine, I didn't know,

Donald Knuth (07:09.320)

well, there wasn't much else in the world at that time.

Lex Fridman (07:13.520)

The 650 was the first machine that there were more

Donald Knuth (07:17.360)

than a thousand of ever.

Lex Fridman (07:19.400)

Before that there were, you know, each machine

Donald Knuth (07:22.760)

there might be a half a dozen examples,

Lex Fridman (07:25.040)

maybe a couple dozen.

Donald Knuth (07:25.880)

The first mass market, mass produced.

Lex Fridman (07:28.240)

The first one, yeah, done in quantity.

Lex Fridman (07:30.640)

And IBM didn't sell them, they rented them,

Lex Fridman (07:36.800)

but they rented them to universities that had a great deal.

Lex Fridman (07:44.440)

And so that's why a lot of students learned

Lex Fridman (07:48.360)

about computers at that time.

Lex Fridman (07:51.640)

So you refer to people, including yourself,

Lex Fridman (07:55.760)

who gravitate toward a kind of computational thinking

Donald Knuth (07:59.160)

as geeks, at least I've heard you use that terminology.

Lex Fridman (08:03.520)

It's true that I think there's something

Donald Knuth (08:06.240)

that happened to me as I was growing up

Lex Fridman (08:08.160)

that made my brain structure in a certain way

Donald Knuth (08:11.680)

that resonates with computers.

Lex Fridman (08:14.120)

So there's this space of people, 2% of the population,

Donald Knuth (08:17.560)

you empirically estimate.

Lex Fridman (08:19.800)

That's been fairly constant over most of my career.

Donald Knuth (08:24.880)

However, it might be different now

Lex Fridman (08:28.160)

because kids have different experiences when they're young.

Donald Knuth (08:30.760)

Obviously.

Lex Fridman (08:31.600)

So what does the world look like to a geek?

Lex Fridman (08:35.480)

What is this aspect of thinking that is unique to,

Lex Fridman (08:43.480)

that makes a geek?

Donald Knuth (08:45.320)

This is a hugely important question.

Lex Fridman (08:48.920)

In the 50s, IBM noticed that there were geeks

Lex Fridman (08:53.920)

and nongeeks, and so they tried to hire geeks.

Lex Fridman (08:56.920)

And they put out ads with papers saying,

Donald Knuth (08:58.880)

if you play chess, come to Madison Avenue

Lex Fridman (09:01.400)

for an interview or something like this.

Donald Knuth (09:03.120)

They were trying for some things.

Lex Fridman (09:04.920)

So what is it that I find easy

Lex Fridman (09:08.800)

and other people tend to find harder?

Lex Fridman (09:11.560)

And I think there's two main things.

Donald Knuth (09:14.480)

One is this, is the ability to jump levels

Lex Fridman (09:19.480)

of abstraction.

Lex Fridman (09:26.920)

So you see something in the large

Lex Fridman (09:29.720)

and you see something in the small

Lex Fridman (09:31.440)

and you pass between those unconsciously.

Lex Fridman (09:35.840)

So you know that in order to solve some big problem,

Lex Fridman (09:40.440)

what you need to do is add one to a certain register

Lex Fridman (09:44.840)

and that gets you to another step.

Lex Fridman (09:47.360)

And below the, I don't go down to the electron level,

Lex Fridman (09:51.360)

but I knew what those milliseconds were,

Lex Fridman (09:54.200)

what the drum was like on the 650.

Lex Fridman (09:56.080)

I knew how I was gonna factor a number

Donald Knuth (09:59.680)

or find a root of an equation or something

Lex Fridman (10:03.080)

because of what was doing.

Lex Fridman (10:04.640)

And as I'm debugging, I'm going through,

Lex Fridman (10:08.520)

did I make a key punch error?

Lex Fridman (10:09.880)

Did I write the wrong instruction?

Lex Fridman (10:13.120)

Do I have the wrong thing in a register?

Lex Fridman (10:15.840)

And each level is different.

Lex Fridman (10:20.480)

And this idea of being able to see something

Donald Knuth (10:25.240)

at lots of levels and fluently go between them

Lex Fridman (10:30.000)

seems to me to be much more pronounced

Donald Knuth (10:32.920)

in the people that resonate with computers like I do.

Lex Fridman (10:37.400)

So in my books, I also don't stick just to the high level,

Lex Fridman (10:42.400)

but I mix low level stuff with high level

Lex Fridman (10:48.440)

and this means that some people think

Donald Knuth (10:54.280)

that I should write better books and it's probably true.

Lex Fridman (10:58.680)

But other people say, well, but that's,

Donald Knuth (11:01.480)

if you think like that, then that's the way

Lex Fridman (11:04.400)

to train yourself, keep mixing the levels

Lex Fridman (11:06.880)

and learn more and more how to jump between.

Lex Fridman (11:10.360)

So that's the one thing.

Donald Knuth (11:11.440)

The other thing is that it's more of a talent

Lex Fridman (11:17.040)

to be able to deal with non uniformity

Donald Knuth (11:20.960)

where there's case one, case two, case three,

Lex Fridman (11:25.400)

instead of having one or two rules that govern everything.

Lex Fridman (11:30.120)

So it doesn't bother me if I need,

Lex Fridman (11:35.720)

like an algorithm has 10 steps to it,

Donald Knuth (11:38.520)

each step does something else that doesn't bother me,

Lex Fridman (11:41.120)

but a lot of pure mathematics is based on one or two rules

Donald Knuth (11:45.440)

which are universal and so this means

Lex Fridman (11:49.760)

that people like me sometimes work with systems

Donald Knuth (11:53.200)

that are more complicated than necessary

Lex Fridman (11:54.840)

because it doesn't bother us that we didn't figure out

Donald Knuth (11:58.800)

the simple rule.

Lex Fridman (12:00.880)

And you mentioned that while Jacobi, Boole, Abel,

Donald Knuth (12:05.680)

all the mathematicians in the 19th century

Lex Fridman (12:07.680)

may have had symptoms of geek,

Donald Knuth (12:11.640)

the first 100% legit geek was Turing, Alan Turing.

Lex Fridman (12:16.000)

I think he had, yeah, a lot more of this quality

Donald Knuth (12:21.480)

than anybody, just from reading the kind of stuff he did.

Lex Fridman (12:26.920)

So how does Turing, what influence has Turing had on you

Lex Fridman (12:33.360)

in your way of thinking?

Lex Fridman (12:35.120)

I didn't know that aspect of him

Donald Knuth (12:38.120)

until after I graduated some years.

Lex Fridman (12:40.640)

As undergraduate we had a class that talked about

Donald Knuth (12:44.760)

computability theory and Turing machines

Lex Fridman (12:46.760)

and it was all, it sounded like a very specific kind

Donald Knuth (12:52.280)

of purely theoretical approach to stuff.

Lex Fridman (12:56.420)

So when, how old were they when I learned

Donald Knuth (12:59.320)

that he had a design machine and that he wrote a wonderful

Lex Fridman (13:08.680)

manual for Manchester machines and he invented

Donald Knuth (13:14.680)

all kinds of subroutines and he was a real hacker

Lex Fridman (13:21.360)

that he had his hands dirty.

Donald Knuth (13:24.240)

I thought for many years that he had only done

Lex Fridman (13:28.480)

purely formal work, as I started reading

Donald Knuth (13:31.640)

his own publications, I could feel this kinship

Lex Fridman (13:36.980)

and of course he had a lot of peculiarities,

Donald Knuth (13:41.880)

like he wrote numbers backwards because I mean,

Lex Fridman (13:45.960)

left to right instead of right to left

Donald Knuth (13:47.520)

because that's, it was easier for computers

Lex Fridman (13:50.360)

to process them that way.

Lex Fridman (13:52.960)

What do you mean left to right?

Lex Fridman (13:54.360)

He would write pi as 9, 5, 1, 4.3, I mean, okay.

Donald Knuth (14:05.280)

Right, got it.

Lex Fridman (14:07.120)

4, 1.3, on the blackboard.

Donald Knuth (14:10.420)

I mean, he had trained himself to do that

Lex Fridman (14:16.680)

because the computers he was working with

Donald Knuth (14:19.680)

worked that way inside.

Lex Fridman (14:21.000)

Trained himself to think like a computer.

Donald Knuth (14:22.840)

There you go, that's geek thinking.

Lex Fridman (14:26.520)

You've practiced some of the most elegant

Donald Knuth (14:28.880)

formalism in computer science and yet you're

Lex Fridman (14:33.080)

the creator of a concept like literate programming

Donald Knuth (14:36.800)

which seems to move closer to natural language

Lex Fridman (14:40.280)

type of description of programming.

Donald Knuth (14:43.520)

Yeah, absolutely.

Lex Fridman (14:44.960)

How do you see those two as conflicting

Donald Knuth (14:47.080)

as the formalism of theory and the idea

Lex Fridman (14:50.160)

of literate programming?

Lex Fridman (14:51.480)

So there we are in a nonuniform system

Lex Fridman (14:54.240)

where I don't think one size fits all

Lex Fridman (14:57.600)

and I don't think all truth lies in one kind of expertise.

Lex Fridman (15:03.320)

And so somehow, in a way you'd say my life

Donald Knuth (15:07.560)

is a convex combination of English and mathematics.

Lex Fridman (15:13.600)

And you're okay with that.

Lex Fridman (15:14.520)

And not only that, I think.

Lex Fridman (15:16.360)

Thrive in it.

Donald Knuth (15:17.200)

I wish, you know, I want my kids to be that way,

Lex Fridman (15:18.920)

I want, et cetera, you know, use left brain,

Donald Knuth (15:21.680)

right brain at the same time.

Lex Fridman (15:23.920)

You got a lot more done.

Donald Knuth (15:25.400)

That was part of the bargain.

Lex Fridman (15:28.760)

And I've heard that you didn't really read

Donald Knuth (15:32.600)

for pleasure until into your 30s, you know, literature.

Lex Fridman (15:37.120)

That's true.

Donald Knuth (15:37.960)

You know more about me than I do

Lex Fridman (15:39.240)

but I'll try to be consistent with what you read.

Donald Knuth (15:41.640)

Yeah, no, just believe me.

Lex Fridman (15:42.960)

I just go with whatever story I tell you.

Donald Knuth (15:45.800)

It'll be easier that way.

Lex Fridman (15:46.840)

The conversation works.

Donald Knuth (15:47.680)

Right, yeah, no, that's true.

Lex Fridman (15:49.960)

So I've heard mention of Philip Roth's American Pastoral,

Donald Knuth (15:53.200)

which I love as a book.

Lex Fridman (15:56.480)

I don't know if, it was mentioned as something,

Donald Knuth (15:59.320)

I think, that was meaningful to you as well.

Lex Fridman (16:03.400)

In either case, what literary books

Lex Fridman (16:05.840)

had a lasting impact on you?

Lex Fridman (16:07.320)

What literature, what poetry?

Donald Knuth (16:08.160)

Yeah, okay, good question.

Lex Fridman (16:09.800)

So I met Roth.

Lex Fridman (16:12.600)

Oh, really?

Lex Fridman (16:13.640)

Well, we both got doctors from Harvard on the same day,

Lex Fridman (16:16.680)

so we had lunch together and stuff like that.

Lex Fridman (16:21.480)

But he knew that, you know, computer books would never sell.

Donald Knuth (16:25.080)

Well, all right, so you say you were a teenager

Lex Fridman (16:32.480)

when you left Russia, so I have to say

Donald Knuth (16:36.040)

that Tolstoy was one of the big influences on me,

Lex Fridman (16:39.680)

especially like Anna Karnina,

Donald Knuth (16:42.640)

not because of particularly of the plot of the story,

Lex Fridman (16:48.280)

but because there's this character who,

Donald Knuth (16:53.440)

you know, the philosophical discussions,

Lex Fridman (17:00.400)

the whole way of life is worked out there

Donald Knuth (17:02.480)

among the characters,

Lex Fridman (17:03.520)

and so that I thought was especially beautiful.

Donald Knuth (17:08.520)

On the other hand, Dostoevsky, I didn't like at all

Lex Fridman (17:12.720)

because I felt that his genius was mostly

Donald Knuth (17:16.000)

because he kept forgetting what he had started out to do,

Lex Fridman (17:18.800)

and he was just sloppy.

Donald Knuth (17:21.080)

I didn't think that he polished his stuff at all,

Lex Fridman (17:26.120)

and I tend to admire somebody

Donald Knuth (17:29.040)

who dots the I's and crosses the T's.

Lex Fridman (17:32.440)

So the music of the pros is what you admire more than...

Donald Knuth (17:36.600)

I certainly do admire the music of the language,

Lex Fridman (17:39.440)

which I couldn't appreciate in the Russian original,

Lex Fridman (17:42.360)

but I can in Victor Hugo, because French is closer.

Lex Fridman (17:47.840)

But Tolstoy, I like the same reason.

Donald Knuth (17:51.440)

I like Herman Wouk as a novelist.

Lex Fridman (17:54.040)

I think like his book, Marjorie Morningstar,

Donald Knuth (17:59.200)

has a similar character in Hugo

Lex Fridman (18:02.000)

who developed his own personal philosophy,

Lex Fridman (18:04.200)

and it goes in the...

Lex Fridman (18:08.680)

What's consistent?

Donald Knuth (18:10.200)

Yeah, right, and it's worth pondering.

Lex Fridman (18:14.880)

So, yeah.

Lex Fridman (18:15.720)

So you don't like Nietzsche, and...

Lex Fridman (18:18.080)

Like what?

Donald Knuth (18:18.920)

You don't like Friedrich Nietzsche, or...

Lex Fridman (18:20.640)

Nietzsche, yeah, no, no, yeah, this has...

Donald Knuth (18:23.640)

I keep seeing quotations from Nietzsche,

Lex Fridman (18:26.480)

and he never tempt me to read any further.

Donald Knuth (18:30.280)

Well, he's full of contradictions,

Lex Fridman (18:31.880)

and you will certainly not appreciate him.

Lex Fridman (18:34.400)

But Schiller, I'm trying to get across

Lex Fridman (18:38.120)

what I appreciate in literature,

Lex Fridman (18:40.520)

and part of it is, as you say,

Lex Fridman (18:44.160)

the music of the language, the way it flows,

Lex Fridman (18:48.560)

and take Raymond Chandler versus Dashiell Hammett.

Lex Fridman (18:52.480)

Dashiell Hammett's sentences are awful,

Lex Fridman (18:55.640)

and Raymond Chandler's are beautiful, they just flow.

Lex Fridman (18:59.880)

So I don't read literature

Donald Knuth (19:04.120)

because it's supposed to be good for me,

Lex Fridman (19:07.320)

or because somebody said it's great,

Lex Fridman (19:09.640)

but I find things that I like.

Lex Fridman (19:14.080)

I mean, you mentioned you were dressed like James Bond,

Lex Fridman (19:18.240)

so I love Ian Fleming.

Lex Fridman (19:20.400)

I think he had a really great gift for...

Donald Knuth (19:23.880)

If he has a golf game, or a game of bridge,

Lex Fridman (19:26.600)

or something and this comes into his story,

Donald Knuth (19:29.120)

it'll be the most exciting golf game,

Lex Fridman (19:32.360)

or the absolute best possible hands of bridge that exists,

Lex Fridman (19:38.600)

and he exploits it and tells it beautifully.

Lex Fridman (19:45.680)

So in connecting some things here,

Donald Knuth (19:49.440)

looking at literate programming

Lex Fridman (19:51.280)

and being able to convey in code algorithms

Donald Knuth (19:56.280)

to a computer in a way that mimics how humans speak,

Lex Fridman (1:00:01.340)

across from east to west or a black path from bottom to top.

Lex Fridman (1:00:05.740)

So there's always, it's the perfect information game

Lex Fridman (1:00:09.700)

and people take turns like tic tac toe.

Lex Fridman (1:00:15.100)

And the hex board can be different sizes.

Lex Fridman (1:00:18.780)

But anyway, there's no possibility of a draw

Lex Fridman (1:00:21.700)

and players move one at a time.

Lex Fridman (1:00:24.460)

And so it's gotta be either a first player win

Donald Knuth (1:00:26.660)

or a second player win.

Lex Fridman (1:00:27.900)

Mathematically, you follow out all the trees

Lex Fridman (1:00:30.860)

and either there's always a win for the first player,

Lex Fridman (1:00:34.500)

second player, okay.

Lex Fridman (1:00:36.100)

And it's finite.

Lex Fridman (1:00:37.300)

The game is finite.

Lex Fridman (1:00:38.680)

So there's an algorithm that will decide.

Lex Fridman (1:00:41.260)

You can show it has to be one or the other

Donald Knuth (1:00:43.900)

because the second player could mimic the first player

Lex Fridman (1:00:46.940)

with kind of a pairing strategy.

Lex Fridman (1:00:49.980)

And so you can show that it has to be one way or the other.

Lex Fridman (1:00:56.540)

But we don't know any algorithm anyway.

Donald Knuth (1:00:58.580)

We don't know the third or the fourth.

Lex Fridman (1:01:01.060)

There are cases where you can prove the existence

Donald Knuth (1:01:03.500)

of a solution but nobody knows any way how to find it.

Lex Fridman (1:01:08.620)

But more like the algorithm question,

Donald Knuth (1:01:12.220)

there's a very powerful theorem in graph theory

Lex Fridman (1:01:15.420)

by Robinson and Seymour that says that every class

Donald Knuth (1:01:21.740)

of graphs that is closed under taking minors

Lex Fridman (1:01:27.020)

has a polynomial time algorithm to determine

Donald Knuth (1:01:29.620)

whether it's in this class or not.

Lex Fridman (1:01:31.540)

Now a class of graphs, for example, planar graphs.

Donald Knuth (1:01:33.740)

These are graphs that you can draw in a plane

Lex Fridman (1:01:35.520)

without crossing lines.

Lex Fridman (1:01:37.340)

And a planar graph, taking minors means

Lex Fridman (1:01:41.280)

that you can shrink an edge into a point

Donald Knuth (1:01:45.940)

or you can delete an edge.

Lex Fridman (1:01:49.180)

And so you start with a planar graph

Lex Fridman (1:01:51.160)

and shrink any edge to a point is still planar.

Lex Fridman (1:01:54.260)

Delete an edge is still planar.

Donald Knuth (1:01:56.660)

Okay, now, but there are millions of different ways

Lex Fridman (1:02:06.580)

to describe a family of graph that still remains

Donald Knuth (1:02:11.740)

the same under taking minor.

Lex Fridman (1:02:14.140)

And Robertson and Seymour proved that any such family

Donald Knuth (1:02:17.780)

of graphs, there's a finite number of minimum graphs

Lex Fridman (1:02:22.540)

that are obstructions so that if it's not in the family,

Donald Knuth (1:02:29.540)

then it has to contain, then there has to be a way

Lex Fridman (1:02:34.780)

to shrink it down until you get one

Donald Knuth (1:02:37.540)

of these bad minimum graphs that's not in the family.

Lex Fridman (1:02:41.660)

In the case of a planar graph, the minimum graph

Donald Knuth (1:02:44.500)

is a five pointed star where everything points to another

Lex Fridman (1:02:48.460)

and the minimum graph consisting of trying

Donald Knuth (1:02:50.780)

to connect three utilities to three houses

Lex Fridman (1:02:52.780)

without crossing lines.

Lex Fridman (1:02:54.420)

And so there are two bad graphs that are not planar

Lex Fridman (1:02:58.300)

and every non planar graph contains one

Donald Knuth (1:03:01.220)

of these two bad graphs by shrinking and removing edges.

Lex Fridman (1:03:07.060)

Sorry, can you say it again?

Lex Fridman (1:03:08.260)

So he proved that there's a finite number

Lex Fridman (1:03:11.020)

of these bad graphs.

Donald Knuth (1:03:11.860)

There's always a finite number.

Lex Fridman (1:03:13.180)

So somebody says, here's a family.

Donald Knuth (1:03:15.220)

It's hard to believe.

Lex Fridman (1:03:16.420)

And they present a sequence of 20 papers.

Donald Knuth (1:03:20.860)

I mean, it's deep work, but it's.

Lex Fridman (1:03:25.140)

Because that's for any arbitrary class.

Lex Fridman (1:03:27.340)

So for any arbitrary class that's closed

Lex Fridman (1:03:29.780)

under taking minors.

Donald Knuth (1:03:31.060)

That's closed under, maybe I'm not understanding

Lex Fridman (1:03:33.980)

because it seems like a lot of them

Donald Knuth (1:03:35.220)

are closed under taking minors.

Lex Fridman (1:03:36.820)

Almost all the important classes of graphs are.

Donald Knuth (1:03:39.780)

There are tons of such graphs, but also hundreds

Lex Fridman (1:03:43.820)

of them that arise in applications.

Donald Knuth (1:03:48.140)

I have a book over here called classes of graphs

Lex Fridman (1:03:51.420)

and it's amazing how many different classes

Donald Knuth (1:03:57.260)

of graphs that people have looked at.

Lex Fridman (1:03:58.980)

So why do you bring up this theorem or this proof?

Lex Fridman (1:04:02.380)

So now there are lots of algorithms that are known

Lex Fridman (1:04:06.220)

for special class of graphs.

Donald Knuth (1:04:07.420)

For example, if I have a certain, if I have a chordal graph

Lex Fridman (1:04:10.740)

then I can color it efficiently.

Donald Knuth (1:04:12.400)

If I have some kind of graphs, it'll make a great network.

Lex Fridman (1:04:17.480)

So you'd like to test, somebody gives you a graph

Lex Fridman (1:04:22.600)

and says, oh, is it in this family of graphs?

Lex Fridman (1:04:24.320)

If so, then I can go to the library

Lex Fridman (1:04:28.360)

and find an algorithm that's gonna solve my problem

Lex Fridman (1:04:30.960)

on that graph.

Donald Knuth (1:04:32.840)

Okay, so we wanna have a graph that says,

Lex Fridman (1:04:37.200)

an algorithm that says,

Donald Knuth (1:04:38.960)

you give me a graph, I'll tell you whether it's in this

Lex Fridman (1:04:45.920)

family or not, okay?

Lex Fridman (1:04:48.720)

And so all I have to do is test whether or not

Lex Fridman (1:04:53.140)

that does this given graph have a minor,

Donald Knuth (1:04:55.400)

that's one of the bad ones.

Lex Fridman (1:04:57.080)

A minor is everything you can get by shrinking

Lex Fridman (1:04:59.720)

and removing edges.

Lex Fridman (1:05:01.580)

And given any minor, there's a polynomial time algorithm

Donald Knuth (1:05:04.720)

saying, I can tell whether this is a minor of you.

Lex Fridman (1:05:09.640)

And there's a finite number of bad cases.

Lex Fridman (1:05:11.680)

So I just try, does it have this bad case?

Lex Fridman (1:05:15.120)

Polynomial time, I got the answer.

Lex Fridman (1:05:17.160)

Does it have this bad case?

Lex Fridman (1:05:18.220)

Polynomial time, I got the answer.

Donald Knuth (1:05:21.240)

Total polynomial time.

Lex Fridman (1:05:23.280)

And so I've solved the problem.

Donald Knuth (1:05:24.720)

However, all we know is that the number of minors is finite.

Lex Fridman (1:05:28.640)

We don't know what, we might only know one or two

Donald Knuth (1:05:32.160)

of those minors, but we don't know if we've got a,

Lex Fridman (1:05:34.360)

if we've got 20 of them, we don't know,

Donald Knuth (1:05:36.000)

there might be 21, 25, there's just some,

Lex Fridman (1:05:39.240)

all we know is that it's finite.

Lex Fridman (1:05:42.640)

So here we have a polynomial time algorithm

Lex Fridman (1:05:44.680)

that we don't know.

Donald Knuth (1:05:46.400)

That's a really great example of what you worry about

Lex Fridman (1:05:49.840)

or why you think P equals NP won't be useful.

Lex Fridman (1:05:53.200)

But still, why do you hold the intuition that P equals NP?

Lex Fridman (1:05:58.200)

P equals NP because you have to rule out

Lex Fridman (1:06:03.480)

so many possible algorithms as being not working.

Lex Fridman (1:06:11.320)

You can take the graph and you can represent it

Donald Knuth (1:06:14.080)

as in terms of certain prime numbers,

Lex Fridman (1:06:18.320)

and then you can multiply those together,

Lex Fridman (1:06:20.020)

and then you can take the bitwise AND

Lex Fridman (1:06:23.440)

and construct some certain constant in polynomial time.

Lex Fridman (1:06:30.000)

And then that's perfectly valid algorithm.

Lex Fridman (1:06:33.240)

And there's so many algorithms of that kind.

Donald Knuth (1:06:37.160)

A lot of times we see random,

Lex Fridman (1:06:42.560)

take data and we get coincidences

Donald Knuth (1:06:46.120)

that some fairly random looking number actually is useful

Lex Fridman (1:06:51.120)

because it happens to solve a problem

Donald Knuth (1:06:59.660)

just because there's so many hairs on your head.

Lex Fridman (1:07:06.560)

But it seems like unlikely that two people

Donald Knuth (1:07:10.880)

are gonna have the same number of hairs on their head.

Lex Fridman (1:07:14.600)

But they're obvious, but you can count

Lex Fridman (1:07:17.520)

how many people there are and how many hairs on the head.

Lex Fridman (1:07:20.680)

There must be people walking around in the country

Donald Knuth (1:07:22.600)

that have the same number of hairs on their head.

Lex Fridman (1:07:24.720)

Well, that's a kind of a coincidence

Donald Knuth (1:07:26.720)

that you might say also this particular combination

Lex Fridman (1:07:30.400)

of operations just happens to prove

Donald Knuth (1:07:32.960)

that the graph has a Hamiltonian path.

Lex Fridman (1:07:36.920)

I see lots of cases where unexpected things happen

Donald Knuth (1:07:41.440)

when you have enough possibilities.

Lex Fridman (1:07:44.260)

So because the space of possibility is so huge,

Donald Knuth (1:07:46.640)

your intuition just says it's not.

Lex Fridman (1:07:47.960)

You have to rule them all out.

Lex Fridman (1:07:49.240)

And so that's the reason for my intuition.

Lex Fridman (1:07:51.720)

It's by no means a proof.

Donald Knuth (1:07:53.240)

I mean, some people say, well, P can't equal NP

Lex Fridman (1:07:58.560)

because you've had all these smart people.

Donald Knuth (1:08:02.960)

The smartest designers of algorithms

Lex Fridman (1:08:05.440)

have been racking their brains for years and years

Lex Fridman (1:08:09.080)

and there's million dollar prizes out there

Lex Fridman (1:08:11.080)

and none of them, nobody has thought of the algorithm.

Lex Fridman (1:08:16.080)

So there must be no such algorithm.

Lex Fridman (1:08:19.240)

On the other hand, I can use exactly the same logic

Lex Fridman (1:08:23.040)

and I can say, well, P must be equal to NP

Lex Fridman (1:08:25.840)

because there's so many smart people out here

Donald Knuth (1:08:27.760)

have been trying to prove it unequal to NP

Lex Fridman (1:08:30.520)

and they've all failed.

Donald Knuth (1:08:34.280)

This kind of reminds me of the discussion

Lex Fridman (1:08:36.880)

about the search for aliens.

Donald Knuth (1:08:39.200)

They've been trying to look for them

Lex Fridman (1:08:40.540)

and we haven't found them yet, therefore they don't exist.

Lex Fridman (1:08:43.880)

But you can show that there's so many planets out there

Lex Fridman (1:08:46.280)

that they very possibly could exist.

Donald Knuth (1:08:48.160)

Yeah, right, and then there's also the possibility

Lex Fridman (1:08:52.040)

that they exist but they all discovered machine learning

Donald Knuth (1:08:57.160)

or something and then blew each other up.

Lex Fridman (1:09:00.920)

Well, on that small, quick tangent, let me ask,

Lex Fridman (1:09:03.640)

do you think there's intelligent life

Lex Fridman (1:09:05.200)

out there in the universe?

Donald Knuth (1:09:07.040)

I have no idea.

Lex Fridman (1:09:08.400)

Do you hope so?

Lex Fridman (1:09:09.240)

Do you think about it?

Lex Fridman (1:09:10.400)

I don't spend my time thinking about things

Donald Knuth (1:09:14.920)

that I could never know, really.

Lex Fridman (1:09:16.880)

And yet you do enjoy the fact that there's many things

Donald Knuth (1:09:19.160)

you don't know.

Lex Fridman (1:09:20.360)

You do enjoy the mystery of things.

Donald Knuth (1:09:23.840)

I enjoy the fact that I have limits, yeah.

Lex Fridman (1:09:27.680)

But I don't take time to answer unsolvable questions.

Donald Knuth (1:09:34.120)

Got it.

Lex Fridman (1:09:35.840)

Well, because you've taken on some tough questions

Donald Knuth (1:09:38.940)

that may seem unsolvable.

Lex Fridman (1:09:40.520)

You have taken on some tough questions

Donald Knuth (1:09:42.600)

that may seem unsolvable, but they're in the space.

Lex Fridman (1:09:44.880)

It gives me a thrill when I can get further

Donald Knuth (1:09:46.640)

than I ever thought I could, yeah.

Lex Fridman (1:09:48.960)

But much like with religion, these.

Donald Knuth (1:09:53.160)

I'm glad that there's no proof that God exists or not.

Lex Fridman (1:09:57.440)

I mean, I think.

Donald Knuth (1:09:59.280)

It would spoil the mystery.

Lex Fridman (1:10:00.760)

It would be too dull, yeah.

Lex Fridman (1:10:04.320)

So to quickly talk about the other art

Lex Fridman (1:10:08.240)

of artificial intelligence, what's your view?

Donald Knuth (1:10:14.240)

Artificial intelligence community has developed

Lex Fridman (1:10:16.720)

as part of computer science and in parallel

Donald Knuth (1:10:18.680)

with computer science since the 60s.

Lex Fridman (1:10:21.360)

What's your view of the AI community from the 60s to now?

Lex Fridman (1:10:27.120)

So all the way through, it was the people

Lex Fridman (1:10:29.440)

who were inspired by trying to mimic intelligence

Donald Knuth (1:10:34.440)

or to do things that were somehow

Lex Fridman (1:10:37.840)

the greatest achievements of intelligence

Donald Knuth (1:10:40.140)

that had been inspiration to people

Lex Fridman (1:10:42.520)

who have pushed the envelope of computer science

Donald Knuth (1:10:47.440)

maybe more than any other group of people.

Lex Fridman (1:10:50.320)

So all the way through, it's been a great source

Donald Knuth (1:10:53.040)

of good problems to sink teeth into.

Lex Fridman (1:10:58.040)

Sink teeth into and getting partial answers

Lex Fridman (1:11:06.560)

and then more and more successful answers over the years.

Lex Fridman (1:11:10.560)

So this has been the inspiration

Donald Knuth (1:11:13.840)

for lots of the great discoveries of computer science.

Lex Fridman (1:11:16.400)

Are you yourself captivated by the possibility

Donald Knuth (1:11:18.840)

of creating, of algorithms having echoes

Lex Fridman (1:11:23.200)

of intelligence in them?

Donald Knuth (1:11:24.720)

Not as much as most of the people in the field, I guess,

Lex Fridman (1:11:29.960)

I would say, but that's not to say that they're wrong

Donald Knuth (1:11:34.160)

or that it's just, you asked about my own personal

Lex Fridman (1:11:36.960)

preferences, but the thing that I worry about

Donald Knuth (1:11:47.480)

is when people start believing that they've actually

Lex Fridman (1:11:49.720)

succeeded and because the, it seems to me,

Donald Knuth (1:11:56.520)

there's a huge gap between really understanding something

Lex Fridman (1:12:01.920)

and being able to pretend to understand something

Lex Fridman (1:12:05.440)

and give the illusion of understanding something.

Lex Fridman (1:12:08.240)

Do you think it's possible to create without understanding?

Donald Knuth (1:12:12.120)

Yeah.

Lex Fridman (1:12:12.940)

So to.

Donald Knuth (1:12:13.780)

Oh, I do that all the time too, I mean.

Lex Fridman (1:12:16.480)

So I use random numbers, but there's still this great gap.

Donald Knuth (1:12:24.920)

I don't assert that it's impossible,

Lex Fridman (1:12:26.920)

but I don't see anything coming any closer

Donald Knuth (1:12:31.920)

to really the kind of stuff

Lex Fridman (1:12:36.360)

that I would consider intelligence.

Lex Fridman (1:12:38.880)

So you've mentioned something that,

Lex Fridman (1:12:41.000)

on that line of thinking, which I very much agree with,

Lex Fridman (1:12:45.480)

so The Art of Computer Programming as the book

Lex Fridman (1:12:49.520)

is focused on single processor algorithms,

Lex Fridman (1:12:53.320)

and for the most part, you mentioned.

Lex Fridman (1:12:57.560)

That's only because I set the table of contents in 1962,

Donald Knuth (1:13:00.840)

you have to remember.

Lex Fridman (1:13:02.320)

For sure, there's no.

Donald Knuth (1:13:04.520)

I'm glad I didn't wait until 1965 or something.

Lex Fridman (1:13:08.040)

That's, one book, maybe we'll touch on the Bible,

Lex Fridman (1:13:12.560)

but one book can't always cover the entirety of everything.

Lex Fridman (1:13:17.040)

So I'm glad the table of contents

Donald Knuth (1:13:22.200)

for The Art of Computer Programming is what it is.

Lex Fridman (1:13:25.960)

But you did mention that you thought

Donald Knuth (1:13:29.560)

that an understanding of the way ant colonies

Lex Fridman (1:13:31.620)

are able to perform incredibly organized tasks

Donald Knuth (1:13:35.000)

might well be the key to understanding human cognition.

Lex Fridman (1:13:38.440)

So these fundamentally distributed systems.

Lex Fridman (1:13:42.020)

So what do you think is the difference

Lex Fridman (1:13:43.640)

between the way Don Knuth would sort a list

Lex Fridman (1:13:47.840)

and an ant colony would sort a list

Lex Fridman (1:13:49.760)

or perform an algorithm?

Donald Knuth (1:13:52.840)

Sorting a list isn't the same as cognition, though,

Lex Fridman (1:13:55.840)

but I know what you're getting at is.

Donald Knuth (1:14:00.400)

Well, the advantage of ant colonies,

Lex Fridman (1:14:02.000)

at least we can see what they're doing.

Donald Knuth (1:14:04.560)

We know which ant has talked to which other ant,

Lex Fridman (1:14:07.600)

and it's much harder with the brains

Donald Knuth (1:14:12.680)

to know to what extent neurons are passing signal.

Lex Fridman (1:14:18.280)

So I'm just saying that ant colony might be,

Donald Knuth (1:14:21.680)

if they have the secret of cognition,

Lex Fridman (1:14:25.320)

think of an ant colony as a cognitive single being

Donald Knuth (1:14:29.880)

rather than as a colony of lots of different ants.

Lex Fridman (1:14:32.360)

I mean, just like the cells of our brain

Lex Fridman (1:14:36.040)

and the microbiome and all that is interacting entities,

Lex Fridman (1:14:42.920)

but somehow I consider myself to be a single person.

Donald Knuth (1:14:48.480)

Well, an ant colony, you can say,

Lex Fridman (1:14:51.640)

might be cognitive somehow.

Donald Knuth (1:14:55.480)

It's some suggestion.

Lex Fridman (1:14:57.000)

Yeah, I mean, okay, I smash a certain ant

Lex Fridman (1:15:02.160)

and the organism's saying, hmm, that stung.

Lex Fridman (1:15:05.160)

What was that?

Lex Fridman (1:15:06.880)

But if we're going to crack the secret of cognition,

Lex Fridman (1:15:10.640)

it might be that we could do so

Donald Knuth (1:15:13.020)

by psyching out how ants do it

Lex Fridman (1:15:16.960)

because we have a better chance to measure

Donald Knuth (1:15:19.720)

their communicating by pheromones

Lex Fridman (1:15:21.300)

and by touching each other in sight,

Lex Fridman (1:15:24.080)

but not by much more subtle phenomenon

Lex Fridman (1:15:27.680)

like electric currents going through.

Lex Fridman (1:15:30.280)

But even a simpler version of that,

Lex Fridman (1:15:31.860)

what are your thoughts of maybe Conway's Game of Life?

Donald Knuth (1:15:35.360)

Okay, so Conway's Game of Life

Lex Fridman (1:15:37.120)

is able to simulate any computable process.

Lex Fridman (1:15:44.200)

And any deterministic process is...

Lex Fridman (1:15:46.800)

I like how you went there.

Donald Knuth (1:15:48.000)

I mean, that's not its most powerful thing, I would say.

Lex Fridman (1:15:53.600)

I mean, it can simulate it,

Lex Fridman (1:15:56.720)

but the magic is that the individual units

Lex Fridman (1:16:00.340)

are distributed and extremely simple.

Donald Knuth (1:16:03.760)

Yes, we understand exactly what the primitives are.

Lex Fridman (1:16:06.880)

The primitives, just like with the ant colony,

Donald Knuth (1:16:08.720)

even simpler, though.

Lex Fridman (1:16:09.560)

But still, it doesn't say that I understand life.

Donald Knuth (1:16:16.480)

I mean, it gives me a better insight

Lex Fridman (1:16:24.000)

into what does it mean to have a deterministic universe?

Lex Fridman (1:16:27.920)

What does it mean to have free choice, for example?

Lex Fridman (1:16:35.800)

Do you think God plays dice?

Donald Knuth (1:16:37.920)

Yes.

Lex Fridman (1:16:38.880)

I don't see any reason why God should be forbidden

Donald Knuth (1:16:41.600)

from using the most efficient ways to...

Lex Fridman (1:16:49.280)

I mean, we know that dice are extremely important

Donald Knuth (1:16:52.960)

in efficient algorithms.

Lex Fridman (1:16:54.760)

There are things that couldn't be done well without randomness.

Lex Fridman (1:16:58.120)

And so, I don't see any reason why God should be prohibited.

Lex Fridman (1:17:03.120)

When the algorithm requires it,

Donald Knuth (1:17:06.360)

you don't see why the physics should constrain it.

Lex Fridman (1:17:11.400)

So, in 2001, you gave a series of lectures at MIT

Donald Knuth (1:17:15.760)

about religion and science.

Lex Fridman (1:17:17.080)

No, that was in 1999.

Donald Knuth (1:17:20.880)

The book came out in 2001.

Lex Fridman (1:17:22.760)

So, in 1999, you spent a little bit of time in Boston

Donald Knuth (1:17:26.880)

enough to give those lectures.

Lex Fridman (1:17:30.640)

And I read the 2001 version, most of it.

Donald Knuth (1:17:36.240)

It's quite fascinating to read.

Lex Fridman (1:17:37.360)

I recommend people, it's a transcription of your lectures.

Donald Knuth (1:17:40.800)

So, what did you learn about how ideas get started

Lex Fridman (1:17:44.440)

and grow from studying the history of the Bible?

Donald Knuth (1:17:46.920)

So, you've rigorously studied a very particular part

Lex Fridman (1:17:50.320)

of the Bible.

Lex Fridman (1:17:51.160)

What did you learn from this process

Lex Fridman (1:17:53.640)

about the way us human beings as a society

Donald Knuth (1:17:56.600)

develop and grow ideas, share ideas,

Lex Fridman (1:17:59.640)

and are defined by those ideas?

Donald Knuth (1:18:01.400)

Well, it's hard to summarize that.

Lex Fridman (1:18:05.400)

I wouldn't say that I learned a great deal

Donald Knuth (1:18:08.440)

of really definite things where I could make conclusions,

Lex Fridman (1:18:12.120)

but I learned more about what I don't know.

Donald Knuth (1:18:15.280)

You have a complex subject,

Lex Fridman (1:18:16.720)

which is really beyond human understanding.

Donald Knuth (1:18:21.640)

So, we give up on saying,

Lex Fridman (1:18:23.400)

I'm never gonna get to the end of the road

Lex Fridman (1:18:24.920)

and I'm never gonna understand it,

Lex Fridman (1:18:26.200)

but you say, but maybe it might be good for me

Donald Knuth (1:18:29.720)

to get closer and closer

Lex Fridman (1:18:32.360)

and learn more and more about something.

Lex Fridman (1:18:34.400)

And so, how can I do that efficiently?

Lex Fridman (1:18:39.160)

And the answer is, well, use randomness.

Lex Fridman (1:18:42.920)

And so, try a random subset

Lex Fridman (1:18:48.800)

of that is within my grasp

Lex Fridman (1:18:52.680)

and study that in detail,

Lex Fridman (1:18:56.960)

instead of just studying parts

Donald Knuth (1:18:59.320)

that somebody tells me to study,

Lex Fridman (1:19:00.960)

or instead of studying nothing because it's too hard.

Donald Knuth (1:19:05.400)

So, I decided, for my own amusement once,

Lex Fridman (1:19:14.400)

that I would take a subset

Donald Knuth (1:19:17.080)

of the verses of the Bible

Lex Fridman (1:19:22.080)

and I would try to find out

Lex Fridman (1:19:25.480)

what the best thinkers have said about that small subset.

Lex Fridman (1:19:29.920)

And I had about, let's say 60 verses out of 3,000,

Donald Knuth (1:19:35.000)

I think it's one out of 500 or something like this.

Lex Fridman (1:19:37.560)

And so, then I went to the libraries,

Donald Knuth (1:19:39.360)

which are well indexed.

Lex Fridman (1:19:43.200)

I spent, for example, at Boston Public Library,

Donald Knuth (1:19:48.400)

I would go once a week for a year

Lex Fridman (1:19:52.200)

and I went, I have done times to Hanover Harvard Library

Donald Knuth (1:19:58.560)

to look at this, that weren't in the Boston Public,

Lex Fridman (1:20:02.360)

where scholars had looked and you can go down the shelves

Lex Fridman (1:20:08.480)

and you can look in the index and say,

Lex Fridman (1:20:12.200)

oh, is this verse mentioned anywhere in this book?

Donald Knuth (1:20:15.400)

If so, look at page 105.

Lex Fridman (1:20:17.560)

So, in other words, I could learn not only about the Bible,

Lex Fridman (1:20:20.520)

but about the secondary literature about the Bible,

Lex Fridman (1:20:23.480)

the things that scholars have written about it.

Lex Fridman (1:20:25.960)

And so, that gave me a way to zoom in on parts of the thing,

Lex Fridman (1:20:33.120)

so that I could get more insight.

Lex Fridman (1:20:35.960)

And so, I look at it as a way of giving me some firm pegs,

Lex Fridman (1:20:43.000)

which I could hang pieces of information,

Lex Fridman (1:20:45.760)

but not as things where I would say,

Lex Fridman (1:20:48.960)

and therefore, this is true.

Donald Knuth (1:20:50.800)

In this random approach of sampling the Bible,

Lex Fridman (1:20:54.920)

what did you learn about the most central,

Lex Fridman (1:21:03.120)

one of the biggest accumulation of ideas in our history?

Lex Fridman (1:21:05.440)

It seemed to me that the main thrust was not the one

Donald Knuth (1:21:09.840)

that most people think of as saying,

Lex Fridman (1:21:11.640)

oh, don't have sex or something like this,

Lex Fridman (1:21:16.000)

but that the main thrust was to try to figure out

Lex Fridman (1:21:21.000)

how to live in harmony with God's wishes.

Donald Knuth (1:21:24.000)

I'm assuming that God exists,

Lex Fridman (1:21:26.000)

and as I say, I'm glad that there's no way to prove this,

Donald Knuth (1:21:30.000)

because I would run through the proof once,

Lex Fridman (1:21:35.000)

and then I'd forget it,

Lex Fridman (1:21:36.000)

and I would never speculate about spiritual things

Lex Fridman (1:21:43.000)

and mysteries otherwise,

Lex Fridman (1:21:46.000)

and I think my life would be very incomplete.

Lex Fridman (1:21:51.000)

So, I'm assuming that God exists,

Lex Fridman (1:21:55.000)

but a lot of the people say God doesn't exist,

Lex Fridman (1:22:01.000)

but that's still important to them.

Lex Fridman (1:22:03.000)

And so, in a way, that might still be,

Lex Fridman (1:22:06.000)

whether God is there or not,

Donald Knuth (1:22:08.000)

in some sense, God is important to them.

Lex Fridman (1:22:12.000)

One of the verses I studied, Doc,

Donald Knuth (1:22:16.000)

you can interpret it as saying that it's much better

Lex Fridman (1:22:19.000)

to be an atheist than not to care at all.

Donald Knuth (1:22:24.000)

So, I would say it's similar to the P equals NP discussion.

Lex Fridman (1:22:29.000)

You mentioned a mental exercise that I'd love it

Donald Knuth (1:22:33.000)

if you could partake in yourself,

Lex Fridman (1:22:36.000)

a mental exercise of being God.

Donald Knuth (1:22:39.000)

So, if you were God, Doc Neuth,

Lex Fridman (1:22:42.000)

how would you present yourself to the people of Earth?

Donald Knuth (1:22:45.000)

You mentioned your love of literature,

Lex Fridman (1:22:47.000)

and there's this book that really I can recommend to you.

Donald Knuth (1:22:52.000)

Yeah, the title, I think, is Blasphemy.

Lex Fridman (1:22:55.000)

It talks about God revealing Himself

Donald Knuth (1:22:58.000)

through a computer in Los Alamos,

Lex Fridman (1:23:02.000)

and it's the only book that I've ever read

Donald Knuth (1:23:09.000)

where the punchline was really the very last word of the book

Lex Fridman (1:23:15.000)

and explained the whole idea of the book.

Lex Fridman (1:23:18.000)

And so, I'd only give that away,

Lex Fridman (1:23:20.000)

but it's really very much about this question that you raised.

Lex Fridman (1:23:27.000)

But suppose God said, okay,

Lex Fridman (1:23:32.000)

my previous means of communication with the world

Donald Knuth (1:23:36.000)

are not the best for the 21st century,

Lex Fridman (1:23:39.000)

so what should I do now?

Lex Fridman (1:23:41.000)

And it's conceivable that God would choose

Lex Fridman (1:23:49.000)

the way that's described in this book.

Donald Knuth (1:23:51.000)

Another way to look at this exercise

Lex Fridman (1:23:53.000)

is looking at the human mind,

Donald Knuth (1:23:55.000)

looking at the human spirit, the human life in a systematic way.

Lex Fridman (1:23:59.000)

I think mostly you want to learn humility.

Donald Knuth (1:24:02.000)

You want to realize that once we solve one problem,

Lex Fridman (1:24:04.000)

that doesn't mean that all of a sudden other problems are going to drop out.

Lex Fridman (1:24:09.000)

And we have to realize that there are things beyond our ability.

Lex Fridman (1:24:22.000)

I see hubris all around.

Donald Knuth (1:24:26.000)

Yeah, well said.

Lex Fridman (1:24:28.000)

If you were to run program analysis on your own life,

Lex Fridman (1:24:33.000)

how did you do in terms of correctness, running time, resource use,

Lex Fridman (1:24:39.000)

asymptotically speaking, of course?

Donald Knuth (1:24:41.000)

Okay, yeah, well, I would say

Lex Fridman (1:24:45.000)

that question has not been asked me before.

Lex Fridman (1:24:50.000)

And I started out with library subroutines

Lex Fridman (1:25:01.000)

and learning how to be an automaton that was obedient,

Lex Fridman (1:25:08.000)

and I had the great advantage that I didn't have anybody to blame for my failures.

Lex Fridman (1:25:18.000)

If I started not understanding something,

Donald Knuth (1:25:22.000)

I knew that I should stop playing ping pong,

Lex Fridman (1:25:25.000)

and it was my fault that I wasn't studying hard enough or something,

Donald Knuth (1:25:29.000)

rather than that somebody was discriminating against me in some way.

Lex Fridman (1:25:33.000)

And I don't know how to avoid the existence of biases in the world,

Lex Fridman (1:25:39.000)

but I know that that's an extra burden that I didn't have to suffer from.

Lex Fridman (1:25:46.000)

And then I found from parents,

Donald Knuth (1:25:54.000)

I learned the idea of service to other people

Lex Fridman (1:26:02.000)

as being more important than what I get out of stuff myself.

Donald Knuth (1:26:10.000)

I know that I need to be happy enough in order to be able to be of service,

Lex Fridman (1:26:18.000)

but I came to a philosophy finally that I phrase as,

Donald Knuth (1:26:25.000)

point eight is enough.

Lex Fridman (1:26:28.000)

There was a TV show once called Eight is Enough,

Donald Knuth (1:26:31.000)

which was about somebody had eight kids.

Lex Fridman (1:26:35.000)

But I say point eight is enough, which means if I can have a way of rating happiness,

Donald Knuth (1:26:43.000)

I think it's good design to have an organism that's happy about 80% of the time.

Lex Fridman (1:26:55.000)

And if it was 100% of the time, it would be like everybody's on drugs

Lex Fridman (1:27:01.000)

and everything collapses and nothing works because everybody's just too happy.

Lex Fridman (1:27:09.000)

Do you think you've achieved that point eight optimal balance?

Donald Knuth (1:27:13.000)

There are times when I'm down and I know that I've actually been programmed

Lex Fridman (1:27:22.000)

to be depressed a certain amount of time.

Lex Fridman (1:27:27.000)

And if that gets out of kilter and I'm more depressed than usual,

Lex Fridman (1:27:31.000)

sometimes I find myself trying to think, now, who should I be mad at today?

Donald Knuth (1:27:36.000)

There must be a reason why.

Lex Fridman (1:27:39.000)

But then I realize it's just my chemistry telling me that I'm supposed to be mad at somebody,

Lex Fridman (1:27:45.000)

and so I trigger it up and say, okay, go to sleep and get better.

Lex Fridman (1:27:49.000)

But if I'm not 100% happy, that doesn't mean that I should find somebody that's screwing me

Lex Fridman (1:27:58.000)

and try to silence them.

Lex Fridman (1:28:01.000)

But I'm saying, okay, I'm not 100% happy, but I'm happy enough to be part of a sustainable situation.

Lex Fridman (1:28:14.000)

So that's kind of the numerical analysis I do.

Lex Fridman (1:28:21.000)

You've converged towards the optimal, which for human life is a point eight.

Donald Knuth (1:28:25.000)

I hope it's okay to talk about, as you talked about previously,

Lex Fridman (1:28:30.000)

in 2006 you were diagnosed with prostate cancer.

Lex Fridman (1:28:34.000)

Has that encounter with mortality changed you in some way or the way you see the world?

Lex Fridman (1:28:40.000)

Yeah, it did. The first encounter with mortality was when my dad died,

Lex Fridman (1:28:45.000)

and I went through a month when I sort of came to be comfortable with the fact that I was going to die someday.

Lex Fridman (1:28:59.000)

And during that month, I don't know, I felt okay, but I couldn't sing.

Lex Fridman (1:29:09.000)

And I couldn't do original research either.

Donald Knuth (1:29:14.000)

I sort of remember after three or four weeks, the first time I started having a technical thought that made sense

Lex Fridman (1:29:22.000)

and was maybe slightly creative, I could sort of feel that something was starting to move again.

Lex Fridman (1:29:29.000)

So I felt very empty until I came to grips with it. I learned that this is sort of a standard grief process that people go through.

Donald Knuth (1:29:42.000)

Okay, so then now I'm at a point in my life, even more so than in 2006,

Donald Knuth (1:29:48.000)

where all of my goals have been fulfilled except for finishing the art of computer programming.

Donald Knuth (1:29:54.000)

I had one major unfulfilled goal. I'd wanted all my life to write a piece of music,

Lex Fridman (1:30:07.000)

and I had an idea for a certain kind of music that I thought ought to be written, at least somebody ought to try to do it.

Lex Fridman (1:30:15.000)

And I felt that it wasn't going to be easy, but I wanted proof of concept.

Lex Fridman (1:30:24.000)

I wanted to know if it was going to work or not, and so I spent a lot of time.

Lex Fridman (1:30:28.000)

And finally, I finished that piece, and we had the world premiere last year on my 80th birthday,

Lex Fridman (1:30:36.000)

and we had another premiere in Canada, and there's talk of concerts in Europe and various things.

Lex Fridman (1:30:42.000)

But that's done. It's part of the world's music now, and it's either good or bad, but I did what I was hoping to do.

Lex Fridman (1:30:50.000)

So the only thing that I have on my agenda is to try to do as well as I can with the art of computer programming until I go to CINA.

Lex Fridman (1:31:03.000)

Do you think there's an element of.8 that might apply there?

Donald Knuth (1:31:07.000)

.8? Well, I look at it more that I got actually to 1.0 when that concert was over with.

Lex Fridman (1:31:24.000)

So in 2006, I was at.8, so when I was diagnosed with prostate cancer, then I said, okay, well, I've had all kinds of good luck all my life,

Lex Fridman (1:31:38.000)

and I have nothing to complain about, so I might die now, and we'll see what happens.

Lex Fridman (1:31:45.000)

And so quite seriously, I had no expectation that I deserved better.

Donald Knuth (1:31:57.000)

I didn't make any plans for the future. I came out of the surgery and spent some time learning how to walk again and so on.

Donald Knuth (1:32:11.000)

It was painful for a while, but I got home, and I realized I hadn't really thought about what to do next.

Donald Knuth (1:32:21.000)

I hadn't any expectation. I said, okay, hey, I'm still alive. Okay, now I can write some more books.

Lex Fridman (1:32:28.000)

But I didn't come with the attitude that this was terribly unfair, and I just said, okay, I was accepting whatever turned out.

Lex Fridman (1:32:44.000)

I'd gotten more than my share already, so why should I?

Donald Knuth (1:32:58.000)

When I got home, I realized that I had really not thought about the next step, what I would do after I would be able to work again.

Donald Knuth (1:33:05.000)

I was comfortable with the fact that it was at the end, but I was hoping that I would still be able to learn about satisfiability and also someday even write music.

Donald Knuth (1:33:29.000)

I didn't start seriously on the music project until 2012.

Lex Fridman (1:33:34.000)

So I'm going to be in huge trouble if I don't talk to you about this.

Donald Knuth (1:33:39.000)

In the 70s, you've created the tech typesetting system together with MetaFont language for font description and computer modern family of typefaces.

Donald Knuth (1:33:49.000)

That has basically defined the methodology and the aesthetic of countless research fields, math, physics, beyond computer science, so on.

Donald Knuth (1:34:02.000)

Okay, well, first of all, thank you.

Lex Fridman (1:34:05.000)

I think I speak for a lot of people in saying that.

Lex Fridman (1:34:08.000)

But question in terms of beauty.

Donald Knuth (1:34:11.000)

There's a beauty to typography that you've created, and yet beauty is hard to quantify.

Lex Fridman (1:34:20.000)

How does one create beautiful letters and beautiful equations?

Lex Fridman (1:34:28.000)

Perhaps there's no words to be describing the process.

Lex Fridman (1:34:35.000)

So the great Harvard mathematician George D. Burkhoff wrote a book in the 30s called Aesthetic Measure where he would have pictures of vases and underneath would be a number.

Lex Fridman (1:34:50.000)

And this was how beautiful the vase was.

Lex Fridman (1:34:52.000)

And he had a formula for this.

Lex Fridman (1:34:54.000)

And he actually also wrote about music.

Lex Fridman (1:34:58.000)

So I thought maybe part of my musical composition I would try to program his algorithms so that I would write something that had the highest number by his score.

Lex Fridman (1:35:14.000)

Well, it wasn't quite rigorous enough for a computer to do.

Lex Fridman (1:35:19.000)

But anyway, people have tried to put numerical value on beauty, and he did probably the most serious attempt.

Lex Fridman (1:35:29.000)

And George Gershwin's teacher also wrote two volumes where he talked about his method of composing music.

Lex Fridman (1:35:38.000)

But you're talking about another kind of beauty and letters and letter phrases.

Lex Fridman (1:35:43.000)

Elegance and whatever that curvature is.

Donald Knuth (1:35:46.000)

Right. And so that's in the eye of the beholder, as they say.

Lex Fridman (1:35:53.000)

But striving for excellence in whatever definition you want to give to beauty, then you try to get as close to that as you can somehow.

Lex Fridman (1:36:02.000)

I guess I'm trying to ask, and there may not be a good answer, what loose definitions were you operating under with the community of people that you were working under?

Lex Fridman (1:36:13.000)

Well, the loose definition, I wanted it to appeal to me.

Donald Knuth (1:36:21.000)

To you personally.

Lex Fridman (1:36:22.000)

Yeah.

Lex Fridman (1:36:23.000)

That's a good start, right?

Donald Knuth (1:36:24.000)

Yeah. No, and it failed that test when Volume Two came out with the new printing, and I was expecting it to be the happiest day of my life.

Lex Fridman (1:36:32.000)

And I felt like a burning, like how angry I was that I opened the book and it was in the same beige covers, but it didn't look right on the page.

Lex Fridman (1:36:48.000)

The number two was particularly ugly.

Donald Knuth (1:36:52.000)

I couldn't stand any page that had a two in its page number.

Lex Fridman (1:36:55.000)

And I was expecting that. I spent all this time making measurements and I had looked at stuff in different ways and I had great technology, but I wasn't done.

Donald Knuth (1:37:15.000)

I had to retune the whole thing after 1961.

Lex Fridman (1:37:20.000)

Has it ever made you happy, finally?

Donald Knuth (1:37:22.000)

Oh, yes.

Lex Fridman (1:37:23.000)

Or is it a 0.8?

Donald Knuth (1:37:26.000)

No, and so many books have come out that would never have been written without this.

Lex Fridman (1:37:31.000)

It's just a joy.

Lex Fridman (1:37:34.000)

But now, I mean, all these pages that are sitting up there, if I didn't like them, I would change them.

Lex Fridman (1:37:44.000)

Nobody else has this ability.

Donald Knuth (1:37:48.000)

They have to stick with what I gave them.

Donald Knuth (1:37:50.000)

Yeah. So, in terms of the other side of it, there's the typography, so the look of the type and the curves and the lines.

Lex Fridman (1:37:59.000)

What about the spacing?

Lex Fridman (1:38:01.000)

What about the?

Donald Knuth (1:38:02.000)

The spacing between the white space.

Lex Fridman (1:38:05.000)

Yeah.

Donald Knuth (1:38:06.000)

It seems like you could be a little bit more systematic about the layout or technical.

Lex Fridman (1:38:12.000)

Oh, yeah. You can always go further.

Donald Knuth (1:38:13.000)

I didn't stop at 0.8, but I stopped at about 0.98.

Lex Fridman (1:38:22.000)

It seems like you're not following your own rule for happiness.

Donald Knuth (1:38:27.000)

No, no, no.

Donald Knuth (1:38:30.000)

Of course, there's this, what is the Japanese word, wabi sabi or something, where the most beautiful works of art are those that have flaws because then the person who perceives them adds their own appreciation and that gives the viewer more satisfaction or so on.

Lex Fridman (1:38:53.000)

But no, no, with typography, I wanted it to look as good as I could in the vast majority of cases, and then when it doesn't, then I say, okay, that's 2% more work for the author.

Lex Fridman (1:39:11.000)

But I didn't want to say that my job was to get to 100% and take all the work away from the author.

Donald Knuth (1:39:20.000)

That's what I meant by that.

Lex Fridman (1:39:22.000)

So if you were to venture a guess, how much of the nature of reality do you think we humans understand?

Donald Knuth (1:39:31.000)

You mentioned you appreciate mystery.

Lex Fridman (1:39:34.000)

How much of the world about us is shrouded in mystery?

Lex Fridman (1:39:38.000)

If you were to put a number on it, what percent of it all do we understand?

Lex Fridman (1:39:45.000)

How many leading zeros, 0.00?

Donald Knuth (1:39:49.000)

I don't know.

Lex Fridman (1:39:50.000)

I think it's infinitesimal.

Lex Fridman (1:39:52.000)

How do we think about that and what do we do about that?

Lex Fridman (1:39:55.000)

Do we continue one step at a time?

Donald Knuth (1:39:57.000)

Yeah, we muddle through.

Lex Fridman (1:39:58.000)

I mean, we do our best.

Donald Knuth (1:40:01.000)

We realize that nobody's perfect and we try to keep advancing, but we don't spend time saying we're not there, we're not all the way to the end.

Donald Knuth (1:40:14.000)

Some mathematicians that would be in the office next to me when I was in the math department, they would never think about anything smaller than countable infinity.

Donald Knuth (1:40:25.000)

We intersected that countable infinity because I rarely got up to countable infinity.

Lex Fridman (1:40:31.000)

I was always talking about finite stuff.

Lex Fridman (1:40:33.000)

But even limiting to finite stuff, which the universe might be, there's no way to really know whether the universe isn't just made out of capital N, whatever units you want to call them, quarks or whatever, where capital N is some finite number.

Donald Knuth (1:41:02.000)

All of the numbers that are comprehensible are still way smaller than almost all finite numbers.

Donald Knuth (1:41:08.000)

I got this one paper called Supernatural Numbers where I guess you probably ran into something called Knuth arrow notation.

Lex Fridman (1:41:19.000)

Did you ever run into that?

Donald Knuth (1:41:20.000)

Anyway, so you take the number, I think it's like, and I called it Super K, I named it after myself, but arrow notation is something like 10 and then four arrows and a three or something like that.

Lex Fridman (1:41:36.000)

Now, the arrow notation, if you have no arrows, that means multiplication.

Donald Knuth (1:41:42.000)

X, Y means X times X times X times X, Y times.

Lex Fridman (1:41:47.000)

If you have one arrow, that means exponentiation.

Lex Fridman (1:41:50.000)

So X one arrow Y means X to the X to the X to the X Y times.

Lex Fridman (1:41:56.000)

So I found out, by the way, that this notation was invented by a guy in 1830 and he was one of the English nobility who spent his time thinking about stuff like this.

Lex Fridman (1:42:15.000)

And it was exactly the same concept that I used arrows and he used a slightly different notation.

Lex Fridman (1:42:23.000)

But anyway, and then this Ackermann's function is based on the same kind of ideas, but Ackermann was 1920s.

Lex Fridman (1:42:31.000)

But anyway, you've got this number 10 quadruple arrow three. So that says, well, we take 10 to the 10 to the 10 to the 10 to the 10th and how many times do we do that?

Lex Fridman (1:42:47.000)

Oh, 10 double arrow two times or something. I mean, how tall is that stack?

Lex Fridman (1:42:52.000)

But then we do that again because that was only 10 quadruple arrow two.

Lex Fridman (1:42:58.000)

It gets to be a pretty large number.

Donald Knuth (1:43:01.000)

It gets way beyond comprehension.

Lex Fridman (1:43:05.000)

But it's so small compared to what finite numbers really are because I'm only using four arrows and 10 and a three.

Donald Knuth (1:43:18.000)

I mean, let's have that many number arrows.

Donald Knuth (1:43:22.000)

The boundary between infinite and finite is incomprehensible for us humans anyway.

Donald Knuth (1:43:29.000)

Infinity is a useful way for us to think about extremely large things.

Lex Fridman (1:43:38.000)

And we can manipulate it, but we can never know that the universe is actually anywhere near that.

Lex Fridman (1:43:51.000)

So I realize how little we know.

Lex Fridman (1:44:02.000)

But we found an awful lot of things that are too hard for any one person to know, even in our small universe.

Donald Knuth (1:44:14.000)

Yeah, and we did pretty good.

Lex Fridman (1:44:16.000)

So when you go up to heaven and meet God and get to ask one question that would get answered, what question would you ask?

Lex Fridman (1:44:30.000)

What kind of browser do you have up here?

Donald Knuth (1:44:35.000)

No, actually, I don't think it's meaningful to ask this question, but I certainly hope we had good internet.

Donald Knuth (1:44:49.000)

Okay, on that note, that's beautiful actually.

Lex Fridman (1:44:53.000)

Don, thank you so much.

Donald Knuth (1:44:54.000)

It was a huge honor to talk to you.

Lex Fridman (1:44:55.000)

I really appreciate it.

Donald Knuth (1:44:56.000)

Well, thanks for the gamut of questions.

Lex Fridman (1:44:59.000)

Yeah, it was fun.

Donald Knuth (1:45:00.000)

Thanks for listening to this conversation with Donald Knuth, and thank you to our presenting sponsor, Cash App.

Donald Knuth (1:45:07.000)

Download it, use Code Lex Podcast, you'll get $10, and $10 will go to FIRST, a STEM education nonprofit that inspires hundreds of thousands of young minds to learn and to dream of engineering our future.

Donald Knuth (1:45:20.000)

If you enjoy this podcast, subscribe on YouTube, give it five stars on Apple Podcast, support it on Patreon, or connect with me on Twitter.

Lex Fridman (1:45:28.000)

And now, let me leave you with some words of wisdom from Donald Knuth.

Donald Knuth (1:45:33.000)

We should continually be striving to transform every art into a science, and in the process, we advance the art.

Lex Fridman (1:45:42.000)

Thank you for listening, and hope to see you next time.

Lex Fridman (20:05.920)

what do you think about natural language in general

Lex Fridman (20:08.680)

and the messiness of our human world,

Lex Fridman (20:11.520)

about trying to express difficult things?

Lex Fridman (20:15.600)

So the idea of literate programming

Donald Knuth (20:17.680)

is really to try to understand something better

Lex Fridman (20:22.680)

by seeing it from at least two perspectives,

Donald Knuth (20:25.680)

the formal and the informal.

Lex Fridman (20:27.560)

If we're trying to understand a complicated thing,

Donald Knuth (20:30.320)

if we can look at it in different ways.

Lex Fridman (20:32.040)

And so this is in fact the key to technical writing,

Donald Knuth (20:36.240)

a good technical writer trying not to be obvious about it,

Lex Fridman (20:40.000)

but says everything twice, formally and informally,

Donald Knuth (20:43.960)

or maybe three times, but you try to give the reader

Lex Fridman (20:48.960)

a way to put the concept into his own brain

Donald Knuth (20:56.400)

or her own brain.

Lex Fridman (20:57.720)

Is that better for the writer or the reader or both?

Donald Knuth (21:01.680)

Well, the writer just tries to understand the reader.

Lex Fridman (21:06.760)

That's the goal of a writer,

Donald Knuth (21:08.080)

is to have a good mental image of the reader

Lex Fridman (21:12.080)

and to say what the reader expects next

Lex Fridman (21:15.000)

and to impress the reader with what has impressed the writer

Lex Fridman (21:22.920)

why something is interesting.

Lex Fridman (21:24.720)

So when you have a computer program,

Lex Fridman (21:26.120)

we try to, instead of looking at it as something

Donald Knuth (21:29.400)

that we're just trying to give instruction to the computer,

Lex Fridman (21:31.840)

what we really wanna be is giving insight

Donald Knuth (21:35.680)

to the person who's gonna be maintaining this program

Lex Fridman (21:40.840)

or to the programmer himself when he's debugging it

Donald Knuth (21:44.720)

as to why this stuff is being done.

Lex Fridman (21:47.120)

And so all the techniques of exposition

Donald Knuth (21:51.000)

that a teacher uses or a book writer uses

Lex Fridman (21:54.000)

make you a better programmer

Donald Knuth (21:55.360)

if your program is gonna be not just a one shot deal.

Lex Fridman (22:00.880)

So how difficult is that?

Lex Fridman (22:04.600)

Do you see hope for the combination of informal and formal

Lex Fridman (22:10.280)

for the programming task?

Donald Knuth (22:12.800)

Yeah, I'm the wrong person to ask, I guess,

Lex Fridman (22:15.920)

because I'm a geek, but I think for a geek it's easy.

Donald Knuth (22:21.840)

Some people have difficulty writing

Lex Fridman (22:24.840)

and that might be because there's something

Donald Knuth (22:29.320)

in their brain structure that makes it hard

Lex Fridman (22:31.760)

for them to write or it might be something

Donald Knuth (22:34.400)

just that they haven't had enough practice.

Lex Fridman (22:36.560)

I'm not the right one to judge,

Lex Fridman (22:39.800)

but I don't think you can teach any person

Lex Fridman (22:42.080)

any particular skill.

Donald Knuth (22:44.480)

I do think that writing is half of my life

Lex Fridman (22:49.400)

and so I put it together in a literate program.

Donald Knuth (22:53.040)

Even when I'm writing a one shot program,

Lex Fridman (22:55.840)

I write it in a literate way

Donald Knuth (23:00.000)

because I get it right faster that way.

Lex Fridman (23:04.640)

Now does it get compiled automatically?

Lex Fridman (23:07.120)

Or?

Lex Fridman (23:08.600)

So I guess on the technical side, my question was

Lex Fridman (23:12.080)

how difficult is it to design a system

Lex Fridman (23:14.800)

where much of the programming is done informally?

Lex Fridman (23:19.480)

Informally?

Lex Fridman (23:20.560)

Yeah, informally.

Donald Knuth (23:22.120)

I think whatever works to make it understandable is good,

Lex Fridman (23:28.280)

but then you have to also understand how informal is.

Donald Knuth (23:33.480)

You have to know the limitations.

Lex Fridman (23:35.000)

So by putting the formal and informal together,

Donald Knuth (23:39.640)

this is where it gets locked into your brain.

Lex Fridman (23:45.400)

You can say informally, well,

Donald Knuth (23:50.320)

I'm working on a problem right now, so.

Lex Fridman (23:52.920)

Let's go there.

Lex Fridman (23:54.680)

Can you give me an example of connecting

Lex Fridman (23:58.160)

the informal and the formal?

Donald Knuth (24:00.040)

Well, it's a little too complicated an example.

Lex Fridman (24:03.440)

There's a puzzle that's self referential.

Donald Knuth (24:06.920)

It's called a Japanese arrow puzzle.

Lex Fridman (24:09.240)

And you're given a bunch of boxes.

Donald Knuth (24:13.640)

Each one points north, east, south, or west.

Lex Fridman (24:16.720)

And at the end, you're supposed to fill in each box

Donald Knuth (24:19.680)

with the number of distinct numbers that it points to.

Lex Fridman (24:25.040)

So if I put a three in a box, that means that,

Lex Fridman (24:28.120)

and it's pointing to five other boxes,

Lex Fridman (24:30.040)

that means that there's gonna be three different numbers

Donald Knuth (24:32.200)

in those five boxes.

Lex Fridman (24:34.480)

And those boxes are pointing,

Donald Knuth (24:36.920)

one of them might be pointing to me,

Lex Fridman (24:38.240)

one of them might be pointing the other way.

Lex Fridman (24:40.680)

But anyway, I'm supposed to find a set of numbers

Lex Fridman (24:45.480)

that obeys this complicated condition

Donald Knuth (24:48.800)

that each number counts how many distinct numbers

Lex Fridman (24:52.280)

it points to.

Lex Fridman (24:54.960)

And so a guy sent me his solution to this problem

Lex Fridman (24:58.840)

where he presents formal statements

Donald Knuth (25:04.920)

that say either this is true or this is true

Lex Fridman (25:07.520)

or this is true.

Lex Fridman (25:08.360)

And so I try to render that formal statement informally

Lex Fridman (25:13.600)

and I try to say, I contain a three

Lex Fridman (25:17.400)

and the guys I'm pointing to contain the numbers one,

Lex Fridman (25:23.600)

two, and six.

Lex Fridman (25:25.320)

So by putting it informally and also I convert it

Lex Fridman (25:27.880)

into a dialogue statement,

Donald Knuth (25:32.160)

that helps me understand the logical statement

Lex Fridman (25:35.600)

that he's written down as a string of numbers

Donald Knuth (25:37.680)

in terms of some abstract variables that he had.

Lex Fridman (25:41.120)

That's really interesting.

Lex Fridman (25:42.120)

So maybe an extension of that,

Lex Fridman (25:45.360)

there has been a resurgence in computer science

Lex Fridman (25:48.200)

and machine learning and neural networks.

Lex Fridman (25:52.520)

So using data to construct algorithms.

Lex Fridman (25:56.640)

So it's another way to construct algorithms, really.

Lex Fridman (25:59.240)

Yes, exactly.

Donald Knuth (26:00.080)

If you can think of it that way.

Lex Fridman (26:03.960)

So as opposed to natural language to construct algorithms,

Donald Knuth (26:06.280)

use data to construct algorithms.

Lex Fridman (26:08.280)

So what's your view of this branch of computer science

Donald Knuth (26:13.520)

where data is almost more important

Lex Fridman (26:15.920)

than the mechanism of the algorithm?

Donald Knuth (26:18.760)

It seems to be suited to a certain kind of non geek,

Lex Fridman (26:22.840)

which is probably why it's taken off.

Donald Knuth (26:29.600)

It has its own community that really resonates with that.

Lex Fridman (26:34.560)

But it's hard to trust something like that

Donald Knuth (26:38.680)

because nobody, even the people who work with it,

Lex Fridman (26:43.400)

they have no idea what has been learned.

Donald Knuth (26:47.160)

That's a really interesting thought

Lex Fridman (26:49.520)

that it makes algorithms more accessible

Donald Knuth (26:54.520)

to a different community, a different type of brain.

Lex Fridman (26:58.600)

Yep.

Lex Fridman (26:59.520)

And that's really interesting

Lex Fridman (27:01.040)

because just like literate programming perhaps

Donald Knuth (27:05.680)

could make programming more accessible

Lex Fridman (27:08.800)

to a certain kind of brain.

Donald Knuth (27:10.560)

There are people who think it's just a matter of education

Lex Fridman (27:13.640)

and anybody can learn to be a great programmer.

Donald Knuth (27:16.320)

Anybody can learn to be a great skier.

Lex Fridman (27:23.600)

I wish that were true,

Lex Fridman (27:24.600)

but I know that there's a lot of things

Lex Fridman (27:27.080)

that I've tried to do and I was well motivated

Lex Fridman (27:31.360)

and I kept trying to build myself up

Lex Fridman (27:33.920)

and I never got past a certain level.

Donald Knuth (27:36.320)

I can't view, for example,

Lex Fridman (27:38.120)

I can't view three dimensional objects in my head.

Donald Knuth (27:43.120)

I have to make a model and look at it

Lex Fridman (27:46.600)

and study it from all points of view

Lex Fridman (27:48.520)

and then I start to get some idea.

Lex Fridman (27:50.640)

But other people are good at four dimensions.

Donald Knuth (27:54.560)

Physicists.

Lex Fridman (27:55.800)

Yeah.

Lex Fridman (27:57.880)

So let's go to the art of computer programming.

Lex Fridman (28:05.400)

In 1962, you set the table of contents

Lex Fridman (28:09.160)

for this magnum opus, right?

Lex Fridman (28:12.960)

Yep.

Donald Knuth (28:13.800)

It was supposed to be a single book with 12 chapters.

Lex Fridman (28:16.680)

Now today, what is it, 57 years later,

Lex Fridman (28:22.360)

you're in the middle of volume four of seven?

Lex Fridman (28:26.720)

In the middle of volume four B is.

Donald Knuth (28:28.520)

Four B.

Lex Fridman (28:29.360)

More precisely.

Donald Knuth (28:30.200)

Can I ask you for an impossible task,

Lex Fridman (28:32.960)

which is try to summarize the book so far

Donald Knuth (28:38.400)

maybe by giving a little examples.

Lex Fridman (28:41.600)

So from the sorting and the search

Lex Fridman (28:43.640)

and the combinatorial algorithms,

Lex Fridman (28:46.320)

if you were to give a summary, a quick elevator summary.

Donald Knuth (28:50.600)

Elevator, that's great.

Lex Fridman (28:51.920)

Yeah, right.

Lex Fridman (28:52.760)

But depending how many floors there are in the building.

Lex Fridman (28:54.640)

Yeah.

Donald Knuth (28:56.080)

The first volume called Fundamental Algorithms

Lex Fridman (28:58.440)

talks about something that you can't,

Donald Knuth (29:02.360)

the stuff you can't do without.

Lex Fridman (29:04.920)

You have to know the basic concepts of what is a program,

Lex Fridman (29:09.920)

what is an algorithm.

Lex Fridman (29:11.600)

And it also talks about a low level machine

Lex Fridman (29:15.960)

so you can have some kind of an idea what's going on.

Lex Fridman (29:20.000)

And it has basic concepts of input and output

Lex Fridman (29:24.280)

and subroutines.

Lex Fridman (29:26.600)

Induction.

Donald Knuth (29:27.880)

Induction, right.

Lex Fridman (29:29.600)

Mathematical, preliminary.

Lex Fridman (29:31.600)

So the thing that makes my book different

Lex Fridman (29:34.200)

from a lot of others is that I try to,

Donald Knuth (29:39.200)

not only present the algorithm,

Lex Fridman (29:40.800)

but I try to analyze them,

Donald Knuth (29:42.200)

which means quantitatively I say,

Lex Fridman (29:44.480)

not only does it work, but it works this fast.

Donald Knuth (29:47.640)

Okay, and so I need math for that.

Lex Fridman (29:49.560)

And then there's the standard way to structure data inside

Lex Fridman (29:52.600)

and represent information in the computer.

Lex Fridman (29:56.080)

So that's all volume one.

Donald Knuth (29:58.360)

Volume two talks, it's called Seminumerical Algorithms.

Lex Fridman (30:01.520)

And here we're writing programs,

Lex Fridman (30:04.200)

but we're also dealing with numbers.

Lex Fridman (30:07.240)

Algorithms deal with any kinds of objects,

Lex Fridman (30:10.480)

but specific when there's objects or numbers,

Lex Fridman (30:13.440)

well then we have certain special paradigms

Donald Knuth (30:17.920)

that apply to things that involve numbers.

Lex Fridman (30:20.680)

And so there's arithmetic on numbers

Lex Fridman (30:24.800)

and there's matrices full of numbers,

Lex Fridman (30:27.400)

there's random numbers,

Lex Fridman (30:29.040)

and there's power series full of numbers.

Lex Fridman (30:31.680)

There's different algebraic concepts

Donald Knuth (30:34.360)

that have numbers in structured ways.

Lex Fridman (30:37.280)

And arithmetic in the way a computer

Donald Knuth (30:38.800)

would think about arithmetic, so floating point.

Lex Fridman (30:41.640)

Floating point arithmetic, high precision arithmetic,

Donald Knuth (30:44.880)

not only addition, subtraction, multiplication,

Lex Fridman (30:47.080)

but also comparison of numbers.

Lex Fridman (30:50.960)

So then volume three talks about.

Lex Fridman (30:53.840)

I like that one, sorting and search.

Donald Knuth (30:55.320)

Sorting and search. I love sorting.

Lex Fridman (30:57.080)

Right, so here we're not dealing necessarily with numbers

Donald Knuth (31:00.960)

because you sort letters and other objects

Lex Fridman (31:03.760)

and searching we're doing all the time with Google nowadays,

Lex Fridman (31:06.440)

but I mean, we have to find stuff.

Lex Fridman (31:09.560)

So again, algorithms that underlie

Donald Knuth (31:14.480)

all kinds of applications.

Lex Fridman (31:16.760)

None of these volumes is about a particular application,

Lex Fridman (31:19.160)

but the applications are examples

Lex Fridman (31:20.840)

of why people want to know about sorting,

Lex Fridman (31:23.640)

why people want to know about random numbers.

Lex Fridman (31:26.680)

So then volume four goes into combinatorial algorithm.

Donald Knuth (31:31.080)

This is where we have zillions of things to deal with

Lex Fridman (31:34.960)

and here we keep finding cases where one good idea

Donald Knuth (31:41.880)

can make something go more than a million times faster.

Lex Fridman (31:45.960)

And we're dealing with problems

Donald Knuth (31:49.480)

that are probably never gonna be solved efficiently,

Lex Fridman (31:53.800)

but that doesn't mean we give up on them

Lex Fridman (31:56.960)

and we have this chance to have good ideas

Lex Fridman (32:00.480)

and go much, much faster on them.

Lex Fridman (32:02.200)

So that's combinatorial algorithms

Lex Fridman (32:04.800)

and those are the ones that are,

Donald Knuth (32:06.880)

I mean, you said sorting is most fun for you.

Lex Fridman (32:09.840)

It's true, it's fun, but combinatorial algorithms

Donald Knuth (32:13.600)

are the ones that I always enjoyed the most

Lex Fridman (32:18.080)

because that's when my skillet programming had most payoff.

Donald Knuth (32:22.160)

The difference between an obvious algorithm

Lex Fridman (32:26.080)

that you think up first thing and an interesting,

Donald Knuth (32:31.760)

subtle algorithm that's not so obvious,

Lex Fridman (32:34.160)

but run circles around the other one,

Donald Knuth (32:37.360)

that's where computer science really comes in.

Lex Fridman (32:43.560)

And a lot of these combinatorial methods

Donald Knuth (32:46.800)

were found first in applications

Lex Fridman (32:49.640)

to artificial intelligence or cryptography.

Lex Fridman (32:52.400)

And in my case, I just liked them

Lex Fridman (32:58.160)

and it was associated more with puzzles.

Lex Fridman (33:01.560)

Do you like them most in the domain of graphs

Lex Fridman (33:04.080)

and graph theory?

Donald Knuth (33:04.960)

Graphs are great because they're terrific models

Lex Fridman (33:08.560)

of so many things in the real world

Lex Fridman (33:10.600)

and you throw numbers on a graph,

Lex Fridman (33:13.480)

you got a network and so there you have many more things.

Lex Fridman (33:18.480)

But combinatorial in general is any arrangement

Lex Fridman (33:24.360)

of objects that has some kind of higher structure,

Donald Knuth (33:30.720)

nonrandom structure and is it possible

Lex Fridman (33:35.160)

to put something together satisfying all these conditions?

Donald Knuth (33:39.360)

Like I mentioned arrows a minute ago,

Lex Fridman (33:41.800)

is there a way to put these numbers

Lex Fridman (33:44.440)

on a bunch of boxes that are pointing to each other?

Lex Fridman (33:47.120)

Is that gonna be possible at all?

Donald Knuth (33:48.800)

That's volume four.

Lex Fridman (33:50.040)

That's volume four.

Lex Fridman (33:52.120)

What does the future hold?

Lex Fridman (33:52.960)

Volume four A was part one.

Lex Fridman (33:54.800)

And what happened was in 1962,

Lex Fridman (33:58.720)

when I started writing down a table of contents,

Donald Knuth (34:03.440)

it wasn't gonna be a book

Lex Fridman (34:04.800)

about computer programming in general,

Donald Knuth (34:07.400)

it was gonna be a book about how to write compilers.

Lex Fridman (34:10.640)

And I was asked to write a book

Donald Knuth (34:14.200)

explaining how to write a compiler.

Lex Fridman (34:16.840)

And at that time, there were only a few dozen people

Donald Knuth (34:22.480)

in the world who had written compilers

Lex Fridman (34:24.120)

and I happened to be one of them.

Lex Fridman (34:25.440)

And I also had some experience writing

Lex Fridman (34:30.840)

for like the campus newspaper and things like that.

Lex Fridman (34:35.480)

So I said, okay, great.

Lex Fridman (34:38.680)

I'm the only person I know who's written a compiler

Lex Fridman (34:42.160)

but hasn't invented any new techniques

Lex Fridman (34:43.960)

for writing compilers.

Lex Fridman (34:45.400)

And all the other people I knew had super ideas

Lex Fridman (34:49.760)

but I couldn't see that they would be able to write a book

Donald Knuth (34:52.320)

that would describe anybody else's ideas with their own.

Lex Fridman (34:55.760)

So I could be the journalist and I could explain

Lex Fridman (34:59.760)

what all these cool ideas about compiler writing were.

Lex Fridman (35:04.280)

And then I started putting down,

Donald Knuth (35:07.280)

well, yeah, you need to have a chapter

Lex Fridman (35:10.200)

about data structures.

Donald Knuth (35:11.080)

You need to have some introductory material.

Lex Fridman (35:13.880)

I wanna talk about searching

Donald Knuth (35:15.200)

because a compiler writer has to look up the variables

Lex Fridman (35:21.440)

in a symbol table and find out which,

Donald Knuth (35:27.400)

when you write the name of a variable in one place,

Lex Fridman (35:29.840)

it's supposed to be the same

Donald Knuth (35:31.520)

as the one you put somewhere else.

Lex Fridman (35:32.680)

So you need all these basic techniques

Lex Fridman (35:35.760)

and I kinda know some arithmetic and stuff.

Lex Fridman (35:40.000)

So I threw in these chapters

Lex Fridman (35:42.040)

and I threw in a chapter on combinatorics

Lex Fridman (35:44.560)

because that was what I really enjoyed programming the most

Lex Fridman (35:48.400)

but there weren't many algorithms known

Lex Fridman (35:50.400)

about combinatorial methods in 1962.

Lex Fridman (35:53.840)

So that was a kind of a short chapter

Lex Fridman (35:55.440)

but it was sort of thrown in just for fun.

Lex Fridman (35:58.160)

And chapter 12 was gonna be actual compilers,

Lex Fridman (36:01.400)

applying all the stuff in chapters one to 11

Donald Knuth (36:05.600)

to make compilers.

Lex Fridman (36:06.560)

Well, okay, so that was my table of contents from 1962.

Lex Fridman (36:10.640)

And during the 70s, the whole field of combinatorics

Lex Fridman (36:15.400)

went through a huge explosion.

Donald Knuth (36:17.880)

People talk about a combinatorial explosion

Lex Fridman (36:20.040)

and they usually mean by that that the number of cases

Donald Knuth (36:23.560)

goes up, you know, you change end to end plus one

Lex Fridman (36:26.600)

and all of a sudden your problem

Donald Knuth (36:28.640)

has gotten more than 10 times harder.

Lex Fridman (36:31.600)

But there was an explosion of ideas

Donald Knuth (36:35.360)

about combinatorics in the 70s to the point

Lex Fridman (36:38.440)

that like take 1975, I bet you more than half

Donald Knuth (36:44.600)

of all the journals of computer science

Lex Fridman (36:46.840)

were about combinatorial methods.

Lex Fridman (36:49.560)

What kind of problems were occupying people's minds?

Lex Fridman (36:52.440)

What kind of problems in combinatorics?

Lex Fridman (36:54.760)

Was it satisfiability, graph theory?

Lex Fridman (36:57.800)

Yeah, graph theory was quite dominant.

Donald Knuth (36:59.880)

I mean, but all of the NP hard problems

Lex Fridman (37:04.880)

that you have like Hamiltonian path.

Donald Knuth (37:08.800)

Travel salesman.

Lex Fridman (37:09.800)

Going beyond graphs, you had operation research

Donald Knuth (37:14.280)

whenever there was a small class of problems

Lex Fridman (37:17.960)

that had efficient solutions and they were usually

Donald Knuth (37:20.200)

associated with matron theory,

Lex Fridman (37:21.960)

special mathematical construction.

Lex Fridman (37:24.640)

But once we went to things that involve

Lex Fridman (37:27.640)

three things at a time instead of two,

Donald Knuth (37:30.440)

all of a sudden things got harder.

Lex Fridman (37:32.480)

So we had satisfiability problems where if you have clauses,

Donald Knuth (37:37.880)

every clause has two logical elements in it,

Lex Fridman (37:40.640)

then we can satisfy it in linear time.

Donald Knuth (37:43.120)

We can test for satisfiability in linear time,

Lex Fridman (37:45.200)

but if you allow yourself three variables in the clause,

Donald Knuth (37:49.960)

then nobody knows how to do it.

Lex Fridman (37:52.560)

So these articles were about trying to find better ways

Donald Knuth (37:56.840)

to solve cryptography problems and graph theory problems.

Lex Fridman (38:01.840)

We have lots of data, but we didn't know how to find

Donald Knuth (38:05.800)

the best subsets of the data.

Lex Fridman (38:07.160)

Like with sorting, we could get the answer.

Donald Knuth (38:12.040)

Didn't take long.

Lex Fridman (38:12.920)

So how did it continue to change from the 70s to today?

Donald Knuth (38:16.920)

Yeah, so now there may be half a dozen conferences

Lex Fridman (38:20.680)

whose topic is combinatorics, a different kind,

Lex Fridman (38:24.920)

but fortunately I don't have to rewrite my book every month

Lex Fridman (38:28.520)

like I had to in the 70s.

Lex Fridman (38:31.120)

But still there's huge amount of work being done

Lex Fridman (38:34.000)

and people getting better ideas on these problems

Donald Knuth (38:37.680)

that don't seem to have really efficient solutions,

Lex Fridman (38:41.400)

but we still do a lot more with them.

Lex Fridman (38:44.920)

And so this book that I'm finishing now is,

Lex Fridman (38:48.320)

I've got a whole bunch of brand new methods

Donald Knuth (38:51.320)

that as far as I know, there's no other book

Lex Fridman (38:55.520)

that covers this particular approach.

Lex Fridman (39:00.280)

And so I'm trying to do my best of exploring

Lex Fridman (39:04.400)

the tip of the iceberg and I try out lots of things

Lex Fridman (39:10.080)

and keep rewriting as I find better method.

Lex Fridman (39:16.520)

So what's your writing process like?

Lex Fridman (39:18.720)

What's your thinking and writing process like every day?

Lex Fridman (39:24.240)

What's your routine even?

Donald Knuth (39:26.480)

Yeah, I guess it's actually the best question

Lex Fridman (39:29.720)

because I spend seven days a week doing it.

Donald Knuth (39:34.720)

You're the most prepared to answer it.

Lex Fridman (39:36.960)

Yeah, but okay.

Lex Fridman (39:38.720)

So the chair I'm sitting in is where I do...

Lex Fridman (39:45.000)

It's where the magic happens.

Donald Knuth (39:46.680)

Well, reading and writing, the chair is usually

Lex Fridman (39:49.920)

sitting over there where I have other books,

Donald Knuth (39:51.760)

some reference books, but I found this chair

Lex Fridman (39:55.520)

which was designed by a Swedish guy anyway.

Donald Knuth (40:00.400)

It turns out this is the only chair I can really sit in

Lex Fridman (40:02.960)

for hours and hours and not know that I'm in a chair.

Lex Fridman (40:05.640)

But then I have the standup desk right next to us

Lex Fridman (40:09.000)

and so after I write something with pencil and eraser,

Donald Knuth (40:13.920)

I get up and I type it and revise and rewrite.

Lex Fridman (40:20.240)

I'm standing up.

Donald Knuth (40:21.160)

The kernel of the idea is first put on paper.

Lex Fridman (40:24.560)

Yeah.

Donald Knuth (40:25.400)

Right.

Lex Fridman (40:26.240)

And I'll write maybe five programs a week,

Donald Knuth (40:31.000)

of course, literate programming.

Lex Fridman (40:33.000)

And these are, before I describe something in my book,

Donald Knuth (40:36.480)

I always program it to see how it's working

Lex Fridman (40:39.040)

and I try it a lot.

Lex Fridman (40:41.440)

So for example, I learned at the end of January,

Lex Fridman (40:45.040)

I learned of a breakthrough by four Japanese people

Donald Knuth (40:49.960)

who had extended one of my methods in a new direction.

Lex Fridman (40:54.320)

And so I spent the next five days writing a program

Donald Knuth (40:57.760)

to implement what they did.

Lex Fridman (40:59.480)

And then they had only generalized part of what I had done

Lex Fridman (41:04.560)

so then I had to see if I could generalize more parts of it.

Lex Fridman (41:07.560)

And then I had to take their approach

Lex Fridman (41:10.400)

and I had to try it out on a couple of dozen

Lex Fridman (41:13.840)

of the other problems I had already worked out

Donald Knuth (41:16.440)

with my old methods.

Lex Fridman (41:18.320)

And so that took another couple of weeks.

Lex Fridman (41:20.200)

And then I started to see the light

Lex Fridman (41:23.920)

and I started writing the final draft

Lex Fridman (41:28.840)

and then I would type it up,

Lex Fridman (41:32.320)

involve some new mathematical questions.

Lex Fridman (41:34.720)

And so I wrote to my friends

Lex Fridman (41:36.440)

who might be good at solving those problems

Lex Fridman (41:39.560)

and they solved some of them.

Lex Fridman (41:42.560)

So I put that in as exercises.

Lex Fridman (41:45.760)

And so a month later, I had absorbed one new idea

Lex Fridman (41:50.160)

that I learned and I'm glad I heard about it in time.

Donald Knuth (41:54.920)

Otherwise, I wouldn't put my book out

Lex Fridman (41:56.760)

before I'd heard about the idea.

Donald Knuth (41:59.000)

On the other hand, this book was supposed to come in

Lex Fridman (42:01.560)

at 300 pages and I'm up to 350 now.

Donald Knuth (42:04.340)

That added 10 pages to the book.

Lex Fridman (42:06.760)

But if I learn about another one,

Donald Knuth (42:09.280)

my publisher is gonna shoot me.

Lex Fridman (42:11.080)

Well, so in that process, in that one month process,

Lex Fridman (42:17.080)

are some days harder than others?

Lex Fridman (42:19.280)

Are some days harder than others?

Donald Knuth (42:20.960)

Well, yeah, my work is fun, but I also work hard

Lex Fridman (42:24.340)

and every big job has parts

Donald Knuth (42:27.120)

that are a lot more fun than others.

Lex Fridman (42:29.280)

And so many days I'll say,

Lex Fridman (42:31.900)

why do I have to have such high standards?

Lex Fridman (42:35.160)

Why couldn't I just be sloppy and not try this out

Lex Fridman (42:37.480)

and just report the answer?

Lex Fridman (42:40.240)

But I know that people are calling me to do this

Lex Fridman (42:45.240)

and so, okay, so, okay, Don, I'll grit my teeth and do it.

Lex Fridman (42:50.060)

And then the joy comes out when I see that actually,

Donald Knuth (42:54.240)

I'm getting good results and I get even more

Lex Fridman (42:58.960)

when I see that somebody has actually read

Lex Fridman (43:01.440)

and understood what I wrote

Lex Fridman (43:02.640)

and told me how to make it even better.

Donald Knuth (43:05.680)

I did wanna mention something about the method.

Lex Fridman (43:10.680)

So I got this tablet here, where I do the first,

Donald Knuth (43:20.040)

the first writing of concepts, okay, so.

Lex Fridman (43:25.280)

And what language is that in?

Donald Knuth (43:27.800)

Right, so take a look at it, but you know,

Lex Fridman (43:29.920)

here, random say, explain how to draw

Donald Knuth (43:33.000)

such skewed pixel diagrams, okay, so.

Lex Fridman (43:36.200)

I got this paper about 40 years ago

Donald Knuth (43:39.600)

when I was visiting my sister in Canada

Lex Fridman (43:42.120)

and they make tablets of paper with this nice large size

Lex Fridman (43:47.240)

and just the right.

Lex Fridman (43:48.080)

A very small space between lines.

Donald Knuth (43:49.680)

Small spaces, yeah, yeah, take a look.

Lex Fridman (43:51.240)

Maybe also just show it.

Donald Knuth (43:54.400)

Yeah.

Lex Fridman (43:56.400)

Yeah.

Donald Knuth (43:57.720)

Wow.

Lex Fridman (43:59.440)

You know, I've got these manuscripts

Donald Knuth (44:00.560)

going back to the 60s.

Lex Fridman (44:04.600)

And those are where I'm getting my ideas on paper, okay.

Lex Fridman (44:09.360)

But I'm a good typist.

Lex Fridman (44:10.640)

In fact, I went to typing school when I was in high school

Lex Fridman (44:14.640)

and so I can type faster than I think.

Lex Fridman (44:17.560)

So then when I do the editing, stand up and type,

Donald Knuth (44:21.000)

then I revise this and it comes out a lot different

Lex Fridman (44:24.760)

than what, you know, for style and rhythm

Lex Fridman (44:27.840)

and things like that come out at the typing stage.

Lex Fridman (44:31.000)

And you type in tech.

Lex Fridman (44:32.840)

And I type in tech.

Lex Fridman (44:34.160)

And can you think in tech?

Donald Knuth (44:37.240)

No.

Lex Fridman (44:38.200)

So.

Donald Knuth (44:39.040)

To a certain extent, I have only a small number of idioms

Lex Fridman (44:43.360)

that I use.

Donald Knuth (44:44.200)

Like, you know, I'm beginning with theorem,

Lex Fridman (44:45.400)

I do something for displayed equation,

Donald Knuth (44:47.640)

I do something and so on.

Lex Fridman (44:49.920)

But I have to see it and.

Donald Knuth (44:53.360)

In the way that it's on paper here.

Lex Fridman (44:55.280)

Yeah, right.

Lex Fridman (44:56.120)

So for example, Turing wrote, what, The Other Direction.

Lex Fridman (44:59.400)

You don't write macros, you don't think in macros.

Donald Knuth (45:04.320)

Not particularly, but when I need a macro,

Lex Fridman (45:06.080)

I'll go ahead and do it.

Lex Fridman (45:09.840)

But the thing is, I also write to fit.

Lex Fridman (45:12.840)

I mean, I'll change something if I can save a line.

Donald Knuth (45:18.400)

You know, it's like haiku.

Lex Fridman (45:19.800)

I'll figure out a way to rewrite the sentence

Lex Fridman (45:21.880)

so that it'll look better on the page.

Lex Fridman (45:25.200)

And I shouldn't be wasting my time on that,

Lex Fridman (45:27.360)

but I can't resist because I know it's only another 3%

Lex Fridman (45:32.200)

of the time or something like that.

Lex Fridman (45:33.880)

And it could also be argued that

Lex Fridman (45:36.040)

that is what life is about.

Donald Knuth (45:39.000)

Ah, yes, in fact, that's true.

Lex Fridman (45:43.040)

Like, I work in the garden one day a week

Lex Fridman (45:45.360)

and that's kind of a description of my life

Lex Fridman (45:48.400)

is getting rid of weeds, you know,

Donald Knuth (45:50.800)

removing bugs for programs.

Lex Fridman (45:52.880)

So, you know, a lot of writers talk about,

Donald Knuth (45:55.600)

you know, basically suffering, the writing processes,

Lex Fridman (45:58.920)

having, you know, it's extremely difficult.

Lex Fridman (46:02.120)

And I think of programming, especially,

Lex Fridman (46:05.160)

or technical writing that you're doing can be like that.

Lex Fridman (46:08.800)

Do you find yourself, methodologically,

Lex Fridman (46:13.440)

how do you every day sit down to do the work?

Lex Fridman (46:16.960)

Is it a challenge?

Lex Fridman (46:18.560)

You kind of say it's, you know, it's fun.

Lex Fridman (46:24.800)

But it'd be interesting to hear if there are non fun parts

Lex Fridman (46:29.120)

that you really struggle with.

Donald Knuth (46:31.120)

Yeah, so the fun comes when I'm able to put together

Lex Fridman (46:35.640)

ideas of two people who didn't know about each other.

Lex Fridman (46:39.440)

And so I might be the first person

Lex Fridman (46:41.760)

that saw both of their ideas.

Lex Fridman (46:44.240)

And so then, you know, then I get to make the synthesis

Lex Fridman (46:47.880)

and that gives me a chance to be creative.

Lex Fridman (46:52.120)

But the dredge work is where I've got to chase everything

Lex Fridman (46:56.720)

down to its root.

Donald Knuth (46:57.720)

This leads me into really interesting stuff.

Lex Fridman (47:00.200)

I mean, I learn about Sanskrit and I try to give credit

Donald Knuth (47:05.840)

to all the authors.

Lex Fridman (47:06.760)

And so I write to people who know the authors

Donald Knuth (47:12.480)

if they're dead or I communicate this way.

Lex Fridman (47:16.000)

And I got to get the math right.

Lex Fridman (47:18.480)

And I got to tackle all my programs,

Lex Fridman (47:20.480)

try to find holes in them.

Lex Fridman (47:22.800)

And I rewrite the programs after I get a better idea.

Lex Fridman (47:26.840)

Is there ever dead ends?

Donald Knuth (47:28.960)

Oh yeah, I throw stuff out, yeah.

Lex Fridman (47:31.720)

One of the things that I spend a lot of time preparing,

Donald Knuth (47:36.160)

a major example based on the game of baseball.

Lex Fridman (47:40.000)

And I know a lot of people for whom baseball

Donald Knuth (47:44.160)

is the most important thing in the world.

Lex Fridman (47:46.520)

But I also know a lot of people for whom cricket

Donald Knuth (47:49.040)

is the most important in the world or soccer or something.

Lex Fridman (47:52.720)

You know, and I realized that if I had a big example,

Donald Knuth (47:57.720)

I mean, it was gonna have a fold out illustration

Lex Fridman (47:59.840)

and everything.

Lex Fridman (48:00.800)

And I was saying, well, what am I really teaching

Lex Fridman (48:02.640)

about algorithms here where I had this baseball example?

Lex Fridman (48:06.800)

And if I was a person who knew only cricket,

Lex Fridman (48:10.440)

wouldn't they, what would they think about this?

Lex Fridman (48:12.920)

And so I've ripped the whole thing out.

Lex Fridman (48:14.920)

But I had something that would have really appealed

Donald Knuth (48:19.160)

to people who grew up with baseball

Lex Fridman (48:20.960)

as a major theme in their life.

Donald Knuth (48:24.160)

Which is a lot of people, but still a minority.

Lex Fridman (48:28.920)

Small minority, I took out bowling too.

Donald Knuth (48:33.240)

Even a smaller minority.

Lex Fridman (48:36.560)

What's the art in the art of programming?

Lex Fridman (48:40.920)

Why is there, of the few words in the title,

Lex Fridman (48:45.080)

why is art one of them?

Donald Knuth (48:46.440)

Yeah, well, that's what I wrote my Turing lecture about.

Lex Fridman (48:50.760)

And so when people talk about art,

Donald Knuth (48:54.640)

it really, I mean, what the word means is

Lex Fridman (49:00.160)

something that's not in nature.

Lex Fridman (49:02.480)

So when you have artificial intelligence,

Lex Fridman (49:06.440)

art comes from the same root,

Donald Knuth (49:09.240)

saying that this is something

Lex Fridman (49:11.200)

that was created by human beings.

Lex Fridman (49:14.560)

And then it's gotten a further meaning often of fine art,

Lex Fridman (49:19.320)

which has this beauty to the mix.

Lex Fridman (49:21.840)

And so we have things that are artistically done,

Lex Fridman (49:25.120)

and this means not only done by humans,

Lex Fridman (49:28.240)

but also done in a way that's elegant and brings joy.

Lex Fridman (49:35.000)

And has, I guess,

Donald Knuth (49:39.880)

Tolstoy versus Dostoevsky going back.

Lex Fridman (49:44.200)

But anyway, it's that part that says

Donald Knuth (49:48.720)

that it's done well, as well as not only different

Lex Fridman (49:53.240)

from nature.

Donald Knuth (49:54.080)

In general, then, art is what human beings

Lex Fridman (49:59.880)

are specifically good at.

Lex Fridman (50:01.680)

And when they say artificial intelligence,

Lex Fridman (50:04.440)

well, they're trying to mimic human beings.

Lex Fridman (50:07.400)

But there's an element of fine art and beauty.

Lex Fridman (50:11.160)

You are one.

Donald Knuth (50:12.000)

That's what I try to also say,

Lex Fridman (50:14.680)

that you can write a program and make a work of art.

Lex Fridman (50:19.920)

So now, in terms of surprising,

Lex Fridman (50:27.080)

what ideas in writing from search

Donald Knuth (50:31.920)

to the combinatorial algorithms,

Lex Fridman (50:34.080)

what ideas have you come across

Donald Knuth (50:37.160)

that were particularly surprising to you

Lex Fridman (50:42.160)

that changed the way you see a space of problems?

Donald Knuth (50:48.280)

I get a surprise every time I have a bug

Lex Fridman (50:49.960)

in my program, obviously.

Lex Fridman (50:51.760)

But that isn't really what you're at.

Lex Fridman (50:53.960)

More transformational than surprising.

Donald Knuth (50:57.120)

For example, in volume 4A,

Lex Fridman (50:59.360)

I was especially surprised when I learned

Donald Knuth (51:02.280)

about data structure called BDD,

Lex Fridman (51:05.480)

Boolean Decision Diagram.

Donald Knuth (51:08.360)

Because I sort of had the feeling

Lex Fridman (51:10.440)

that as an old timer,

Lex Fridman (51:14.720)

and I've been programming since the 50s,

Lex Fridman (51:19.200)

and BDDs weren't invented until 1986.

Lex Fridman (51:23.240)

And here comes a brand new idea that revolutionizes

Lex Fridman (51:26.880)

the way to represent a Boolean function.

Lex Fridman (51:29.560)

And Boolean functions are so basic

Lex Fridman (51:32.040)

to all kinds of things in,

Donald Knuth (51:35.480)

I mean, logic is, underlies it.

Lex Fridman (51:39.400)

Everything we can describe,

Donald Knuth (51:41.360)

all of what we know in terms of logic somehow,

Lex Fridman (51:45.880)

and propositional logic,

Donald Knuth (51:49.240)

I thought that was cut and dried

Lex Fridman (51:52.800)

and everything was known.

Lex Fridman (51:55.680)

But here comes

Lex Fridman (51:58.560)

Randy Bryant

Lex Fridman (52:00.680)

and discovers that BDDs are incredibly powerful.

Lex Fridman (52:05.680)

Then, so that means I have a whole new section

Donald Knuth (52:12.800)

to the book that I never would have thought of

Lex Fridman (52:14.400)

until 1986, not even until 1990s,

Donald Knuth (52:17.480)

when people started to use it

Lex Fridman (52:21.000)

for a billion dollar of applications.

Lex Fridman (52:26.000)

And it was the standard way to design computers

Lex Fridman (52:29.280)

for a long time,

Donald Knuth (52:30.120)

until SAT solvers came along in the year 2000.

Lex Fridman (52:34.440)

So that's another great big surprise.

Lex Fridman (52:36.960)

So a lot of these things have totally changed

Lex Fridman (52:40.480)

the structure of my book.

Lex Fridman (52:42.440)

And the middle third of volume 4B is about SAT solvers,

Lex Fridman (52:47.040)

and that's 300 plus pages,

Donald Knuth (52:51.200)

which is all about material,

Lex Fridman (52:55.000)

mostly about material that was discovered in this century.

Lex Fridman (52:59.160)

And I had to start from scratch

Lex Fridman (53:02.000)

and meet all the people in the field

Lex Fridman (53:04.120)

and write 15 different SAT solvers

Lex Fridman (53:07.760)

that I wrote while preparing that.

Donald Knuth (53:10.280)

Seven of them are described in the book.

Lex Fridman (53:12.720)

Others were from my own experience.

Lex Fridman (53:16.120)

So newly invented data structures

Lex Fridman (53:17.960)

or ways to represent?

Donald Knuth (53:20.720)

A whole new class of algorithm.

Lex Fridman (53:22.640)

Whole new class of algorithm.

Donald Knuth (53:23.480)

Yeah, and the interesting thing about the BDDs

Lex Fridman (53:27.000)

was that the theoreticians started looking at it

Lex Fridman (53:30.440)

and started to describe all the things

Lex Fridman (53:33.920)

you couldn't do with BDDs.

Lex Fridman (53:36.440)

And so they were getting a bad name

Lex Fridman (53:42.360)

because, okay, they were useful,

Lex Fridman (53:45.480)

but they didn't solve every problem.

Lex Fridman (53:48.280)

I'm sure that the theoreticians are,

Donald Knuth (53:50.440)

in the next 10 years,

Lex Fridman (53:51.760)

are gonna show why machine learning

Donald Knuth (53:54.480)

doesn't solve everything.

Lex Fridman (53:56.360)

But I'm not only worried about the worst case,

Donald Knuth (53:59.680)

I get a huge delight when I can actually solve a problem

Lex Fridman (54:03.640)

that I couldn't solve before.

Donald Knuth (54:05.360)

Even though I can't solve the problem

Lex Fridman (54:07.520)

that it suggests is a further problem,

Donald Knuth (54:10.560)

I know that I'm way better than I was before.

Lex Fridman (54:14.160)

And so I found out that BDDs could do

Donald Knuth (54:16.520)

all kinds of miraculous things.

Lex Fridman (54:19.840)

And so I had to spend quite a few years

Donald Knuth (54:27.080)

learning about that territory.

Lex Fridman (54:31.040)

So in general, what brings you more pleasure?

Donald Knuth (54:36.000)

Proving or showing a worst case analysis of an algorithm

Lex Fridman (54:40.000)

or showing a good average case

Lex Fridman (54:43.840)

or just showing a good case?

Lex Fridman (54:45.840)

That something good,

Donald Knuth (54:46.920)

pragmatically can be done with this algorithm.

Lex Fridman (54:49.320)

Yeah, I like a good case

Donald Knuth (54:50.640)

that is maybe only a million times faster

Lex Fridman (54:53.920)

than I was able to do before.

Donald Knuth (54:55.320)

But, and not worry about the fact

Lex Fridman (54:57.680)

that it's still gonna take too long

Donald Knuth (55:02.600)

if I double the size of the problem.

Lex Fridman (55:05.640)

So that said, you popularized the asymptotic notation

Donald Knuth (55:10.040)

for describing running time,

Lex Fridman (55:13.120)

obviously in the analysis of algorithms.

Donald Knuth (55:15.560)

Worst case is such an important part.

Lex Fridman (55:18.440)

Do you see any aspects of that kind of analysis

Lex Fridman (55:22.360)

as lacking and notation too?

Lex Fridman (55:26.080)

Well, the main purpose should have notations

Donald Knuth (55:29.440)

that help us for the problems we wanna solve.

Lex Fridman (55:33.240)

And so they match our intuitions.

Lex Fridman (55:36.200)

And people who worked in number theory

Lex Fridman (55:38.920)

had used asymptotic notation in a certain way,

Lex Fridman (55:43.120)

but it was only known to a small group of people.

Lex Fridman (55:46.360)

And I realized that, in fact,

Donald Knuth (55:49.280)

it was very useful to be able to have a notation

Lex Fridman (55:52.720)

for something that we don't know exactly what it is,

Lex Fridman (55:55.040)

but we only know partial about it.

Lex Fridman (55:57.400)

And so instead, so for example,

Donald Knuth (56:00.640)

instead of big O notation,

Lex Fridman (56:02.240)

let's just take a much simpler notation

Donald Knuth (56:05.400)

where I'd say zero or one, or zero, one or two.

Lex Fridman (56:10.280)

And suppose that when I had been in high school,

Donald Knuth (56:13.880)

we would be allowed to put in the middle of our formula,

Lex Fridman (56:18.120)

X plus zero, one or two equals Y, okay?

Lex Fridman (56:23.120)

And then we would learn how to multiply

Lex Fridman (56:27.080)

two such expressions together and deal with them.

Donald Knuth (56:32.720)

Well, the same thing big O notation says,

Lex Fridman (56:35.400)

here's something that's, I'm not sure what it is,

Lex Fridman (56:38.960)

but I know it's not too big.

Lex Fridman (56:41.560)

I know it's not bigger than some constant times N squared

Donald Knuth (56:44.200)

or something like that.

Lex Fridman (56:45.520)

So I write big O of N squared.

Lex Fridman (56:47.320)

And now I learned how to add big O of N squared

Lex Fridman (56:50.120)

to big O of N cubed.

Lex Fridman (56:51.120)

And I know how to add big O of N squared to plus one

Lex Fridman (56:55.160)

and square that and how to take logarithmic exponentials

Donald Knuth (56:58.400)

where I have big O's in the middle of them.

Lex Fridman (57:00.400)

And that turned out to be hugely valuable

Donald Knuth (57:04.640)

in all of the work that I was trying to do

Lex Fridman (57:06.300)

as I'm trying to figure out how good an algorithm is.

Lex Fridman (57:09.480)

So have there been algorithms in your journey

Lex Fridman (57:12.800)

that perform very differently in practice

Lex Fridman (57:16.780)

than they do in theory?

Lex Fridman (57:18.780)

Well, the worst case of a combinatorial algorithm

Donald Knuth (57:21.360)

is almost always horrible.

Lex Fridman (57:25.200)

But we have SAT solvers that are solving,

Donald Knuth (57:28.040)

where one of the last exercises in that part of my book

Lex Fridman (57:33.000)

was to figure out a problem that has 100 variables

Donald Knuth (57:37.200)

that's difficult for a SAT solver.

Lex Fridman (57:41.520)

But you would think that a problem

Donald Knuth (57:43.960)

with 100 billion variables has,

Lex Fridman (57:46.280)

requires you to do two to the 100th operations

Donald Knuth (57:50.960)

because that's the number of possibilities

Lex Fridman (57:52.720)

when you have 100 billion variables in two to the 100th.

Donald Knuth (57:57.000)

Two to the 100th is way bigger than we can handle.

Lex Fridman (58:00.240)

10 to the 17th is a lot.

Donald Knuth (58:03.160)

You've mentioned over the past few years

Lex Fridman (58:05.160)

that you believe P may be equal to NP,

Lex Fridman (58:08.520)

but that it's not really,

Lex Fridman (58:11.640)

if somebody does prove that P equals NP,

Donald Knuth (58:14.040)

it will not directly lead to an actual algorithm

Lex Fridman (58:16.680)

to solve difficult problems.

Lex Fridman (58:19.920)

Can you explain your intuition here?

Lex Fridman (58:21.580)

Has it been changed?

Lex Fridman (58:23.440)

And in general, on the difference between

Lex Fridman (58:25.480)

easy and difficult problems of P and NP and so on?

Donald Knuth (58:28.760)

Yeah, so the popular idea is if an algorithm exists,

Lex Fridman (58:34.960)

then somebody will find it.

Lex Fridman (58:36.960)

And it's just a matter of writing it down.

Lex Fridman (58:44.700)

But many more algorithms exist

Donald Knuth (58:48.420)

than anybody can understand or ever make use of.

Lex Fridman (58:51.740)

Or discover, yeah.

Donald Knuth (58:53.200)

Because they're just way beyond human comprehension.

Lex Fridman (58:56.900)

The total number of algorithms is more than mind boggling.

Lex Fridman (59:03.580)

So we have situations now

Lex Fridman (59:06.500)

where we know that algorithms exist,

Lex Fridman (59:08.740)

but we don't have the farthest idea what the algorithms are.

Lex Fridman (59:12.900)

There are simple examples based on game playing

Donald Knuth (59:18.540)

where you have, where you say,

Lex Fridman (59:22.220)

well, there must be an algorithm that exists

Donald Knuth (59:25.140)

to win in the game of Hex because,

Lex Fridman (59:27.940)

for the first player to win in the game of Hex

Donald Knuth (59:29.740)

because Hex is always either a win

Lex Fridman (59:33.500)

for the first player or the second player.

Lex Fridman (59:35.180)

Well, what's the game of Hex?

Lex Fridman (59:36.220)

There's a game of Hex which is based

Donald Knuth (59:38.660)

on putting pebbles onto a hexagonal board

Lex Fridman (59:42.180)

and the white player tries to get a white path

Donald Knuth (59:45.140)

from left to right and the black player tries

Lex Fridman (59:47.100)

to get a black path from bottom to top.

Lex Fridman (59:49.660)

And how does capture occur?

Lex Fridman (59:51.060)

Just so I understand.

Lex Fridman (59:51.900)

And there's no capture.

Lex Fridman (59:53.040)

You just put pebbles down one at a time.

Lex Fridman (59:56.180)

But there's no draws because after all the white

Lex Fridman (59:58.780)

and black are played, there's either gonna be a white path