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

The following is a conversation with Donald Knuth, one 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, one of the kindest, most brilliant people in our field. This podcast was recorded many months ago. It's one 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. So the camera angle is a bit off. I hope that's okay with you. The office space was a bit cramped for filming, but was it? 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. It was quite a journey to get there. As many people know, he doesn't check email, so I had to get creative. The effort was worth it. 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 five stars on Apple Podcasts, follow on Spotify, support on Patreon, or simply connect with me on Twitter lexfridman, spelled F R I D M A n I recently started doing ads at the end of the introduction. I I'll do one or two 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 one 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's 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 one 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 an 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. And I was a freshman, I had a job with the statistics group and I was supposed to punch cards and for data and then sort them on another machine. But then they got this new computer came in and I. And it had interesting, you know, lights. Okay, so, well, but I had a kind of key to the building so I can, you know, 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 is a big thing for. But the Imus 650 was big in size, but incredibly small in power in memory. 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 two numbers together. You could probably expect that would take, I'll say 3 milliseconds.

So still pretty fast. It's the memory is the constraint. The memory is the problem.

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, five cycle Times if, if you have an instruction in one position on the drum, then it would be ready to read the data for the instruction and go three notches. The drum is 50 cycles around and you go three cycles and you can get the data and then you can go another three 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. Senior year we got 50 words of random access memory which were priceless. And we would move stuff up to the, up to the random access memory in 60 word chunks and then we would store it again. So subroutine wanted to go up there.

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

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, computing has surprised you? 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 five minutes to think of something that I, 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 was that there were more than a thousand of ever before that there were, you know, it was each machine there might be a half a dozen examples.

Maybe, maybe first mass market mass produced.

The first one. Yeah. Done in quantity. And IBM didn't sell them, they rented them, but they rented them to universities at, at great, you know, had a great deal and, 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. I've heard, 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 structured in a certain way that, that resonates with, with computers.

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

A fair, that's been proven 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, what is this aspect of thinking that is unique to, that makes, yeah that makes a geek.

This is hugely important question. In, in the 50s IBM noticed that.

That.

There were geeks and non geeks and so they tried to hire geeks and they, and they put out ads with paper saying, you know, if you play chess, come to Madison Avenue. And for an inter or something like this, they were trying for some things. So what is it that I find easy and other people tend to find harder? And I think there's two main things. One is 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 one 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 going to 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? Did I write the wrong instruction? Do I have the wrong thing in a register? And each level is different and this idea of being able to see something at lots of levels and fluently go between them seems to me to be more pronounced, much more pronounced in the, in the people that resonate with computers like 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 but if you think like, like that, then that's the way to train yourself. Keep mixing the levels and learn more and more how to jump between. So that's the one thing. The other thing is that it's more of a talent to be able to deal with non uniformity where there's case one, case two, case three instead of having one or two 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 that doesn't bother me. But a lot of pure mathematics is based on one or two 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 simpler rule.

And you mentioned that while Jacoby boole abo all the mathematicians in the 19th century may have had symptoms of geek the first 100 legit geek was touring Alan Turing.

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

And so how does touring, what influence has touring had on you? Well, in your way of thinking.

So I didn't know that aspect of him until after I graduated some years as 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 of stuff. So when, how old was I, when I, when I learned that he, that he had, you know, a design machine and that he wrote the, you know, he wrote a wonderful manual for, for Manchester machines and, and he invented all, you know, subroutines and, and, and he was a real hacker that, that he got 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, you know, 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.

What do you mean left to right?

He would write PI as, you know, 9, 5. Oh 1, 4.3. I mean, okay.

Right, got it.

4. 1.3 on the blackboard. I mean when he, he, he had trained himself to, to do that because the computers he was working with worked.

That way inside, trained himself to think like a computer. Well, there you go. That, that's geek thinking. 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?

Yeah, absolutely.

Do you see those two as conflicting as the formalism of theory and the idea of literate programming?

So there, there we are in a non uniform system where I don't, I don't think one, one size fits all and I don't, and I don't think all truth lies in one, in one kind of expertise. And so somehow in a way you'd say my, my life is a convex combination of English and mathematics.

And you're okay with that.

And not only that, I think thriving. I wish, you know, I want my kids to be that way. I want, etc, you know, use left brain, right brain. At the same time you get a lot more done. That's, that was part of, the, part of the bargain.

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.

Yeah, no, just believe me. I just go with whatever story I tell you.

It'll be easier that way.

The conversation.

Right, Yeah, I know that's true.

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? What literature?

Okay, good question. So I met Roth.

Oh, really?

Well, we both got doctors from Harvard on the same day, so, so we were, yeah, we had lunch together and stuff like that. And, but he knew that, you know, computer books would never sell well. Well, all right, so you say you, you, you, you were a teenager when you left Russia. So I have to say that Tolstoy was one of the big influences on me. I especially like Anna Karnina, not because of particular of the plot of the story where, 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, I didn't like at all because I, I felt that his genius was mostly because he kept forgetting what he, what he had started out to do, and he was just sloppy. I didn't think that, that, that, that he polished his stuff at all. And I tend to admire somebody who, who dots the I's and crosses the T's.

So the, 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 Wuk as a novelist, I think like his book. Marjorie Morningstar has a similar character in, who developed his own personal philosophy and expo. And, and it goes in, in the, was consistent. Yeah, right. And it's worth, worth pondering.

So, so you don't like Nietzsche and like what, you don't like Friedrich Nietzsche or Nietzsche?

Yeah, no, no. Yeah. This has, I, I, I keep seeing quotations from Nietzsche and, and they never tempt me to.

Well, he's full of contradictions, 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. They just flow. 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. I mean, you mentioned you were dressed like James Bond, so I love Ian Fleming. I think he had 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 exists. 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, how. 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 two 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 three times. But you try to give the, the reader a way to, 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, 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 book writer uses make you a better programmer if you, if your program is going to be not just a one shot deal.

So how difficult is that?

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

Yeah, I, I'm the wrong person to ask, I guess because I'm a geek, but, but I think for a geek it's easy Well, I, I don't know. Not. 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, or it might be something just that they haven't had enough practice. I'm not the right one to, 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 literature program. Even when I'm writing a one shot program, I write it in a literate way because I get it right faster that way.

Now does it get compiled automatically? So I guess on the technical side my question was how difficult is it design a system where much of the programming is done informally?

Informally?

Yeah, informally.

I think whatever works to make it understandable is good, but then you have to also understand how informal it is. You have to know the limitations. You have to. So by putting the formal and informal together, this, this is where, this is where it gets locked into your, into your brain. You can, you can say informally, well, I'm working on a problem right now.

So let's go there. Let's. Can you give me an example of, of connecting the informal and the formal?

Well, it's a little too complicated an example. There's a puzzle that's self referential, it's called a Japanese arrow puzzle. And you're given a bunch of boxes, each one 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 three in a box, that means that, and it's pointing to five other boxes, that means that there's going to be three different numbers in those five boxes. And those boxes are pointing. One of them might be pointing to me, one 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 the 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 three and the guys I'm pointing to contain the numbers one, two and six. So by putting it informally, and also I converted into a, 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 that's really interesting. So maybe an extension of that. There has been a resurgence in computer science and machine learning and neural networks. So using data to construct algorithms. So it's another way to construct algorithms, really? Yes, exactly, if you can think of it that way. 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, which is probably why it's taken off. It has its own community that.