Donald Knuth is a computer scientist, Turing Award winner, father of algorithm analysis, author of The Art of Computer Programming, and creator of TeX. Please support this podcast by checking out our sponsors:
- Coinbase: https://coinbase.com/lex to get $5 in free Bitcoin
- InsideTracker: https://insidetracker.com/lex and use code Lex25 to get 25% off
- NetSuite: http://netsuite.com/lex to get free product tour
- ExpressVPN: https://expressvpn.com/lexpod and use code LexPod to get 3 months free
- BetterHelp: https://betterhelp.com/lex to get 10% off

EPISODE LINKS:
Donald's Stanford Page: https://profiles.stanford.edu/donald-knuth
Donald's Books: https://amzn.to/3heyBsC

PODCAST INFO:
Podcast website: https://lexfridman.com/podcast
Apple Podcasts: https://apple.co/2lwqZIr
Spotify: https://spoti.fi/2nEwCF8
RSS: https://lexfridman.com/feed/podcast/
Full episodes playlist: https://www.youtube.com/playlist?list=PLrAXtmErZgOdP_8GztsuKi9nrraNbKKp4
Clips playlist: https://www.youtube.com/playlist?list=PLrAXtmErZgOeciFP3CBCIEElOJeitOr41

OUTLINE:
0:00 - Introduction
0:48 - First programs
24:11 - Literate programming
27:20 - Beauty in programming
33:15 - OpenAI
42:26 - Optimization 
48:31 - Consciousness
57:14 - Conway's game of life
1:10:01 - Stable marriage 
1:13:21 - Richard Feynman
1:24:15 - Knuth-Morris-Pratt Algorithm
1:33:47 - Hardest problem
1:51:26 - Open source
1:56:39 - Favorite symbols
2:06:12 - Productivity
2:13:53 - Meaning of life

SOCIAL:
- Twitter: https://twitter.com/lexfridman
- LinkedIn: https://www.linkedin.com/in/lexfridman
- Facebook: https://www.facebook.com/lexfridman
- Instagram: https://www.instagram.com/lexfridman
- Medium: https://medium.com/@lexfridman
- Reddit: https://reddit.com/r/lexfridman
- Support on Patreon: https://www.patreon.com/lexfridman

The following is a conversation with Donald Knuth, his second time on this podcast.

Don is a legendary computer scientist, Turing Award winner, father of algorithm analysis, author of the art of computer programming, creator of tech that led to late tech, and 1 of the kindest and most fascinating human beings I've ever got a chance to talk to.

I wrote him a letter a long time ago, he responded, and the rest, as they say, is history.

We've interacted many times since then, and every time has been joyful and inspiring.

To support this podcast, please check out our sponsors in the description.

This is the Lex Friedman Podcast, and here is my conversation with Donald Knuth.

Your first large scale program, you wrote it in IBM 650 Assembler in the summer of

I didn't know about Assembler until a year later.

But the year 1957, and the program is Tic-Tac-Toe.

And I learned about Assembler later that summer.

In 1957, hardly anybody had heard of Assembler.

How would you write a program for this machine?

which meant load the distributor, and then you would give the address of the number you wanted to load into the distributor.

Yesterday, my friend, Doug Spicer at the Computer History Museum sent me a link to something that just went on YouTube.

It was IBM's progress report from 1956, which is very contemporary with

And in 1956, IBM had donated to Stanford University an IBM 650, 1 of the first ones, when they showed a picture of the assembly line for IBM 650s.

And they said, you know, this is number 500 or something coming off the assembly line.

And I had never seen so many IBM 650s I did in this movie that was on YouTube now.

They said, look, we donated 1 of these to Stanford, 1 to MIT, and they mentioned 1 other, 1 other college.

And in December of 56, they donated to my university, K-STEC.

But anyway, they showed a picture then of a class session where a guy was teaching programming and on the blackboard it said

I mean, he was teaching them how to write code for this IBM 650, which was in decimal numbers.

So the instructions were 10 decimal digits.

You had 2 digits that said what to do, 4 digits to say what to do it to, and 4 more digits to say where to get your next instruction.

And there's a manual that describes what each of the numbers mean.

And the manual was actually 1, if the manual had been well written, I probably never would have gone into computer science, but it was so badly written, I figured that I must have a talent for it because I'm only a freshman and I could write a better manual.

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

The first program was factoring a number.

You sat at this big mainframe and you turn the dials, set a number, and then it would punch out the factors of that number on cards.

The input was, yeah, The input was a number, attended a number, and the output was its factors.

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

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

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

I don't remember how I got it into the machine, but I think there was a way to punch it on cards.

Or maybe I could get 7 instructions on a card, 8 instructions, I don't know.

But anyway, so I'm sitting there at the console of the machine.

I mean, I'm doing this at night when nobody else is around.

And so you have 1 set of switches where you can dial the number I'm inputting, but there's another switch that says, okay, now execute 1 instruction and show me what you did.

Or there was another 4 switches, I'd say, stop if you get to that instruction.

So I can say, now go until you get there again and watch.

So I could watch, it would take that number and it would divide it by 2.

And if there's no remainder, then okay, 2 is a factor.

Keep trying until you know you're at the end.

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

I mean, first of all, I might have tried to divide by 1 instead of 2.

You're off by 1 error, as people make all the time.

Maybe I left something in a register that I shouldn't have done.

But the first bugs were pretty, you know, probably on the first night I was able to, I was able to get the factors of 30, you know, as equal to 2, 3, and 5, okay?

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

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

So most of the world is sleeping and you have to be there at night because that's when you get access to the computer.

Between my freshman and sophomore year, I didn't need sleep.

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

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

That was, I didn't get ulcers and stuff like that until later, you know, but.

Well, I don't know if you know Rodney Brooks.

Yeah, he told me a story that he really looked up to you.

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

I think this might have been MIT, I don't know.

And you were waiting for them to fix the machine so you can get back to work late at night.

But no, no, the machine at Danford AI Lab was down an awful lot because they had many talented programmers changing the operating system every day.

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

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

Well, he was saying it's a hardware problem.

They tried to fix it and they reinserted something and smoke was everywhere.

Well, that didn't happen as often as the operatives.

Anyway, it's a funny story, because you're saying there's this tall Don Knuth that I look up to and There was pressure to fix the computer.

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

Yeah, well, I can tell you a bunch of Rodbrooke stories too, but Let's go back to the

And I had more bugs in it than number of lines of code.

I mean, the number of lines of code kept growing.

then I got to put 2 somewhere on the card, I got to put a 3 somewhere on the card, I got to put a 5 somewhere on the card, right?

And you know what, it was my first program, I probably screwed up and it fell off the edge of the card or something like that.

But I didn't realize that there are some tensioned numbers that have more than 8 factors.

And the card has only 80 columns, and so I need 10 columns for every factor.

So my first program didn't take account for the fact that I would have to punch more than 1 card.

My first program, you know, just lined stuff up in memory and then punched the card.

But but after, you know, so by the time I finished, I had to, I had to deal with lots of lots of things.

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

And so it would sit there spinning its wheels and you wouldn't know if it was in a loop or whatever.

That would take me a while for that first 1.

Well, what was your goal with that program?

Was there something you were hoping to find a large prime maybe or the opposite?

No, my goal was to see the lights flashing and understand how this magical machine would be able to do something that took so long by hand.

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

It was much simpler, it didn't have that many bugs in it.

So the Tic-Tac-Toe program is interesting on many levels, but 1 of them is that it had some, you can call machine learning in it.

I don't know how long it's going to be before the name of our field is changed from computer science to machine learning.

But anyway, it was my first experience with machine learning.

Well, first of all, what is the problem you were solving?

So you've got a three-by-three grid, and each can be in 3 states.

It can be empty or it can have an X or an O, right?

So 3 to the ninth is a, well, what is, how big is it?

So anyway, 8 is like 2 to the 3rd, so that would be like 2 to the 6th.

So, the 3 comes from the fact that it's either empty, an X, or an O.

And the 650 was a machine that had only 2,010-digit words.

You go from 0,000 to 1999, and that's it.

And in each word, you have a 10-digit number.

In order to have a memory of every position I've seen, I need 3 to the ninth bits.

Okay, but it was a decimal machine too, it didn't have bits.

But it did have strange instruction where if you had a 10 digit number, but all the digits were either 8 or 9, you'd be 89988 or something like that.

You could make a test whether it was 8 or 9.

That was 1 of the strange things IBM engineers put into the machine.

But anyway, I needed 1 digit for every position I'd seen.

0 meant it was a bad position, 9 meant it was a good position.

I think I started out at 5 or 6, but if you win a game, then you increase the value of that position for you, but you decrease it for your opponent.

I had that much total memory for every possible position was 1 digit, and I had a total of 20,000 digits, which had to also include my program, and all the logic and everything, including how to ask the user what the moves are and things like this.

Okay, so I think I had to work it out because every position in tic-tac-toe is equivalent to roughly 8 others because you can rotate the board, which gives you a factor of 4, and you can also flip it over.

So I might have needed only 3 to the ninth over 8 positions plus a little bit.

But anyway, that was a part of the program to squeeze it into this tiny...

So you tried to find an efficient representation that took account for that kind of rotation.

I had to, otherwise I couldn't do the learning.

So, But I had 3 parts to my Tic-Tac-Toe program, and I called it Brain 1, Brain 2, and Brain 3.

You got to put an x somewhere, it has to go in an empty space, but that's it.

And I think it was, it also, maybe it had, maybe it assumed you were the first player or maybe it allowed you to be first.

I think you're allowed to be either first or second, but had a canned, built-in strategy known to be optimum for Tic-Tac-Toe.

Before I forget, by the way, I learned many years later that Charles Babbage had planned to, had thought about programming tic-tac-toe for his dream machine that he was never able to finish.

Wow, so that was the program he thought about?

And I had however been influenced by a demonstration at the at the Museum of Science and Industry in Chicago, it's like Boston's Science Museum.

I think Bell Labs had prepared a special exhibit about telephones and relay technology, and they had a tic-tac-toe playing machine as part of that exhibit.

So that had been 1 of my, you know, something I'd seen before I was a freshman in college and inspired me to see if I could write a program for it.

Okay, so anyway, I had brain 1, random, you know, knowing nothing, brain 2, knowing everything, Then brain 3 was the learning 1.

And I could play brain 1 against brain 1, brain 1 against brain 2, and so on.

And so you could also play against the user, against a live universe.

But so I started going, the learning thing, and I said, okay, you know, take 2 random, random people, just playing tic-tac-toe, knowing nothing.

And after about, I forget the number now, but it converged after about 600 games to a safe draw.

The way my program learned was actually, it learned how not to make mistakes.

It didn't try to do anything for winning, it just tried to say not losing.

So that was probably because of the way I designed the learning thing.

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

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

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

Was there, did you, did a curiosity and interest in learning systems persist for you?

Yeah, I think naturally it's, we're talking about Rod Brooks, He was teaching all kinds of very small devices to learn stuff.

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

But I mean, he pushed that a little bit too far, but he said he could probably train some little mini bugs to scour out dishes if he had enough financial support.

Because he also mentioned that during those years, there was discussion about, inspired by Turing, about computation, you know, of what is computation.

And I never thought about any stuff like that.

I mean, I didn't, I was pretty much a machine.

It's a tinkering mindset, not a philosophical mindset.

It was just exciting to me to be able to control something, but not to say, am I solving a big problem or something like that?

Or is this a step for humankind or anything?

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

You know, like the universal Turing machine

See all Lex Fridman transcripts on Youtube

Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life | Lex Fridman Podcast #219