The following is a conversation with Donald Knuth, 1 of the greatest and most impactful computer scientists and mathematicians ever.

He's the recipient of the 1974 Turing Award, considered the Nobel Prize of computing.

He's the author of the multi-volume work, the magnum opus, The Art of Computer Programming.

He made several key contributions to the rigorous analysis of computational complexity of algorithms, including the popularization of asymptotic notation that we all affectionately know as the big O notation.

He also created the tech typesetting system which most computer scientists, physicists, mathematicians, and scientists and engineers in general use to write technical papers and make them look beautiful.

I can imagine no better guest to end 2019 with than Don, 1 of the kindest, most brilliant people in our field.

This podcast was recorded many months ago.

It's 1 I avoided because perhaps counterintuitively, the conversation meant so much to me.

If you can believe it, I knew even less about recording back then.

The office space was a big cramp for filming, but it was a magical space where Don does most of his work.

It meant a lot to me that he would welcome me into his home.

As many people know, He doesn't check email, so I had to get creative.

I've been doing this podcast on the side for just over a year.

Sometimes I had to sacrifice a bit of sleep, but always happy to do it, and to be part of an amazing community of curious minds.

Thank you for your kind words of support and for the interesting discussions.

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

This is the Artificial Intelligence Podcast.

If you enjoy it, subscribe on YouTube, give it 5 stars on Apple Podcast, follow on Spotify, support on Patreon, or simply connect with me on Twitter at Lex Friedman, spelled F-R-I-D-M-A-N.

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

I'll do 1 or 2 minutes after introducing the episode and never any ads in the middle that break the flow of the conversation.

I hope that works for you and doesn't hurt the listening experience.

I provide timestamps for the start of the conversation that you can skip to, but it helps if you listen to the ad and support this podcast by trying out the product or service being advertised.

This show is presented by Cash App, the number 1 finance app in the App Store.

I personally use Cash App to send money to friends, but you can also use it to buy, sell, and deposit Bitcoin in just seconds.

Cash App also has a new investing feature.

You can buy fractions of a stock, say $1 worth, no matter what the stock price is.

Broker services are provided by Cash App Investing, a subsidiary of Square and member SIPC.

I'm excited to be working with Cash App to support 1 of my favorite organizations called FIRST, best known for their FIRST Robotics and LEGO competitions.

They educate and inspire hundreds of thousands of students in over 110 countries and have a perfect rating on Charity Navigator, which means that donated money is used to maximum effectiveness.

When you get Cash App from the App Store or Google Play and use code LEXPODCAST, you'll get $10 and Cash App will also donate $10 to FIRST, which again is an organization that I've personally seen inspire girls and boys to dream of engineering a better world.

And now here's my conversation with Donald Knuth.

In 1957 at Case Tech, you were once allowed to spend several evenings with a IBM 650 computer, as you've talked about in the past, and you fell in love with computing then.

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

What was it that grabbed you about that computer?

So the IBM 650 was this machine that, well it didn't fill a room, but it was big and noisy.

But when I first saw it, it was through a window, and there were just a lot of lights flashing on it.

I had a job with the statistics group, and I was supposed to punch cards for data and then sort them on another machine.

But then they got this new computer, came in, and It had interesting lights.

Okay, so, well, but I had a key to the building, so I could get in and look at it and got a manual for it.

And my first experience was based on the fact that I could punch cards, basically, which was a big thing for the idea.

But the IMX 650 was big in size, but incredibly small in power.

It had 2,000 words of memory, and a word of memory was 10 decimal digits plus a sign.

And it would do, to add 2 numbers together, you could probably expect that would take, I'll say, 3 milliseconds.

That was why it was it took 3 milliseconds because it took 5 milliseconds for the drum to go around.

And you had to wait, I don't know, 5 cycle times.

If you have an instruction, 1 position on the drum, then it would be ready to read the data for the instruction, you know, 3 notches.

The drum is 50 cycles around, and you go 3 cycles, and you can get the data, and then you can go another 3 cycles and get to your next instruction, if the instruction is there.

Otherwise, you spin until you get to the right place.

And we had no random access memory whatsoever until my senior year.

In my senior year, we got 50 words of random access memory, which were priceless.

And we would move stuff up to the random access memory in 60 word chunks, and then we would start again.

So, subroutine wanted to go up there and...

Could you have predicted the future 60 years later of computing from then?

No, you know, in fact, the hardest question I was ever asked was, what could I have predicted?

In other words, The interviewer asked me, she said, you know, what about computing has surprised you?

You know, and immediately I ran, I rattled off a couple dozen things.

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

And I was, I tried for 5 minutes to think of something that I would have predicted, and I couldn't.

But let me say that this machine, I didn't know, well, there wasn't much else in the world at that time.

The 650 was the first machine that there were more than 1,000 of ever.

Before that, there were, you know, there was each machine there might be a half a dozen examples, maybe.

And IBM didn't sell them, they rented them, but they rented them to universities at great, you know, had a great deal.

And So that's why a lot of students learned about computers at that time.

So you refer to people, including yourself, who gravitate toward a kind of computational thinking as geeks.

At least I've heard you use that terminology.

It's true that I think there's something that happened to me as I was growing up that made my brain structure in a certain way that resonates with computers.

So there's this space of people, 2% of the population, you empirically estimate.

That's been fairly constant over most of my career, however, it might be different now because kids have different experiences when they're young.

So what does the world look like to a geek?

What is this aspect of thinking that is unique to

In the 50s, IBM noticed that there were geeks and non-geeks, and so they tried to hire geeks.

And they put out ads for the paper saying, if you play chess, come to Madison Avenue for an interview or something like this.

So what is it that I find easy and other people tend to find harder?

1 is this ability to jump levels of abstraction.

So you see something in the large and you see something in the small and you pass between those unconsciously.

So you know that in order to solve some big problem, what you need to do is add 1 to a certain register, And that gets you to another step.

And below the, yeah, I don't go down to the electron level, but I knew what those milliseconds were, what the drum was like on the 650.

I knew how I was gonna factor a number or find a root of an equation or something because of what was doing.

And as I'm debugging, I'm going through, did I make a key punch error?

And this idea of being able to see something at lots of levels and fluently go between them seems to me to be much more pronounced in the people that resonate with computers.

So, in my books, I also don't stick just to the high level, but I mix low-level stuff with high level, and this means that some people think that I should write better books.

And it's probably true, but other people say, well, if you think like that, then that's the way to train yourself, like keep mixing the levels and learn more and more how to jump between.

The other thing is that it's more of a talent to be able to deal with non-uniformity, where there's case 1, case 2, case 3, instead of having 1 or 2 rules that govern everything.

So it doesn't bother me if I need, like an algorithm has 10 steps to it, you know, each step does something else.

But a lot of pure mathematics is based on 1 or 2 rules, which are universal.

And so this means that people like me sometimes work with systems that are more complicated than necessary because it doesn't bother us that we didn't figure out the simple rule.

And you mentioned that while Jacobi, Boole, Abel, all the mathematicians in the 19th century may have had symptoms of geek, the first 100% legit geek was Turing, Alan Turing.

I think he had, yeah, a lot more of this quality than any, just from reading the kind of stuff he did.

So how does Turing, What influence has Turing had on you?

Well, okay, so I didn't know that aspect of him until after I graduated some years.

As an undergraduate, we had a class that talked about computability theory and Turing machines, and it was all, it sounded like a very specific kind of purely theoretical approach to stuff.

So, how old was I when I learned that he had a design machine and that he wrote a wonderful manual for Manchester machines.

And he was a real hacker that he had his hands dirty.

I thought for many years that he had only done purely formal work.

As I started reading his own publications, I could feel this kinship.

And of course he had a lot of peculiarities.

Like he wrote numbers backwards because, I mean, left to right instead of right to left, because it was easier for computers to process them that way.

He would write pi as, you know, 9514.3, I mean, okay.

I mean, he had trained himself to do that because the computers he was working with worked that way inside.

Trained himself to think like a computer.

You've practiced some of the most elegant formalism in computer science, and yet you're the creator of a concept like literate programming, which seems to move closer to natural language type of description of programming.

So Do you see those 2 as conflicting, as the formalism of theory and the idea of literate programming?

So there we are in a non-uniform system where I don't think 1 size fits all and I don't think all truth lies in 1 kind of expertise.

And so somehow, in a way, you'd say my life is a convex combination of English and mathematics.

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

Use left brain, right brain at the same time, you got a lot more done.

And I've heard that you didn't really read for pleasure until into your 30s, you know, literature.

That's true, you know more about me than I do, but I'll try to be consistent with what you read.

I just go with whatever story I tell you.

It'll be easier that way, The conversation will

So I've heard mention of Philip Roth's American Pastoral, which I love as a book.

I don't know if, it was mentioned as something, I think, that was meaningful to you as well.

In either case, what literary books had a lasting impact on you?

Well, we both got doctors from Harvard on the same day, so we were, yeah, we had lunch together and stuff like that.

But he knew that computer books would never sell.

So you say you were a teenager when you left Russia.

So, I have to say that Tolstoy was 1 of the big influences on me.

Not because of the plot of the story, but because there's this character who, you know, the philosophical discussions, the whole way of life is worked out there among the characters.

And so that I thought was especially beautiful.

On the other hand, Dostoevsky, I didn't like at all because I felt that his genius was mostly because he kept forgetting what he had started out to do and he was just sloppy.

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

And I tend to admire somebody who dods the I's and crosses the T's.

So the music of the prose is what you admire more than?

I certainly do admire the music of the language, which I couldn't appreciate in the Russian original, but I can in Victor Hugo, because French is closer.

But Tolstoy, I like, the same reason I like Herman Wouk as a novelist.

I think, like, his book Marjorie Morningstar has a similar character in Hugo who developed his own personal philosophy and it goes in...

This has, I keep seeing quotations for Nietzsche and he never tempt me to read any further.

So you will certainly not appreciate him.

But Schiller, you know, I'm trying to get across what I appreciate in literature, and part of it is, as you say, the music of the language, the way it flows.

And take Raymond Chandler versus Dashiell Hammett.

Dashiell Hammett's sentences are awful, and Raymond Chandler's are beautiful.

So I don't read literature because it's supposed to be good for me or because somebody said it's great, but I find things that I like.

You mentioned you were dressed like James Bond.

I think he's got a really great gift for if he has a golf game or a game of bridge or something, and this comes into his story, it'll be the most exciting golf game or the absolute best possible hands of bridge that exist, and he exploits it and tells it beautifully.

So in connecting some things here, looking at literate programming and being able to convey, encode algorithms to a computer in a way that mimics how humans speak.

What do you think about natural language in general and the messiness of our human world, about trying to express difficult things?

So the idea of literate programming is really to try to understand something better by seeing it from at least 2 perspectives, the formal and the informal.

If we're trying to understand a complicated thing, if we can look at it in different ways.

And so this is in fact the key to technical writing, a good technical writer trying not to be obvious about it, but says everything twice, formally and informally, or maybe 3 times.

But you try to give the reader a way to put the concept into his own brain or her own brain.

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

Well, the writer just tries to understand the reader.

That's the goal of a writer, is to have a good mental image of the reader and to say what the reader expects next and to impress the reader with what has impressed the writer, why something is interesting.

So when you have a computer program, we try to, instead of looking at it as something that we're just trying to give an instruction to the computer, what we really want to be is giving insight to the person who's going to be maintaining this program or to the programmer himself when he's debugging it as to why this stuff is being done.

And so all the techniques of exposition that a teacher uses or a book writer uses make you a better programmer if your program is gonna be not just a one-shot deal.

Do you see hope for the combination of informal and formal for the programming task?

Yeah, I'm the wrong person to ask, I guess, because I'm a geek.

Some people have difficulty writing, and that might be because there's something in their brain structure that makes it hard for them to write, or it might be something just that they haven't had enough practice.

I'm not the right 1 to judge, but I don't think you can teach any person any particular skill.

I do think that writing is half of my life, and so I put it together in a literary program.

Even when I'm writing a one-shot program, I write it in a literary way because I get it right faster that way.

So I guess on the technical side, my question was, how difficult is it to design a system where much of the programming is done informally.

I think whatever works to make it understandable is good, but then you have to also understand how informal it is.

So by putting the formal and informal together, this is where it gets locked into your brain.

You can say informally, well, I'm working on a problem right now, so.

Can you give me an example of connecting the informal and the formal?

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

There's a puzzle that's self-referential.

Each 1 points north, east, south, or West.

And at the end, you're supposed to fill in each box with the number of distinct numbers that it points to.

So if I put a 3 in a box, that means that, and it's pointing to 5 other boxes, that means that there's going to be 3 different numbers in those 5 boxes.

And those boxes are pointing, 1 of them might be pointing to me, 1 of them might be pointing the other way.

But anyway, I'm supposed to find a set of numbers that obeys this complicated condition that each number counts how many distinct numbers it points to.

Well, and so Guy sent me his solution to this problem where he presents formal statements that say either this is true or this is true or this is true.

And so I try to render that formal statement informally and I try to say, I contain a 3 and the guys I'm pointing to contain the numbers 1, 2, and 6.

So by putting it informally and also I convert it into a dialogue statement, that helps me understand the logical statement that he's written down as a string of numbers in terms of some abstract variables that he had.

So maybe an extension of that, there has been a resurgence in computer science and machine learning and neural networks.

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

So as opposed to natural language to construct algorithms, use data to construct algorithms.

So what's your view of this branch of computer science where data is almost more important than the mechanism of the algorithm?

It seems to be suited to a certain kind of non-geek.

It has its own community that really resonates with that.

But it's hard to trust something like that because nobody, even the people who work with it, they have no idea what has been learned.

That's a really interesting thought, that it makes algorithms more accessible to a different community, a different type of brain.

And that's really interesting, because just like literate programming, perhaps, could make programming more accessible to a certain kind of brain.

There are people who think it's just a matter of education, and anybody can learn to be a great programmer, anybody can learn to be a great skier.

I wish that were true, but I know that there's a lot of things that I've tried to do and I was well motivated and I kept trying to build myself up and I never got past a certain level.

I can't view, for example, I can't view three-dimensional objects in my head.

I have to make a model and look at it and study it from all points of view and then I start to get some idea of it.

But other people are good at 4 dimensions.

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

In 1962, you set the table of contents for this Magnum Opus, right?

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

Now today, what is it, 57 years later, you're in the middle of volume 4 of 7.

In the middle of volume 4B, more precisely.

Which is try to summarize the book so far, maybe by giving a little examples.

So from the sorting and the search and the combinatorial algorithms, if you were to give a summary, a quick elevator summary.

But depending how many floors there are in the building.

The first volume called Fundamental Algorithms talks about something that you can't, the stuff you can't do without.

You have to know some basic concepts of what is a program, what is an algorithm, and it also talks about a low-level machine so you can have some kind of an idea what's going on.

And it has basic concepts of input output and subroutines.

So the thing that makes my book different from a lot of others is that I try to not only present the algorithm, but I try to analyze them, which means that quantitatively, I say not only does it work, but it works this fast.

And then the standard way to structure data inside and represent information in the computer.

Volume 2 talks, it's called semi-numerical algorithms, and here we're writing programs, but we're also dealing with numbers.

Algorithms deal with any kinds of objects, but when objects are numbers, well then we have certain special paradigms that apply to things that involve numbers, and so there's arithmetic on numbers and there's matrices full of numbers, there's random numbers, and there's power series full of numbers, There's different algebraic concepts that have numbers in structured ways.

in the way a computer would think about arithmetic.

See all Lex Fridman transcripts on Youtube

Donald Knuth: Algorithms, Complexity, and The Art of Computer Programming | Lex Fridman Podcast #62