back to indexDonald Knuth: Programming, Algorithms, Hard Problems & the Game of Life | Lex Fridman Podcast #219
link |
The following is a conversation with Donald Knuth, his second time on this podcast.
link |
Don is a legendary computer scientist, touring award winner, father of algorithm analysis,
link |
author of the art of computer programming, creator of tech that led to late tech,
link |
and one of the kindest and most fascinating human beings I've ever got a chance to talk to.
link |
I wrote him a letter a long time ago, he responded, and the rest, as they say, is history.
link |
We've interacted many times since then, and every time has been joyful and inspiring.
link |
To support this podcast, please check out our sponsors in the description.
link |
This is the Lex Friedman podcast, and here is my conversation with Donald Knuth.
link |
Donald Knuth, your first large scale program, you wrote it in IBM 650 assembler in the summer of 1957.
link |
I wrote it in decimal machine language. I didn't know about assembler until a year later.
link |
But the year 1957, and the program is tic tacto.
link |
Yeah, I might have learned about assembler later that summer, I probably did.
link |
In 1957, hardly anybody had heard of assemblers. You looked at the user manuals,
link |
how would you write a program for this machine? It would say 69, which meant load the distributor,
link |
and then you would give the address of the number you wanted to load into the distributor.
link |
Yesterday, my friend at Doug Spicer at the Computer History Museum sent me a link to
link |
something that just went on YouTube, it was the IBM's Progress Report from 1956,
link |
which is very contemporary with 1957. And in 1956, IBM had donated to Stanford University
link |
an IBM 650, one of the first ones, when they showed a picture of the assembly line for IBM 650s.
link |
And they said, this is number 500 or something coming off the assembly line.
link |
And I had never seen so many IBM 650s. I did in this movie that was on YouTube now.
link |
And it showed the picture from Stanford. They said, we donated one of these to
link |
Stanford, one to MIT, and they mentioned one other college. And in December of 1956,
link |
they donated it to my university case deck. But anyway, they showed a picture then of a class
link |
session where a guy was teaching programming. And on the blackboard, it said 69, 8,000.
link |
I mean, he was teaching them how to write code for this IBM 650, which was in decimal numbers.
link |
So the instructions were 10 decimal digits. You had two digits that said what to do,
link |
four digits to say what to do it to, and four more digits to say where to get your next instruction.
link |
And there's a manual that describes what each of the numbers mean.
link |
If the manual had been well written, I probably never would have gone into computer science,
link |
but it was so badly written, I figured that I must have a talent for it because I'm only a
link |
freshman and I could write a better manual. And so I started working at the computer center
link |
and wrote some manuals then. But this was the way we did it. And my first program then was
link |
June of 1957. The Tic Tac Toe. No, that was the second program. The first program was factoring
link |
a number. So you dial a number on the switches. I mean, you sat at this big main frame and you
link |
turn the dials and set a number. And then it would punch out the factors of that number on cards.
link |
So that's the input is the number? The input was, yeah, the input was a number,
link |
attended a number. And the output was its factors. And I wrote that program.
link |
I still have a copy of it somewhere. How many lines of code do you remember?
link |
Well, yeah, I started out as about 20, but then I kept having me debug it.
link |
And I discovered debugging, of course, when I wrote my first program.
link |
And what does debugging look like on a program with just all numbers?
link |
Well, you sit there and you, I don't remember how I got it into the machine, but I think there
link |
was a way to punch it on cards. So each instruction would be one card. Or maybe I could get seven
link |
instructions on a card, eight instructions, I don't know. But anyway, so I'm sitting there at
link |
console of the machine. I mean, I'm doing this at night when nobody else is around.
link |
Of course. And, and so you have one set of switches where you dial the number I'm inputting,
link |
but there's another switch that, you know, that says, okay, now execute one instruction and show
link |
me what you did, what you did. Or, or you, or you, there was another four switches and say,
link |
stop if you get to those, if you get to that instruction. So, so I can see now go until
link |
you get there again and watch. Okay, so I could watch, you know, it would take that number and
link |
it would divide it by two. And if it's, you know, there's no remainder, then okay, two is a factor.
link |
So, so, so then I work on them. But if, if, if not divisible by two, divide by three, okay,
link |
keep trying until, you know, you're, you're at the end. And you would find a bug if, if
link |
you were just surprised that something weird happened? Well, certainly, I mean, first of all, I
link |
might have, you know, try to divide by one instead of two off by one error that people make all the
link |
time. But maybe I go to the wrong instruction. Maybe I, you know, maybe I left left something
link |
in a register that I shouldn't have done. But the first bugs were pretty, you know, I probably,
link |
on the first night, I was able to, I was able to get the factors of 30, you know, as equal to two,
link |
three and five. Okay. So you're sorry to interrupt. You're, so you're sitting there late at night.
link |
Yeah. So it feels like you spent many years late at night working on a computer. Oh, yeah.
link |
So like, what's that like? So most the world is sleeping. And you have to be there at night
link |
because that's when you get access to the computer. Between my freshman sophomore year,
link |
I didn't need to sleep. I used to do all nighters. When I was in high school, I used to,
link |
I used to do the whole student newspaper every Monday night. I would, you know, I would just
link |
stay up all night and, and it would be done on Tuesday morning. That was because I didn't get
link |
ulcers and stuff like that until later, you know, but, but I don't know if you know Rodney Brooks.
link |
Rod Brooks, of course. Yeah. He told, he told me a story that he really, you're, you know,
link |
he really looked up to you. He was actually afraid of you. Well, vice versa, I must say.
link |
But he tells a story when you were working on tech that they screwed up something with a machine.
link |
I think this might have been MIT, I don't know. And you were waiting for them to fix the machine
link |
so you can get back to work late at night. Oh, that happened all the time. He was really
link |
intimidated. He's like, Dr. Nooth is not happy with this. Oh, that's interesting. But no, no, the,
link |
the, the machine at Stanford AI lab was, was down an awful lot because we, they had, they had many
link |
talented programmers changing the operating system every day. And so operating system was getting
link |
better every day, but it was also crashing. So, so, so I wrote almost the entire manual for tech
link |
during downtime of that machine. But that's another story. Okay. Well, he was saying they,
link |
it's a hardware problem. They, they tried to fix it. They reinserted something and smoke was
link |
everywhere. Oh, wow. Because he was, he was, Oh, that didn't happen as often as the operating system
link |
kind of. But yeah, there was a funny story because you're saying there's this tall Don Knuth that
link |
I look up to and there was pressure to fix the computer. Well, it's funny. Okay. The kind of
link |
things we remember that stick in our memory. Well, okay. Yeah. Well, I can tell you a bunch of
link |
Rodbrook stories too, but let's, let's, let's go back to the 50. So, so I'm debugging this my first
link |
program. And I, I had more bugs in it than number of lines of code. I mean, the number of lines of
link |
code kept growing. And let me explain. So I had to punch the answers on cards. All right. So, so
link |
suppose I'm, suppose I'm factoring the number 30, then I got, then I got to, I got to put two
link |
somewhere on the card, I got to put a three somewhere on the card, I got to put a five
link |
somewhere on the card, right? And, and you know what, my, my first program, I probably screwed up
link |
and, you know, it fell off the edge of the card or something like that. But, but I didn't realize
link |
that there are some tentative numbers that have, that have more than eight factors. And the card
link |
has only 80 columns. And so I need 10 columns for every factor. So my first program didn't take
link |
account for the fact that I would have to punch more than one card. My first program, you know,
link |
just lined the stuff up in memory and then punched the card. But, but after, you know,
link |
by the time I finished, I had to, I had to deal with lots of, lots of things. Also, I, if you,
link |
if you put a large prime number in there, my program might have sat there for 10 minutes. So
link |
650 was pretty slow. And so it would sit there spinning its wheels and you wouldn't know if it
link |
was in a loop or whatever. You said 10 digit as the 10 digits. Yeah. So I think the largest is sort
link |
of 99999999997 or something like that. And that would, you know, that, that would take me a while
link |
for that first point. Anyway, that was my first program. Well, what was your goal with that program?
link |
My goal? Was there something you were hoping to find a large prime, maybe? Or no, the opposite?
link |
No, my goal was to see the lights flashing and understand how this magical machine would be
link |
able to do something that took so long by hand. So what was your second program? My second program
link |
was, was a converted number from, from binary to decimal or something like that. It was much,
link |
much simpler. It didn't have that many bugs in it. My third program was tic tac toe. Yeah.
link |
And it had some, so the, the tic tac toe program is interesting on many levels, but one of them
link |
is that it had some, you can call machine learning in it. That's, yeah, that's right.
link |
I don't know how long it's going to be before the name of our field has changed from computer science
link |
to machine learning. But, but anyway, it, it was my first experience with machine learning.
link |
Okay. So here we had. Yeah. How does the program, well, first of all, what is the problem you were
link |
solving? What is tic tac toe? What are we talking about? And then, right, what, how, how was it
link |
designed? Right. So you got, you got a three by three grid and each, each, each can be in three
link |
states. It can be empty or it can have an X or an O. Right. So three to the ninth is a, well, what
link |
is, how big is it? I should know. But it's 80, 81 times 81 times three. So
link |
anyway, eight is like two to the third. And so that would be, that would be like two to the sixth.
link |
And then, but that'd be 64. Then you have to anyway,
link |
I love how you're doing the calculation. So the three, anyway,
link |
the three comes from the fact that it's either empty and X or an O. Right.
link |
And the 650, what was it, was a machine that had only 2000
link |
10 digit words. You go from 0, 0, 0, 0 to 1, 9, 9, and that's it. And, and each word you have a
link |
10 digit number. So that's not many bits. I mean, I got to have three, in order to have a memory
link |
of every position I've seen, I need three to the ninth bits. Okay. But it was a decimal machine
link |
too. It didn't have bits, but, but it did have, it did have strange instruction where if you had a
link |
10 digit number that, but all the digits were either eight or nine. You'd be eight, nine, nine, eight,
link |
something like that. That would, you can make a test whether it was eight or nine. That was one
link |
of the strange things IBM engineers put into the machine. I have no idea why. Well, hardly ever
link |
used. But anyway, I needed one digit for every, every position I'd seen. Zero meant it was a
link |
bad position. Nine meant it was good position. I think I started out at five or six, you know,
link |
but if you, if you win a game, then you, then you increase the value of that position for you,
link |
but you decrease it for, for your opponent. So, but, but I could, I had that much total memory
link |
for every, every possible position was one digit. And I had a total of 20,000 digits,
link |
which had to, which had to also include my program and all the logic and everything,
link |
including how to, how to ask the user what the moves are and things like this. Okay.
link |
So, so I think I had to work it out. Every, every position in tic, tac, toe is equivalent to,
link |
to roughly eight others because you, you, you can rotate the board, which gives you factor four,
link |
and you can also flip it over. And that's another factor too. So, so I might, you know,
link |
so I might have needed only three to the ninth over eight positions, you know, plus, plus a
link |
little bit. So I had, but anyway, that was, that was a part of the program to, to squeeze it into
link |
this tiny. So you tried to find an efficient representation that took account for that kind
link |
of routine. I had to. Otherwise I couldn't do the learning. So, so, but, but I had three parts to
link |
my tic, tac, toe program. And I called it brain one, brain two, and brain three. So brain one,
link |
just played a, let's see, at random. Okay. It's your turn. Okay. You got to put an X somewhere.
link |
It has to go in an empty space, but that's, that's it. Okay. Choose, choose one and play it. Brain
link |
two had a canned routine. And I think it was, it also, maybe it had, maybe to assume you were the
link |
first player or maybe it allowed you to be first. I think you ought to be either first or second,
link |
but had a canned built in strategy known to be optimum for tic, tac, toe. Before I forget, by the
link |
way, I learned many years later that Charles Babbage had, had planned to, had thought about
link |
programming tic, tac, toe for his, for his dream machine that he, that he would never
link |
able to finish. Wow. So that was the program he thought about. More than a hundred years ago.
link |
Yeah. Yeah. He had, he did that. Okay. And I had, and I had how been influenced by a
link |
demonstration at the, at the Museum of Science and Industry in Chicago. It's like,
link |
it's like Boston's science museum. I think Bell Labs had, had prepared a special exhibit about
link |
telephones and relay technology. And they had a tic, tac, toe playing
link |
machine as part of that exhibit. So that had been one of my, you know,
link |
something I'd seen before I was a freshman in college and, and inspired me to see if I could
link |
write a program for, for, okay. So anyway, I had brain one random, you know,
link |
knowing nothing, brain two, knowing everything. Then brain three was the learning one.
link |
And, and I could, I could play brain one against brain one, brain one against brain two, and so
link |
on. And so you could also play against the user against the live universe. But, but, but so,
link |
so I started going the learning thing. And I said, okay, you know, take two random random people
link |
who just playing tic, tac, toe, knowing nothing. And after about, I forget the number now, but,
link |
but it converged after about 600 games to a safe draw. The way my program learned was actually,
link |
it learned how not to make mistakes because, you know, it didn't try to do anything for winning.
link |
It just tried to say not losing. So that was probably because of the way I, I designed the
link |
learning thing. I could have, you know, had a different reinforcement function that would,
link |
that would reward brilliant play. But anyway, it didn't, and, and, and if I, if I took a novice
link |
against the, you know, the skilled player, it was able to learn how to play a good game.
link |
So that was, and that was really my, but after I finished that, I felt I, I understood programming.
link |
Was there, did you, did a curiosity and interest in learning systems persist for you?
link |
So why, why did you want Brain 3 to learn?
link |
Yeah, I think naturally it's, we're talking about Rod Brooks. He was teaching all kinds of
link |
very small devices to learn stuff. If a leaf drops off of a tree, you know,
link |
he was saying something, well, it learns if there's wind or not. But, but, but I mean,
link |
he pushed that a little bit too far, but he said he could probably train some little
link |
mini bugs to, to scour out dishes if he had enough financial support. I don't know.
link |
So can I, can I ask you about that? Because he also mentioned that during those years,
link |
there was discussion about, inspired by touring about computation, you know, of what is computation.
link |
Yeah. And, yeah, I never thought about any stuff like that. That was, that was way too
link |
philosophical. I mean, I was a, I was a freshman after all. I mean, I didn't, I was pretty much a
link |
machine. So it's almost like, yeah, I got you. It's a tinkering mindset, not a philosophical
link |
mindset. It was just exciting to me to be able to control something, but not, but not to,
link |
but not to say, hmm, am I solving a big problem or something like that? Or is this a step for
link |
humankind or anything? No, no way. When did you first start thinking about computation
link |
in the big sense? You know, like the universal turing machine sense? Well, I mean, I had to pass
link |
an exam. I had to take, I had to take classes on computability when I was a senior. So, you know,
link |
we read this book by Martin Davis and yeah, this is cool stuff. But, you know, I learned about it
link |
because I, you know, I needed to pass the exams, but I didn't, I didn't invent any of that forward
link |
stuff. But I had great fun playing with the machine, you know, I, I wrote program because it was fun
link |
to write programs and get this. I mean, it was like watching miracles happen.
link |
You mentioned in an interview that when reading a program, you can tell when the author of the
link |
program changed. Oh, okay. Well, how the heck can you do that? Like what makes a distinct style
link |
for a programmer, do you think? You know, there's different Hemingway has a style of writing
link |
versus James Joyce or something. Well, those are pretty, yeah, those are pretty easy to imitate,
link |
but it's the same with music and whatever you can. I found, well, during the pandemic, I
link |
spent a lot more time playing the piano and I, and I found something that I'd had. I had it
link |
when I was taking lessons before I was a teenager and it was Yankee Doodle
link |
played in the style of, you know, and you had Beethoven and you had W.C. and Chopin and, you
link |
know, and the last one was Gershwin and, and I played over and over again. I thought it was so
link |
brilliant, but, but it was so easy, but also to appreciate how this, this author, Mario, somebody
link |
or other had, had been able to reverse engineer the styles of those computers. So, but now,
link |
particularly a pure question, I mean, there would be, there, it was, it was pretty obvious in this
link |
program. I was reading, it was, it was a compiler and it had been written by a team at, at Carnegie
link |
Mellon and I have no idea which program was responsible for, but, but you would get to a
link |
part where the guy would just not know how to, how to move things between registers very efficiently
link |
and so, and so everything that could be done in one instruction would take three or something like
link |
that. That would be a pretty obvious change in style, but there were, but there were also,
link |
you know, flashes of brilliance where you could do in one instruction. Normally I used two because,
link |
because you knew enough about the way the machine worked that you could, that you could
link |
accomplish two goals in one step. So, so it was mostly the, the brilliance of the concept more than
link |
the, you know, semicolons and, you know, or the, you know, the use of short sentences versus long
link |
sentences or something like that. So you would see the idea in the code and you could see the,
link |
the different style of thinking expressed in the code. Right. It was, yeah. So it was stylistic.
link |
I mean, I, I could identify authors by their, by the amount of technical aptitude they had,
link |
but not by style in the sense of, of rhythm or something like that. So if you think about Mozart,
link |
Beethoven, Bach, if somebody looked at Don Knuth code, would they be able to tell
link |
that this is a distinct style of thinking going on here? What do you think?
link |
And what, what would be the defining characteristic of the style?
link |
Well, my code now is, it is literate programming. So I'm, it's a combination of English and C
link |
mostly. But, but, but if you just looked at the C part of it, you would also probably notice that I
link |
don't, you know, that I use a lot of global variables that other people don't. And I expand
link |
things in line more than instead of calling. Anyway, I have different subset of C that I use.
link |
Okay. But this, that's a little bit stylistic.
link |
Yeah. But with literate programming, you alternate between English and C or whatever.
link |
And, and by the way, people listening to this should look up literate programming. It's
link |
very interesting concept that you, that you proposed and developed over the years.
link |
Yeah, yeah. I'm, that's the most
link |
significant thing I think to come out of the tech project is that I, I realized that
link |
my programs were to be read by people and not just by computers and that typography could
link |
massively enhance that. And so, I mean, they're just wonderful. If they're going to look it up,
link |
that they should also look up this book by, it's called physically based rendering by
link |
Matt Far and gosh, anyway, it got an Academy Award. But it's, but, but all the,
link |
all the graphic effects you see in movies, you know, are accomplished by algorithms. And this
link |
book is, the whole book is a literate program. It tells you not only how you do all the shading and
link |
and bringing images in that you need for animation and textures and so on, but it also,
link |
you can run the code. And, and, and so I find it an extension of the way I,
link |
of how to teach programming is, is by, by telling a story as part of the program.
link |
So it's, it works as a program, but it's also readable by humans.
link |
Yes. And especially by me, a week later or a year later.
link |
That's a good test. If you yourself understand the code easily a week or a month or a year later.
link |
Yeah. So it, it's, it's the greatest thing since sliced bread programming or literate
link |
literate program. Okay. You heard it here first. Okay. You dodged this question in an interview
link |
I listened to. So let me ask you again here. What makes for a beautiful program?
link |
What makes for a beautiful program? Yeah. What are the characteristics you see,
link |
like you just said, literate programming? What are the characteristics you see in a program
link |
that make you sit back and say, that's pretty good? Well, the reason I didn't answer is because
link |
there are, there are dozens and dozens of answers to that because, because each, each, you can define
link |
beauty, the same person will define beauty a different way from hour to hour. I mean, it
link |
depends on what, on what you're looking for at one level. It's beautiful. Just if it works at all
link |
another level. It's beautiful if it's, if it can be understood easily. It's beautiful if it,
link |
if it's a literate programming, it's beautiful. It makes you laugh. I mean, yeah. I'm actually,
link |
so I'm with you. I think beauty, if it's readable. Readable. Yeah. As if you understand what's going
link |
on and also understand the elegance of thought behind it. And then also, as you said, wit and
link |
humor. I was always, I remember having this conversation, I had this conversation on Stack
link |
Overflow, whether humor is good in comments. And I think it is. Whether humor is good in comments.
link |
Like when you add comments and code, I always thought a little bit of humor is good. It shows
link |
personality. It shows character shows wit and fun and all those kinds of things of the personality
link |
of the programmer. Yeah. Okay. So a couple of days ago, I received a wonderful present from my
link |
former editor. I'd asked Wesley, he's downsizing his house and he found that somebody at the company
link |
had found all of their internal files about the art of computer programming from the 1960s.
link |
And they gave it to him. And then, you know, before throwing, throwing in the garbage. And then,
link |
so he said, oh, yeah, he planned to keep it for posterity, but now he realized that posterity is
link |
too much for him to handle. So he sent it to me. And so I just received this big stack of letters,
link |
some of which I had written to them, but many of which they had written to early guinea pigs who
link |
were telling them whether they should publish or not. And one of the things was in the comments to
link |
volume one, the major reader was Bob Floyd, who is my great coworker in the 60s, died early,
link |
unfortunately. And he commented about the humor in it. And so we had, you know, he ran it by me,
link |
you know, he says, you know, keep this joke in or not, you know, they also sent it out to focus
link |
groups. What do you think about humor in a book about computer programming? What's the conclusion?
link |
And I stated my philosophy. It says, you know, the ideal thing is that it's something where
link |
the reader knows that there's probably a joke here, if you only understood it. And this is a
link |
motivation to understand, to think about it a little bit. But anyway, it's a very delicate
link |
humor. I mean, it's really, each century invents a different kind of humor, too. I mean,
link |
you know, and different cultures have different different kinds of humor.
link |
Yeah, like we talked about Russia a little bit offline, you know, there's dark humor.
link |
And when a country goes to something different,
link |
Right, I don't hear that live and stuff like this. And, you know, and Jack Benny, I mean,
link |
Steve Allen wrote this book about humor, and it was the most boring book. But he was one of my
link |
idols. But it's called The Funny Men or something like that. But yeah, okay, so anyway, I think
link |
it's important to know that this is part of life, and it should be fun and not. And so, you know,
link |
I wrote this organ composition, which is based on the Bible, but I didn't refrain from putting
link |
little jokes in it, also, in the music. It's hidden in the music. It's, it's, it's there. Yeah.
link |
A little humor is okay. Yeah, I mean, not egregious humor. So in this correspondence, you know, there
link |
were, there were things I said, yeah, I really shouldn't have done that. But, but other ones,
link |
I, you know, I insisted on it. And I've got jokes in there that nobody has figured out. In fact,
link |
in volume two, I've got a cryptogram, a message in Cyford. And in order to decipher it, you're
link |
going to have to have to break an RSA key, which is larger than people know how to break. And so,
link |
you know, if computers keep getting faster and faster, then, you know, it might be a hundred
link |
years, but somebody will figure out what this message is, and they will laugh. I mean, I've
link |
got a joke in there. So that one you really have to work for. I don't know if you've heard about this.
link |
Let me explain it. Maybe you'll find it interesting. So OpenAI is a company that does AI work,
link |
and they have this language model. It's a neural network that can generate language pretty well.
link |
But they also, on top of that, develop something called OpenAI Codex. And together with GitHub,
link |
they developed a system called OpenAI Copilot. Let me explain what it does.
link |
There's echoes of literate programming in it. So what you do is you start writing code, and it
link |
completes the code for you. So for example, you start, let's go to your factoring program. You
link |
start, you write in JavaScript and Python and any language that it trained on. You start,
link |
you write the first line and some comments, like what this code does, and it generates the function
link |
for you. And it does an incredibly good job. Like, it's not provably right, but it often
link |
does a really good job of completing the code for you. But how do you know whether it did a good
link |
job or not? You can see a lot of examples where it did a good job. And so it's not a thing that
link |
generates code for you. It starts, it gives you a, so it puts the human in the seat of fixing
link |
issues versus writing from scratch. Do you find that kind of idea at all interesting?
link |
Every year, we're going to be losing more and more control over what machines are doing. And
link |
people are saying, well, when I was a professor at Caltech, in the 60s, we had this guy who
link |
talked a good game. He could give inspiring lectures, and you'd think, well,
link |
thrilling things he was talking about an hour later, you'd say, well, what did he say?
link |
But he really felt that it didn't matter whether computers got the right answer or not,
link |
it just didn't matter whether it made you happy or not. In other words, if your boss paid for it,
link |
then you had a job, you could take care of your wife.
link |
Happiness is more important than truth. Exactly. He didn't believe in truth,
link |
but he was a philosopher. I like it. And somehow you see... We're going that way. I mean,
link |
so many more things are taken over by saying, well, this seems to work. And when there's
link |
competing interests involved, and he decides, understands why the decision is being made,
link |
we realize now that it's bad. But consider what happens. Private attend you down the line.
link |
When things get even more further detached, and each thing is based on something from the previous
link |
year. Yeah. So you start to lose... The more you automate, the more you start to lose track of
link |
some deep human thing. Exponentially. Exponentially. But so that's the dark side. The positive side is
link |
the more you automate, the more you let humans do what humans do best. So maybe programming,
link |
this... Maybe humans should focus on a small part of programming that requires that genius,
link |
the magic of the human mind, and the mess you let the machine generate.
link |
Yeah. I mean, that's the positive. But of course, it does come with the darkness,
link |
of automation. What's better? I'm never going to try to write a book about that.
link |
I'm never going to recommend to any of my students to work for them.
link |
So you're on the side of correctness. I'm on the side of understanding.
link |
Understanding. And I think these things are really marvelous. If what they do is,
link |
all of a sudden, we have a better medical diagnosis or it'll help guide some scientific
link |
experiment or something like this, curing diseases or whatever. But when it affects
link |
people's lives in a serious way... So if you're writing code for... Oh, yeah. This is great.
link |
This will make a slaughter butt. Okay. So I see. So you have to be very careful.
link |
Like right now, it seems like fun and games. It's useful to write a little JavaScript
link |
program that helps you with the website. But like you said, one year passes, two years passes,
link |
five years, and you forget. You start building on top of it. And then all of a sudden,
link |
you have autonomous weapon systems based. Well, we're all dead. It doesn't matter in that sense.
link |
Well, in the end, this whole thing ends anyway. So... But it pays.
link |
There is a heat death of the universe predicted, but I'm trying to postpone that for...
link |
For a little bit. Well, it'd be nice that at the end, as we approach the heat death of
link |
the universe, there's still some kind of consciousness there to appreciate it.
link |
Hopefully human consciousness. I'll settle for 10 to the 10 to the 10 to the 10th year.
link |
There's some finite number, but things like this might be the reason we don't pick up any
link |
signals from extraterrestrial... They don't want anything to do with us.
link |
Oh, because they invented it too.
link |
So you do have a little bit of worry on the existential threats of AI and automation.
link |
So like removing the human from the picture.
link |
Et cetera, yeah. People have more potential to do harm now, by far, than they did 100 years ago.
link |
But are you optimistic about... So humans are good at creating destructive things,
link |
but also humans are good at solving problems. Yeah. I mean, there's half empty and half full,
link |
you know. So... So are we half full or what? I can go... So let me put it this way because
link |
it's the only way I can be optimistic. But think of things that have changed because of civilization.
link |
They don't occur just in nature. So just imagine the room we're in, for example.
link |
Okay. We've got pencils. We've got books. We've got tables. We've got microphones.
link |
We've got clothing. Food. All these things were added. Somebody invented them one by one.
link |
Millions of things that we inherit. Okay. And it's inconceivable that so many millions of
link |
billions of things wouldn't have problems. And we'd get it all right. And each one would have no negative effects and so on.
link |
So it's very amazing that much works as does work. It's incredibly amazing. And actually,
link |
that's the source of my optimism as well, including for artificial intelligence. So we drive over bridges.
link |
We use all kinds of technology. We don't know how it works. And there's millions of brilliant people
link |
involved in building a small part of that. And it doesn't go wrong. And it works. I mean, it works.
link |
And it doesn't go wrong often enough for us to suffer. And we can identify things that aren't
link |
working and try to improve on them. In an often suboptimal way. Oh, absolutely. But it's those.
link |
But the kind of things that I know how to improve require human beings to be rational.
link |
And I'm losing my confidence that human beings are rational. Yeah. Yeah. Now, here you go again
link |
with the worst case, worst case analysis. They may not be rational, but they're
link |
clever and beautiful in their own kind of way. I tend to think that most people
link |
have the desire and the capacity to be good to each other. And love will ultimately win out.
link |
Like if they're given the opportunity, that's where they lean. In the art of computer programming,
link |
you wrote, the real problem is that programmers have spent far too much time worrying about
link |
efficiency in the wrong places. And at the wrong times, premature optimization is the root of all
link |
evil in parentheses, or at least most of it in programming. Can you explain this idea?
link |
What's the wrong time? What is the wrong place for optimization?
link |
So first of all, the word optimization. I started out writing software and optimization was,
link |
I was a compiler writer. So optimization meant making a better translation so that it would run
link |
faster on a machine. So an optimized program is just like, you know, you run a program and you
link |
set the optimization level for the compiler. So that's one word for optimization.
link |
And at that time, I happened to be looking in an unabridged dictionary, for some reason or
link |
other, and I came to word optimize. So what's the meaning of the word optimized? And it says,
link |
to view with optimism. And you look in Webster's dictionary of English language in early 1960s,
link |
that's what optimized me meant. So people started doing cost optimization, all the kinds of things
link |
whole subfields of algorithms and economics and whatever are based on what they call optimization
link |
now. But to me, optimization, when I was saying that, was changing a program to make it more
link |
tuned to the machine. And I found out that when a person writes a program,
link |
he or she tends to think that the parts that were hardest to write are going to be hardest for
link |
the computer to execute. So maybe I have 10 pages of code, but I had to work a week writing this
link |
page. I mentally think that when the computer gets to that page, it's going to slow down.
link |
It's gonna say, oh, I don't understand what I'm doing. I better be more careful. Anyway,
link |
this is, of course, silly, but it's something that we don't know when we write a piece of
link |
code. We don't know whether the computer is actually going to be executing that code very
link |
much. So people had a very poor understanding of what the computer was actually doing. I made
link |
one test where we studied a Fortran compiler, and it was spending more than 80% of its time
link |
reading the comments card. But as a programmer, we were really concerned about how fast it could
link |
take a complicated expression that had lots of levels of parenthesis and convert that into
link |
something. But that was just less than 1%. So if we optimized that, we didn't know what we were
link |
doing. But if we knew that it was spending 80% of its time on the comments card, in 10 minutes,
link |
we could make the compiler run more than twice as fast.
link |
And you could only do that once you've completed the program, and then you empirically study where...
link |
I had some kind of profiling that I knew what was important.
link |
So you don't think this applies generally? I mean, there's something that rings true to this
link |
across all of them. I'm glad that it applied generally, but it was only my good luck. I said
link |
it, but I did, but I said it in a limited context, and I'm glad if it makes people think about
link |
stuff. But it applies in another sense, too. That is, sometimes I will do optimization in a way
link |
that does help the actual running time, but makes the program impossible to change next week,
link |
because I've changed my data structure or something that made it less adaptable.
link |
So one of the great principles of computer science is laziness, or whatever you call it,
link |
late binding. Hold off decisions when you can. And we understand now,
link |
quantitatively, how valuable that is. What do you mean we understand? So you mean...
link |
People have written thesis about how late binding will improve the... I mean,
link |
just in time, manufacturing or whatever, you can defer a decision instead of doing
link |
your advanced planning and say, I'm going to allocate 30% to this and 50%.
link |
So in all kinds of domains, there's an optimality to laziness in many cases.
link |
Decision is not made in advance. So instead, you design in order to be flexible to change with
link |
the way the wind is blowing. Yeah, but the reason that line resonated with a lot of people
link |
is because there's something about the programmer's mind that enjoys optimization.
link |
So it's a constant struggle to balance laziness and late binding with the desire to optimize.
link |
The elegance of a well optimized code is something that's compelling to programming.
link |
Yeah, it's another concept of beauty. Let me ask you a weird question.
link |
So Roger Penrose has talked about computation computers and he proposed that
link |
the way the human mind discovers mathematical ideas is something more than a computer,
link |
that a universal Turing machine cannot do everything that a human mind can do.
link |
Now, this includes discovering mathematical ideas and it also includes,
link |
he's written a book about it, Consciousness. So I don't know if you know, Roger, but
link |
my daughter's kids played with his kids in Oxford.
link |
So do you think there is such a limit to the computer? Do you think consciousness is more
link |
than a computation? Do you think the human mind, the way it thinks, is more than a computation?
link |
I mean, I can say yes or no, but I have no reason.
link |
So you don't find it useful to have an intuition in one way or the other?
link |
Like when you think about algorithms, isn't it useful to think about the limits?
link |
An answerable question, in my opinion, is no better than anybody else.
link |
You think it's unanswerable, so you don't think eventually science will be able to do it.
link |
How many angels can dance on the head of it? I mean, I don't know.
link |
No, but angels aren't...
link |
Anyway, there are lots of things that are beyond, that we can speculate about, but
link |
I don't want somebody to say, oh yeah, can you set this and so he's smart and so that must be,
link |
I mean, I say it's something that we'll never know.
link |
Interesting. Okay, that's a strong statement. I personally think it's something we will know
link |
eventually. Like there's no reason to me why the workings of the human mind are not within the
link |
reach of science. That's absolutely possible, and I'm not denying it. But right now, you don't have
link |
a good intuition. I mean, that's also possible that AI created the universe, the intelligent
link |
design has all been done by an AI. Yes. I mean, all of these things are, but you're asking me to
link |
pronounce on it, and I don't have any expertise. I'm a teacher that passes on knowledge, but I don't
link |
know. The fact that I vote yes or no on... Well, you do have expertise as a human,
link |
and not as a teacher or a scholar of computer science. I mean, that's ultimately the realm
link |
of where the discussion of human thought and consciousness is. I know where Penrose is coming
link |
from. I'm sure he has no proof. He might even thought he proved it, but... No, he doesn't.
link |
He doesn't prove it. He is following intuition. But I mean, you have to ask John McCarthy. I think
link |
we're totally unimpressed by these statements. So you don't think... So even like the touring paper on
link |
the touring tests that starts by asking, can machines think? You don't think these kind of...
link |
So touring doesn't like that question? Yeah. I don't consider it important, let's put it that way,
link |
because it's in the category of things that it would be nice to know, but I think it's beyond
link |
knowledge. And so I'm more interested in knowing about the Riemann hypothesis or something.
link |
So when you say... It's an interesting statement, beyond knowledge. Yeah. I think what you mean
link |
is it's not sufficiently well... It's not even known well enough to be able to formalize it
link |
in order to ask a clear question. Yeah. And so that's why it's beyond knowledge, but that doesn't
link |
mean it's not eventually going to be formalized. Yeah. Maybe consciousness will be understood
link |
someday. But the last time I checked, it was still 200 years away. I haven't been specializing in
link |
this by any means, but I went to lectures about it 20 years ago when I was... There was a symposium
link |
at the American Academy in Cambridge. And it started out by saying, essentially, everything
link |
that's been written about consciousness is hogwash. I tend to... I tend to disagree with
link |
that a little bit. So consciousness for the longest time still is in the realm of philosophy.
link |
So it's just conversations without any basis and understanding. Still, I think once you start
link |
creating artificial intelligence systems that interact with humans and they have personality,
link |
they have identity, you start flirting with the question of consciousness, not from a
link |
philosophical perspective, but from an engineering perspective. And then it starts becoming much more...
link |
Yeah. Don't misunderstand me. I certainly don't disagree with that at all. And even at these
link |
lectures that we had 20 years ago, there were neurologists pointing out that human beings
link |
had actually decided to do something before they were conscious of making that decision.
link |
Yeah. I mean, they could tell that signals were being sent to their arms before they
link |
knew that they were... And things like this are true. And my... Les Valiant has an architecture
link |
for the brain and more recently, Christus Papadimitriou in the Academy of Science Proceedings
link |
a year ago with two other people, but I know Christus very well. And he's got this model of
link |
this architecture by which you could create things that correlate well with experiments
link |
that are done on consciousness. And he actually has a machine language in which you can write code
link |
and test hypotheses. And so we might have a big breakthrough. My personal feeling is that
link |
consciousness... The best model I've heard of, to explain the miracle of consciousness,
link |
is that somehow inside of our brains, we're having a continual survival for the fittest
link |
competition. As I'm speaking to you, all the possible things I might be wanting to say...
link |
Are all in there. And there's like a voting going on.
link |
Yeah, right. And one of them is winning. And that's affecting the next sentence and so on.
link |
And there was this book Machine Intelligence or something.
link |
On intelligence. On intelligence, yeah. Bill Atkinson was a total devotee of that book.
link |
I like whether it's consciousness or something else. I like the storytelling part that it feels like
link |
for us humans, it feels like there's a concrete... It's almost like literary programming.
link |
I don't know what the programming going on in the inside, but I'm getting a nice story here about
link |
what happened. It feels like I'm in control and I'm getting a nice, clear story. But it's also
link |
possible there's a computation going on that's really messy. There's a bunch of different competing
link |
ideas. And in the end, it just kind of generates a story for you, a consistent story for you to
link |
believe. And that makes it all nice. Yeah. And so I prefer to talk about things that I have some
link |
expertise in than things which I'm only on the sideline. So there's a tricky thing. I don't
link |
know if you have any expertise in this. You might be a little bit on the sideline. It'd be interesting
link |
to ask, though, what are your thoughts on cellular automata and the game of life? Have you ever played
link |
with those kind of little games? I think the game of life is wonderful and shows all kind of
link |
stuff about how things can evolve without the creator understanding anything more than the power
link |
of learning in a way. But to me, the most important thing about the game of life is how it focused
link |
for me what it meant to have free will or not. Because the game of life is obviously totally
link |
deterministic. And I find it hard to believe that anybody who's ever had children cannot
link |
believe in free will. On the other hand, this makes it crystal clear. John Conway said,
link |
he wondered whether it was immoral to shut the computer off after he got into a particularly
link |
interesting play of the game of life. Wow. Yeah. So to me, the reason I love the game of life
link |
is exactly, as you said, a clear illustration that from simple initial conditions with simple rules,
link |
you know exactly how the system is operating. It's deterministic. And yet, if you allow yourself
link |
to lose that knowledge a little bit enough to see the bigger organisms that emerge,
link |
and then all of a sudden they seem conscious. They seem not conscious, but living. If the universe
link |
is finite, we're all living in the game of life to slow down. I mean, it sped up a lot.
link |
But do you think technically some of the ideas that you used for analysis of algorithms
link |
can be used to analyze the game of life? Can we make sense of it? Or is it too weird?
link |
Yeah. I mean, I've got a dozen exercises in volume for
link |
Fastical Six that actually work rather well for that purpose.
link |
Bill Gosper came up with the algorithm that allowed Golly to run thousands and thousands
link |
of times faster. You know the website called Golly? It simulates the cellular automata,
link |
a game of life. Yeah, you got to check it out. Can I ask you about John Conway?
link |
Yes. In fact, I'm just reading now the issue of mathematical intelligence,
link |
or that came in last week. It's a whole issue devoted to the remembrance of him.
link |
Did you know him? I slept overnight in his house several times.
link |
Yeah. He recently passed away. Yeah, he died a year ago, May, I think it was of COVID.
link |
What are some memories of him, of his work that stand out for you? On a technical level,
link |
that any of his work inspire you on a personal level? Did he himself inspire you in some way?
link |
Absolutely. All of those things. But let's see, when did I first meet him? I guess I first met
link |
him at Oxford in 1967 when I was… Wow. Okay, that's a long time ago.
link |
Yeah, you were minus 20 years old or something, I don't know, 1967. But there was a conference where…
link |
I think I was speaking about something that
link |
no one has the Knuth Bendix algorithm now, but he gave famous talk about knots.
link |
And I didn't know at the time, but that talk had now the source of thousands and thousands
link |
of papers since then. And he was reported on something that he had done in high school
link |
almost 10 years earlier before this conference, but he never published it. And he climaxed his
link |
talk by building some knots. You have these little plastic things that you could stick
link |
together. It's something like Lego, but easier. And so he made a whole bunch of knots in front
link |
of the audience and so on and then disassembled. So it was a dramatic lecture before he had learned
link |
how to give even more dramatic lectures later. Were you at that lecture?
link |
And I was there because I was at the same conference.
link |
For some reason, I happened to be in Calgary at the same day that he was visiting Calgary.
link |
And it was the spring of 1972, I'm pretty sure. And we had lunch together. And he wrote down
link |
during the lunch on a napkin all of the facts about what he called numbers.
link |
And he covered the napkin with the theorems about his idea of numbers. And I thought it was
link |
incredibly beautiful. And later in 1972, my sabbatical year began and I went to Norway.
link |
And in December of that year, in middle of the night, the thought came to me,
link |
Conway's theory about numbers would be a great thing to teach students how to invent research
link |
and what the joys are of research. And so I said, and I had also read a book in dialogue
link |
by Alfred Renye, kind of a Socratic thing where the two characters were talking to each other
link |
about mathematics. And so at the end, in the morning, I woke up my wife and said,
link |
Jill, I think I want to write a book about Conway's theory. And I'm supposed to be
link |
writing the art of computer programming, doing all this other stuff. But I really want to write
link |
this other book. And so we made this plan. But I said, I thought I could write it in a week.
link |
And we made the plan. And so in January, I rented a room in a hotel in downtown Oslo.
link |
We were in sabbatical in Norway. And I rented the hotel in downtown Oslo and
link |
did nothing else except write Conway's theory. And I changed the name to Surreal Numbers.
link |
And so this book is now published as Surreal Numbers. And we figured out, we'd always wonder
link |
do you like to have a fair enough hotel room? So we figured out that she would visit me twice
link |
during the week. Things like this. We would try to sneak in. This hotel was run by a mission
link |
organization. These ladies were probably very strict. But anyway, so and...
link |
It's a wild week in every way.
link |
But the thing is, I had lost that napkin in which you wrote the theory. But I looked for it, but
link |
couldn't find it. So I tried to recreate from memory what he had told me at that lunch in Calgary.
link |
And as I wrote the book, I was going through exactly what the characters in the book were
link |
supposed to be doing. So I start with the two axioms and start out the whole thing.
link |
Everything is defined, flows from that, but you have to discover why.
link |
And as every mistake that I make as I'm trying to discover it, my characters make too.
link |
And so it's a long, long story. But I worked through this week.
link |
And it was one of the most intense weeks of my life. And I described it in other plays.
link |
But anyway, after six days, I finished it. And on the seventh day, I rested.
link |
And I sent my secretary to type it. It was flowing as I was writing it faster than I
link |
could think almost. But after I finished and tried to write a letter to my secretary,
link |
telling her how to type it, I couldn't write anymore.
link |
You gave it everything. The muse had left me completely.
link |
Can you explain how that week could have happened? That seems like such a magical
link |
week of productivity. I have no idea. But anyway, it was almost as if I was channeling.
link |
So the book was typed. I sent it to Conway. And he said, well, Don, you got the one axiom wrong.
link |
Is there a difference between less than or equal and not greater than?
link |
The opposite of being greater than and less than or equal. But anyway,
link |
technically, it can make a difference when you're developing a logical theory.
link |
And the way I had chosen was harder to do than John's original.
link |
And we visited him at his house in Cambridge. In April, we took a boat actually from Norway
link |
over across the channel and so on and stayed with him for some days.
link |
We talked about all kinds of things he has. He had puzzles that I'd never heard of before.
link |
He had a great way to solve the game of solitaire. Many common interests that he had never written
link |
up. But anyway, then in the summertime, I took another week off and went to a
link |
place in the mountains of Norway and rewrote the book using the correct axiom.
link |
So that was the most intensive connection with Conway.
link |
It started with a napkin.
link |
It started with a napkin. But we would run into each other.
link |
The next really, I was giving lectures in Montreal.
link |
I was giving a series of seven lectures about a topic called stable marriages.
link |
And he arrived in Montreal between my sixth and seventh lecture.
link |
And we met at a party. And I started telling him about the topic I was doing.
link |
And he sat and thought about it. He came up with a beautiful theory to show that the,
link |
I mean, in technical terms, it's that the set of all stable marriages forms a lattice.
link |
And there was a simple way to find the greatest floor bound of two stable
link |
fairings and least upper bound of two stable married. And so I could use it in my lecture
link |
the next day. And he came up with this theorem during the party.
link |
And it's a brilliant, it's a distributive lesson. I mean, it's, you know,
link |
it added greatly to the theory of stable mansion.
link |
So you mentioned your wife, Jill mentioned stable marriage.
link |
Can you tell the story of how you two met?
link |
So we celebrated 60 years of wedded lists last month.
link |
And, and we met because I was dating her roommate. This was my sophomore year,
link |
her freshman year. I was dating her roommate. And I wanted her advice on strategy or something
link |
like this. And anyway, I found I enjoyed her advice better than her. I enjoyed her roommate.
link |
You guys were majoring the same thing?
link |
No, no, no. Because I read something about working on a computer in grad school
link |
on a difficult computer science topic.
link |
So, so she's an artist and I'm, and I'm a geek.
link |
And what was she doing with a computer science book?
link |
All right. I read the, was it the manual that she was reading?
link |
What was she reading?
link |
I wrote the manual that she had had, she had to take a class in computer science.
link |
Okay. And, and so.
link |
No, no, yeah. No, we, you know, we, there were terrible times,
link |
you know, trying to learn certain concept, but I learned art from her.
link |
And so we worked together, you know, occasionally in design projects, but,
link |
but every year we write a Christmas card and, and we each have to
link |
compromise our, our own notions of beauty.
link |
Yes. When did you fall in love with her?
link |
That day that I asked her about her, her roommate.
link |
I mean, no, I, okay. So you're, I don't mind telling these things,
link |
depending on how you far, how far you go, but
link |
the, but, but, but let me, I promise, I promise not to go too far.
link |
Let me tell you this, that I, I never really enjoyed kissing
link |
until I found how she did it.
link |
Is there a secret you can, you can say in terms of stable marriages of how you
link |
stay together so long? The topic, stable marriage, by the way, is not, is a technical term.
link |
Yes. It's a joke, Don.
link |
But two different people will have to learn how to compromise and, and work together and, and,
link |
and you're going to have ups and downs and, and crises and so on.
link |
And so as long as you don't set your expectation on having 24 hours of bliss,
link |
then there's a lot of hope for stability. But if you, if, if you decide that it's,
link |
that, that there's going to be no frustration.
link |
So you're going to have to compromise on your notions of beauty when you write Christmas cards?
link |
Uh, you, uh, you mentioned that Richard Feynman was someone you looked up to.
link |
Probably you've met him in Caltech.
link |
Well, we knew each other.
link |
Yeah, at Caltech for sure.
link |
You are one of the seminal personalities of computer science. He's one for physics.
link |
Have you, have, is there specific things you picked up from him
link |
and by way of inspiration or, uh,
link |
So we used to go to each other's lectures and, and, and, but, but if I saw him sitting in the
link |
front row, I would throw me for a loop actually. And I would, I would miss a few, a few sentences.
link |
What unique story do I have about, I mean, I, I, I often refer to his, his time in Brazil, uh,
link |
where he, um, essentially said they were teaching all the physics students the wrong way. They were
link |
just, they were just learning how to pass exams and not learning any physics. And he said, you
link |
know, if you want me to prove it, you know, here I'll turn to any page of this textbook and, and
link |
I'll tell you what's wrong with this page. And, and he did so. And, and the textbook had been
link |
written by his host and, and it was a big embarrassing incident, but he had previously asked
link |
his host if, if he was supposed to tell the truth. Um, but, but anyway, it epitomizes the way, uh,
link |
uh, uh, education goes wrong, uh, in all kinds of fields, uh, and has to periodically be brought back
link |
from heck, from, from a process of giving credentials to a process of giving knowledge.
link |
That's probably a story that continues through this day in a bunch of places where it's too easy for
link |
uh, educational institutions to fall into credentialism versus, uh, inspirationalism.
link |
I don't know if those are words, but sort of, uh, understanding versus just giving a little, um,
link |
plaque. And, you know, it's, it's pretty much like what we're talking about. If you want the computer to,
link |
if, if you want to be able to believe the answer, computer is, is doing that. One of the things
link |
Bob Floyd showed me in the 60s, there was a, uh, he loved this cartoon. There was a, there were two
link |
guys standing in front of, in those days, a computer was a big thing, you know, and, and,
link |
and the first guy says to the other guy, this machine can do in one second what it would take
link |
a million people to do in a hundred years. And the other guy says, Oh, so how do you know it's right?
link |
Oh, that's a good line. Uh, is there some interesting distinction between physics and
link |
math to you? Have you looked at physics much to like speaking versus your Feynman? So the
link |
difference between the physics community, the physics way of thinking, the physics intuition
link |
versus the computer science, the theoretical computer science, the mathematical sciences.
link |
Do you see that as a gap or are they strongly overlapping?
link |
It's quite different, in my opinion. I started as a physics major and I switched into math.
link |
And probably the reason was that I could, I could get A plus on the physics exam, but I,
link |
but I never had any idea why I would have been able to come up with the problems that were on
link |
those exams. But, but in math, I, I, I knew, you know, why the teacher set those problems,
link |
and I thought of other problems that I could set too. And I believe it's, it's quite a different
link |
mentality. Is it has to do with your philosophy of geek, geekdom?
link |
I mean, some of my computer scientists friends are really good at physics and others are not.
link |
And, and I'm, you know, I'm really good at algebra, but not at geometry.
link |
Talk about different parts of mathematics, you know, it's so different kind of physical, but
link |
physicists think of things in terms of waves. And I can think of things in terms of waves,
link |
but it's like a dog walking on hind legs, if I'm thinking about it.
link |
So you basically, you like to see the world in, in discreet ways, and then
link |
physics is more continuous. Yeah, I'm not sure if Turing would have been a great physicist.
link |
I think it was a pretty good chemist, but I don't know. But, but, but anyway, I see things.
link |
I believe that computer science is largely driven by people who have brains who are good at
link |
resonating with certain kind of, of, of concepts. And like quantum computers, it takes a different
link |
kind of brain. Yeah, that's interesting. Yeah. It's, it's, well, quantum computers is almost
link |
like at the intersection in terms of brain between computer science and physics, because
link |
they involves both at least at this, at this time. But there is like the physicists I've known,
link |
they have incredibly powerful intuition. And, and there's a lot, I mean, statistical mechanics.
link |
So I, I study statistical mechanics and I mean, random processes are related to algorithms in a
link |
lot of, in a lot of ways. But there's lots of different flavors of flavors of physics,
link |
there are different flavors of mathematics as well. But, but the thing is that I don't see, well,
link |
actually, when they talk to physicists, use completely different language than when they're
link |
talking to, when they're writing expository papers. And so I didn't understand quantum
link |
mechanics at all, from reading about it and scientific American. But, but when I read,
link |
you know, how they described it to each other, talking about eigen, eigenvalues and, and various
link |
mathematical terms that, that made sense, then it made sense to me. But, but Hawking said that
link |
every formula you put in a book, you lose half of your readers. And so he didn't put any formulas
link |
in the book. So I couldn't understand his book at all. And you could say you understood it,
link |
but I really, I really didn't. Well, Feynman also spoke in this way. So Feynman,
link |
I think, prided himself on really strong intuition. But at the same time, he was hiding all the,
link |
the really good, the deep computation he was doing. So, so there was one thing that, that
link |
I was never able to, I wish I had more time to work out with him. But I guess I could describe
link |
it for you. There's, there's something that got my name attached to it, called Knuth arrow notation.
link |
But, but it's a notation for very large numbers. And so it, I find out that, that somebody invented
link |
it in 1830s. It's fairly easy to, to understand anyway. So you start with x plus x plus x plus x
link |
n times, and, and, and you can call that x n. So x n is multiplication. Then you take x times x,
link |
times x times x and n times, that gives you exponentiation x to the nth power. So that's
link |
one arrow x. So x n with no arrows is multiplication x, arrow n is x to the nth power.
link |
Yeah. So just to clarify for the, so x times x times x n times is obviously x n.
link |
x plus x plus x n times. Oh yeah. Okay. And then x n, no.
link |
And then multiplications x to the n. And then, and then here the arrow is when you're doing the same
link |
kind of repetitive operation for the exponent. So I, so I put in one arrow and I get x to the
link |
nth power. Now I put in two arrows. And that makes, takes x to the x to the x to the x to the x
link |
n times power. So in other words, if it's two double arrow three, that would be,
link |
that would be two to the two to the two. So that would be two to the fourth power. That
link |
would be 16. Okay. So, so, so that's the double arrow. And now you can do a triple arrow, of
link |
course, and, and so on. And, and I had this, this paper called, well, essentially big numbers.
link |
You know, you try to impress your friend, but by saying a number they never thought of before.
link |
And, and, and I gave a special name for it and designed a font for it that has script k and so
link |
on. But it, but it really is 10. I think like 10 quadruple arrow three or something like that.
link |
And I claimed that that number, if it is so mind boggling that you can't comprehend how large it
link |
is. But anyway, Feynman, I talked to Feynman about this. And he said, oh, let's just, let's just use
link |
double arrow. But instead of taking integers, let's consider complex numbers. So, so, so you
link |
know, you know, I mean, okay, x, x arrow, arrow two, that means x, x, or x, but what about x,
link |
x double arrow to 2.5. Well, that's not too hard to figure out that's interpolate between
link |
those. But what about x double arrow? I or one plus I or some complex number. And, and so he claimed
link |
that that that there was no analytic function that would that would do that would do the job.
link |
But I didn't know how he could claim that that was that wasn't true. And his next question was,
link |
did then have a complex number of arrows?
link |
Yeah, okay. Wow, okay. Okay, so that's that that's Feynman. That's Feynman's. Yeah.
link |
Can you describe what the
link |
Knuth, Morris, Pratt algorithm does? And how did you come to develop it? One of the many things
link |
that you're known for, and has your name attached to it? Yeah, all right. So, it should be actually
link |
Morris Pratt Knuth. But we decided to use alphabetical order when we published the paper. The problem is
link |
something that everybody knows now if they're, if they're using a search engine,
link |
you have a large collection of text, and you want to know if, if the word Knuth appears anywhere in
link |
the text, to say, or, or some, some other word that's less interesting than Knuth. That's the
link |
most interesting word. Morris or something like Morris, right. So we have, we have a large piece
link |
of text, and it's all one long, one dimensional thing, you know, first letter, second letter,
link |
et cetera, et cetera, et cetera. And so the question, you'd like to be able to do this quickly. And the
link |
obvious way is, let's say we're looking for Morris. Okay, so we would, we would go through and
link |
wait till we get to letter M. Then we look at the next word and sure enough, it's an O and then an R.
link |
But then the, well, too bad. The next letter is, is E. So we missed, we missed out on Morris.
link |
And so we go back and start looking for another. Okay. So that's the obvious way to do it. All
link |
right. And, and Jim Morris noticed there was a more clever way to do it. The obvious way would
link |
have started, let's say we, you know, we found that letter M at character position 1000.
link |
Started next at character position 1001. But, but he, but he said, no, look, we already read the O
link |
and the R. And we know that they aren't M's. So we can, we can start, we don't have to read those
link |
over again. All right. So, and this gets pretty tricky when, when the word isn't Morris, but it's
link |
more like abracadabra, where you have patterns that are occurring. Like repeating patterns
link |
in the, at the beginning, at the middle. Right. Right. So, so he worked it out. And he put it
link |
into the system software at Berkeley, I think it was where he was, he was writing some Berkeley
link |
Unix, I think it was some routine I was supposed to find occurrences of patterns in text and, and,
link |
and, but he didn't explain it. And, and so he found out that several months later, somebody had,
link |
had looked at it, didn't look right. And so they ripped it out. So he had this, this algorithm,
link |
but it didn't make it through, you know, because he wasn't understood. Nobody knew about this
link |
particularly. Von Pratt also had independently discovered it a year or two later. I forget
link |
why. I think Von was studying some technical problem about palindromes or something like that.
link |
He wasn't really, it, Von wasn't working on, on text searching, but he was working on a,
link |
on an abstract problem that, that was related. Well, at that time, Steve Cook was a professor at
link |
Berkeley. And it was the greatest mistake that Berkeley CS department made was not to give him
link |
tenure. And so Steve went to, went to Toronto. But, but, but I knew Steve while he was at Berkeley.
link |
And he had come up with a, with a very peculiar theorem about a technical concept called a
link |
stack automaton. And a stack automaton is a machine that, that it can't do everything
link |
that the machine can do, but it can only look at something on at the top of a stack, or it can
link |
put more things on the stack, or, or it can take things off the stack. Like it can't remember
link |
a long string of symbols, but, but it can remember them in reverse order. So, so, so if you tell a
link |
stack automaton ABCDE, it can, it can tell you afterward, EDCBA, you know, it doesn't have any
link |
other memory except, except this one thing that it can see. And, and Steve Cook proved this amazing
link |
thing that says, if a stack automaton can recognize a language, where the strings of the
link |
language are length n, in any amount of time whatsoever, for the stack automaton might use
link |
a zillion steps, a regular computer can recognize that same language in time n log n. So Steve had
link |
a way of transforming a computation that goes on and on and on and on into using different
link |
data structures into something that you can do on a regular computer fast. The stack automaton
link |
goes slow, but, but, but somehow the fact that it can do it at all means that there has to be a
link |
fast way. So I thought this was a pretty, you know, cool theorem. And so I tried it out on, on a problem
link |
where I knew a stack automaton could do it. But I couldn't figure out a fast way to do it on a
link |
regular computer. I thought I was a pretty good programmer. But, but by golly, I couldn't think
link |
of any way to recognize this language efficiently. So I went through Steve Cook's construction.
link |
I filled my blackboard with all the everything that stack automaton did, you know, I wrote down,
link |
and then I tried to see patterns in that. And, and how did he convert that into a computer program
link |
on a regular machine? And finally, I psyched it out. What was what was the thing I was missing
link |
so that I could say, oh, yeah, this is what I should do in my program. And now I have an official
link |
program. And, and so I, I would never have thought about like that if I hadn't had his theorem, which
link |
was purely abstract thing to try to intuit how to use the stack automaton for the string matching
link |
problem. Yeah. So, so, so the problem I had started with was not the string matching problem. But
link |
then I realized that the string matching problem was another thing, which would also be could be
link |
done by a stack automaton. And so when, when I looked at what that told me, then I had a nice
link |
algorithm for this string matching problem. And it told me exactly what I should remember as I'm
link |
as I'm going through the string. And I worked it out. And, and I wrote this little paper called
link |
Automata Theory Can Be Useful. And, and the reason was that it was the first, I mean, I had been
link |
reading all kinds of papers about Automata Theory. But it never taught me it never improved my
link |
programming for everyday problems. It was something that you published in journals and, and, and,
link |
you know, it was it was interesting stuff. But it, but here was a case where I couldn't figure
link |
how to write the program. I had a theorem from Automata Theory. Then I knew how to write the
link |
program. So this was, for me, you know, a change in life, I started to say, maybe I should learn
link |
more about Automata Theory. And, and, and I showed this note to Vaughan Pratt. And he said he that's
link |
simple, similar to something I was working on. And then, and Jim Morris was at Berkeley too,
link |
at the time. Anyway, he, he's had an illustrious career, but I haven't kept track of Jim. But
link |
Vaughan is my colleague at Stanford, and my student later. But this was before Vaughan, Vaughan was
link |
still a graduate student and hadn't come to Stanford yet. So we found out that we'd all been working
link |
on the same thing. So it was our algorithm we each discovered independently. But each of us
link |
had discovered a different, a different part of the elephant, you know, a different aspect of it.
link |
And so we could put our things together with my job to write the paper. How did the elephant spring
link |
to life? Spring to life was because I had drafted this paper, Automata Theory. Oh, can be useful,
link |
which was seen by Vaughan and then by Jim. And then, then, then we combined, because maybe they
link |
had also been thinking of writing something up about it. About specifically a string match.
link |
Specifically the string match and problem in a period.
link |
Let me ask a ridiculous question. Last time we talked, you told me what the most beautiful
link |
algorithm is, actually, for strongly connected graphs. What is the hardest problem, puzzle,
link |
idea in computer science for you personally that you had to work through? Just something that was
link |
just the hardest thing that I've ever been involved with? Yeah. Okay, well, yeah, that's,
link |
I don't know how to answer questions like that. But in this case, it's pretty clear.
link |
Okay, because it's called the birth of the giant component. Okay, so now let me explain that,
link |
because this actually gets into physics too. And it gets into something called Bose Einstein
link |
statistics. But anyway, it's got some interesting stories and it connected with Berkeley again.
link |
So start with the idea of a random graph. Now, this is, here, we just say we have
link |
n points that are totally unconnected. And, and there's no geometry involved. There's no
link |
saying some points are further apart than others. All points are exactly, are exactly alike. And
link |
let's say we have 100 points and we number them from 0 to 99. All right. Now, let's, let's take pi,
link |
the digits of pi, so two at a time. So we had 31, 41, 59, 26, we can go through pi.
link |
And so what, so we take the first two 31, 41, and let's, let's put a connection between 0.31
link |
and 0.41. That's an edge in the graph. So then we take 5926 and make another edge. And the graph
link |
gets bigger, gets more and more connected as we add these things one at a time. Okay,
link |
we start out with n points and we add m edges. Okay. Each edge is completely, we forgot about
link |
edges we had before. We make an edge twice. We make an edge from a point to itself even.
link |
You know, maybe pi is going to have a run of four digits in there. So we're going to,
link |
like, but anyway, we're evolving a graph at random. And a magical thing happens
link |
when the number of edges is like 0.49 and so maybe n is a million and I have,
link |
you know, 490,000 edges. Then it almost all the time, it consists of isolated trees,
link |
not even any loops. It's a very small number of edges so far.
link |
About a little less than half n. But if I had 0.51 edges, so a little more than half n.
link |
So it's, you know, million points, 510,000 edges. Now it probably has
link |
a one component that's much bigger than the others.
link |
And we call that the giant component.
link |
Okay, can you clarify? So can you clarify? First of all, is there a name for this kind of random,
link |
super cool pi random graph? Well, I call it the pi graph. No, no, the pi graph is actually,
link |
my pi graph is based on binary representation of pi, not the decimal representation of pi.
link |
But anyway, let's suppose I was rolling dice instead. So it doesn't have to be pi?
link |
It doesn't have to be any source of, the point is, every step, choose totally at random one of
link |
those endpoints. Choose totally at random another one of the endpoints. Make that an edge.
link |
That's the process. Yeah. So there's nothing magical about pi that you're just giving us.
link |
No, no, I was using pi to sort of saying pi is sort of random that nobody knows a pattern in.
link |
Exactly. Got it. Got it. But it's not, yeah, I could have just as well drawn straws or something.
link |
This was a concept invented by Erdos and Rainey, and they called the evolution of random graphs.
link |
And if you start out with, with a large number and, and you, and you repeat this process,
link |
all of a sudden a big bang happens at one half in, there'll be two points together,
link |
then maybe we'll have, have, have three. And then, you know, then they maybe branch out a
link |
little bit, but, but they'll all be separate until we get to one half in. And we pass one half in,
link |
and all of a sudden there's substance to it that there are, there's a big clump of stuff that's
link |
all joined together. So it's almost like a phase transition of some kind. It's exactly, it, it's
link |
a phase transition, but it's actually, it's a double phase transition. It turns out it, it, it,
link |
it happens. I mean, there's actually two things going on at once at this phase transition, which
link |
which is very remarkable about it. Okay. So, so a lot of the most important algorithms are,
link |
are based on random processes. And so I wanted to, you know, I want to understand random processes
link |
now. And so there are data structures that sort of grow this way. Okay. So, so, so Dick Carp,
link |
one of the leading experts on random randomized algorithms, had his students working, looking
link |
at this at Berkeley. And we heard a rumor that the students had found something interesting
link |
happening. The students are generating this, or similarly, this random evolution of graphs.
link |
And they're taking snapshots that were so often, take a look at what the graph is.
link |
And the rumor was that every time they looked, that there was only one component that had loops in
link |
it, almost always, they do a million experiments. And only three or four times did they ever,
link |
ever happen to see a loop at this, at this point. I mean, no, more than one component with a loop.
link |
So they watch until the graph gets completely full. So it starts out totally empty and gets
link |
more and more, more and more edges all the time. And so, okay, certainly a loop comes along once.
link |
But, but now all the loops stay somehow joined to that one. They're never, there never were two
link |
guys with loops. Wow, interesting. In these experiments. Okay. So anyway, this was almost
link |
almost always, certainly not always. But, but, but with very high probability, this seemed to be true.
link |
So we heard about this rumor as Stanford. And we said, if that's true, then must, you know,
link |
a lot more must also be true. So there's a whole, there's a whole theory out there waiting to be
link |
discovered that we haven't ever thought about. So let's take a look at it. And so we look closer
link |
and we find out, no, it actually, it's not true. But, but in fact, it's almost true.
link |
Namely, there's a very short interval of time when it's true. And if you don't happen to look at it,
link |
during that short interval of time, then you miss it. So the, in other words, there'll be a period
link |
where there are two or three components have loops, but they joined together pretty soon.
link |
Okay. So if you don't have a real fast shutter speed, you're going to miss, you're going to miss
link |
that instant. So separate loops don't exist for long. That's it. Yeah. You know, I started looking
link |
at this to make it quantitative. And the basic problem was to slow down the big bang so that I
link |
could watch it happening. Yeah. I think I can explain it actually in fairly elementary terms,
link |
even without writing a formula. Let's try. Like Hawking would do. And, and, and so
link |
let's, let's watch the evolution. And at first, these edges are coming along and they're just
link |
making things without loops, which we call trees. Okay. So then all of a sudden, the loop first
link |
appears. So at that point, I have one component that has a loop. All right. Now, now I say that
link |
the complexity of a component is the number of edges minus the number of vertices. So if I have a
link |
loop, I have like a loop of length five has five edges and five vertices. Or I could put a tail on
link |
that. And that would be another edge, another vertex. Zero, one, two complexity kind of thing.
link |
So if the, if the complexity is zero, we have one, one loop, I call it a cycle or I call it
link |
cyclic components. So cyclic component looks like a wheel to which you attach fibers or trees.
link |
They go branchy, but there's no more loops. There's only one loop and everything else
link |
feeds into that loop. Okay. And that has complexity zero. But, but a tree itself has complexity
link |
minus one because it has, you know, like, like, like it might have 10 vertices and nine edges to
link |
tie the time together. So nine minus 10 is minus one. So, so complexity minus one is a tree.
link |
It's got to be connected. That's what I mean by a component. It's got to be connected. So,
link |
so, so if, if I have 10 things connected, I have to have nine edges.
link |
Can you clarify why when complexity goes, can go above zero? I'm a little, guess what?
link |
Right. So the complexity plus one is the number of loops. So if complexity is zero, I have one loop.
link |
And if, if complexity is one, that means I have one more edge than I have verdicts.
link |
So I might have like 11 edges and 10 vertices. So it turns, we call that a bicycle because it,
link |
it, it's got two loops and it's got to have two loops in it.
link |
Well, why can't it be trees just going off of the loop?
link |
That I would need more edges than I. Oh, right. Right. Okay. I got you. So, so every time I get
link |
another loop, I get another excess of edges over vertices. I got you. Okay. So in other words,
link |
we start out and after I have one loop, I have one component that has a cycle in it.
link |
And now the next step, according to the rumor would be that at the next step, I would have
link |
a bicycle in the evolution of almost all graphs. It would go from cycle to bicycle.
link |
But in fact, there's a certain probability it goes from cycle to two, you know,
link |
two different cycles. All right. And I worked out the probability was something like five out of
link |
24. It was pretty high. It was substantial. Yeah. But still,
link |
soon they're going to merge together almost. Okay. So that's so cool. But, but then it splits again
link |
after you have either, either two or one, one. The next step is you either have three,
link |
or you have two, one, or you have one, one, one. Okay. And so I worked out the probability
link |
for, for those transitions. And I worked it out up to, up to the first five transitions.
link |
And I had these, I had these strange numbers, five, 24. And I stayed up all night and about three
link |
a.m. I had the numbers computed and I looked at them and here were the denominator was something like
link |
223023. So, so the probability was something over 23023.
link |
I don't know how you worked that out, but I had a formula that, you know, I could calculate the
link |
probability. Yeah. And, and I could find the limiting probability as n goes to infinity. And,
link |
and it turned out to be this number, but the denominator was 23. And I, and I looked at the
link |
denominator, I said, wait a minute, this number factors, because 1001 is equal to seven times
link |
11 times 13. I had learned that in my first computer program. So, so, so, so, so, so 23023 is
link |
seven times 11 times 13 times 23. That's not a random number. There has to be a reason why
link |
those small primes appear in the denominator. But my think, so all of a sudden that suggested
link |
another way of looking at the problem where small prime factors would occur. So, so what would that
link |
be? So that said, oh, yeah, let me take the logarithm of this formula. And, and sure enough,
link |
it's going to simplify. And it happened. So, and I wouldn't have noticed it except for this
link |
factorization. Okay, so I go to bed and I say, oh, okay, this is this looks like I'm flowing down
link |
the Big Bang, I can figure out what's going on here. And the next day, turn out Bill Gates comes
link |
to Stanford to visit. They're trying to sell him on donating money for a new computer science building.
link |
Sure. And, and, and I simply gave me an appointment to talk to Bill and I, and I wrote down on the
link |
blackboard this, this evolutionary diagram, you know, going from one to two, five, 24 and all
link |
this business. Yeah. And I wrote it down. And anyway, at the end of the day, the he was discussing
link |
people with the with the development office. And you said, boy, I was really impressed with
link |
the what Professor Knuth said about this giant component. And, and so, you know, I love this
link |
story because it shows that theoretical computer science is is really worthwhile. You know,
link |
does Bill, have you ever talked to Bill Gates about it? Since then?
link |
Yeah. That's a cool, that's a cool little moment in history. But anyway, he happened to visit on
link |
exactly the day after I had found this pattern. And that allowed me to crack the problem. So,
link |
so that I could develop the theory, the theory some more and understand what's happening in the big
link |
but because I could I could now write down explicit formulas for stuff. And so it would,
link |
you know, you work not only the first few steps, but also the study the whole process. And, and I
link |
worked further and further. And I with two authors, coauthors, and we finally figured out
link |
that the probability that the rumor was true. In other words, look at the evolution of
link |
of a random graph going from zero zero to complete and say what's the probability that
link |
at every point in time, there was only one component with a cycle. We started with this
link |
rumor saying there's only one site, there's only one component with a cycle. And so the rumor was
link |
it's 100%. The rumor was that was 100%. And it turned out the actual numbers is like 87%.
link |
I should remember the number, but I don't, but I don't have it with me. But, but anyway,
link |
but, but the, but the number, it turned out to be like 12 over pi squared or eight over pi. Anyway,
link |
it was a nice, it related to pi. Yeah. And we could never have done that with it. But so that's
link |
the hardest problem I ever saw in my life was to prove that this probability is you was proven
link |
the probability was proven. Yeah, I was able to prove this that this and this shed shed light
link |
on a whole bunch of other things about random graphs that that was sort of the the major
link |
thing we were after. That's super cool. What was the connection to physics that you mentioned?
link |
Well, Bose Einstein statistics is the study of how molecules bond together
link |
without geometry, without this. You created the tech type setting system and released it as open
link |
source. Just on that little aspect, why did you release it as open source? What is your vision
link |
for open source? No, okay, well, that the word open source didn't exist at that time. But we,
link |
but I didn't want proprietary rights over it. Because I saw how proprietary rights were holding
link |
things back. In the late fifties, people at IBM developed the language called Fortran. They could
link |
have kept it proprietary. They could have said only IBM can use this language. Everybody else has to,
link |
but but they didn't. They said anybody who can write, who can translate Fortran into the
link |
into the language of their machines is allowed to make Fortran capacitors to.
link |
On the other hand, in the topography industry, I had seen a lot of languages that were developed
link |
for composing pages. And each manufacturer had his own language for composing pages.
link |
And that was holding everything back because people were tied to a particular manufacturer.
link |
And then a new equipment is invented a year later. But printing, printing machines, they have to
link |
expect to amortize the cost over 20, 30 years. So you didn't want that for tech?
link |
I didn't need the income. I already I already had a good job. And, you know, my books were
link |
people were buying enough books that I that it would bring me plenty of supplemental income
link |
for everything my kids needed for education, whatever. So there was no reason for me to try
link |
to maximize income any further. Income is sort of a threshold function. If you don't have,
link |
if you don't have enough, you're starving. But if you get over the threshold, then you start
link |
thinking about philanthropy or else, or you're trying to take it with you. But
link |
but anyway, there's a I had my income was over the threshold. So so I didn't need to keep it.
link |
And so I specifically could see the advantage of of making it open for everybody.
link |
Do you think most software should be open?
link |
So I think that people should charge for non trivial software, but not for trivial software.
link |
Yeah, you give an example of, I think, Adobe Photoshop versus GIMP on Linux,
link |
as Photoshop has value, which so it's definitely worth paying, paying for all the stuff. I mean,
link |
I mean, well, they keep adding, adding stuff that my wife and I don't care about. But
link |
somebody I mean, but I mean, but they have built in a fantastic
link |
undo feature, for example, in Photoshop, where where you you can go through a
link |
sequence of 1000 complicated steps on graphics, and it can take you back anywhere in that sequence.
link |
Yeah, that's a long history with really beautiful algorithm. I mean, yeah, it's it's
link |
Oh, that's interesting. I didn't think about what algorithm it must be some kind of efficient
link |
representation. Really? Yeah, no. I mean, there's a lot of really subtle Nobel Prize class
link |
creation of intellectual property in in there. And
link |
and with patents, you get a limited time to
link |
I mean, eventually, the idea of patents is that you publish so that it's not secret. It's not a
link |
trade secret. That said, you you've said that I currently use Ubuntu Linux on a standalone
link |
laptop. It has no internet connection. I occasionally carry flash memory drives between the machine
link |
and the Macs that I use for network surfing and graphics. But I trust my family jewels only to
link |
Linux. Why do you love Linux? The version of Linux that I use is stable. Actually,
link |
I'm going to have to upgrade one of these days, but to a newer version of Ubuntu. Yeah, I'll stick
link |
with Ubuntu. But but right now I'm running something that doesn't support a lot of the new
link |
software. It's the last stable. I don't remember the number like 14. Anyway, it's quite and I'm
link |
going to get a new computer. I'm getting new solid state memory instead of a hard disk.
link |
Yeah, the basics. Well, let me ask you, thinking on the topic of tech,
link |
when thinking about beautiful typography, what is your favorite letter, number or symbol?
link |
I know, I know. Ridiculous question. But is there some
link |
Let me show you. Or look at the last page. The very end of the index.
link |
What is that? There's a book by Dr. Seuss called On Beyond Zebra, and he gave a name to that.
link |
Did you say Dr. Seuss gave a name to that? Dr. Seuss. This is SEUSSE. He wrote children's books
link |
in the 50s, 40s and 50s. Wait, are you talking about Cat in the Hat?
link |
Cat in the Hat, yeah. That's it, yeah. On Beyond Zebra did it get to Soviet Union.
link |
No, Dr. Seuss did not come to the Soviet Union, but since you... Oh, actually, I think he did
link |
actually a little bit when we're... Maybe Cat in the Hat or Green Eggs and Ham, I think was used
link |
to learn English. So I think it made it in that way. Okay, I didn't like those as much as Bartholomew
link |
Cubbins, but I used to know Bartholomew Cubbins by heart when I was young. So what the heck is
link |
this symbol we're looking at? There's so much going on. He has a name for it at the end of his book
link |
on Beyond Zebra. Who made it? He did. He did. So there's... It looks like a bunch of vines.
link |
Is that symbol of existence? By the way, he made a movie in the early 50s. I don't remember the
link |
name of the movie. Now you can probably find it easily enough, but it features dozens and dozens
link |
of pianos all playing together at the same time. But all the scenery is sort of based on the kind
link |
of artwork that was in his books and the fantasy based of Seuss land. I saw the movie only once
link |
or twice, but it's quite... I'd like to see it again. That's really fascinating that you gave
link |
them. They gave him a shout out here. Okay. Is there some elegant basic symbol that you're attracted
link |
to? Something that gives you pleasure? Something used a lot? Pie? Pie, of course. I try to use pie
link |
as often as I can when I need a random example because it doesn't have any
link |
known characters. So for instance, I don't have it here to show you, but do you know the game
link |
called Masiu, M.A.S.Y.U.? No. It's a great recreation. I mean, Sudoku is easier to understand,
link |
but Masiu is more addictive. You have black and white stones like on a go board, and you have
link |
to draw a path that goes straight through a white stone and makes the right angle turn at the black
link |
stone. And it turns out to be a really nice puzzle because it doesn't involve numbers,
link |
which is visual, but it's really pleasant to play with. So I wanted to use it as an example in
link |
Art of Computer Programming, and I have exercised on how to design cool Masiu puzzles.
link |
You can find it on Wikipedia, certainly as an example, M.A.S.Y.U. And so I decided I would
link |
take Pi, the actual image of it, and I had pixels, and I would put a stone wherever it belongs in the
link |
letter Pi, in the Greek letter Pi. But the problem was find a way to make some of the stones white,
link |
some of the stones black, so that there's a unique solution to the Masiu puzzle.
link |
That was a good test case for my algorithm on how to design Masiu puzzles, because I
link |
insisted in advance that the stones had to be placed in exactly the positions that make the
link |
letter Pi, make a few letter Pi. That's cool. And it turned out there was a unique way to do that.
link |
And so Pi is a source of examples where I can prove that I'm starting with something that
link |
isn't canned. And most recently, I was writing about something called Graceful Graphs. Graceful
link |
Graphs is the following. You have a graph that has M edges to it, and you attach numbers to every
link |
vertex in the following way. So every time you have an edge between vertices, you take the
link |
difference between those numbers. And that difference has got to be, I'll tell you what edge
link |
it is. So one edge, two numbers will be one apart. There'll be another edge where the numbers are
link |
two apart. And so it's a great computer problem. Can you find a graceful way to label a graph?
link |
So I started with a graph that I use for an organic graph, not a mathematically symmetric
link |
graph or anything. And I take 49 states of the United States, the edges go from one state to
link |
a next state. So for example, California, be next to Oregon, Nevada, Arizona. And I include
link |
District of Columbia. So I have 49. I can't get Alaska and Hawaii in there because they don't
link |
touch. You have to be able to drive from one to the other. So is there a graceful labeling
link |
of the United States? Each state gets a number. And then if California is number 30 and Oregon
link |
is number 11, that edge is going to be number 19. The difference between those, okay? So is there
link |
a way to do this for all the states? And so I was thinking of having a contest
link |
for people to get it as graceful as they could. But my friend, Tom Rukiki, actually solved the
link |
problem by proving that. I mean, I was able to get it down within seven or something like that.
link |
He was able to get a perfect solution. The actual solution or to prove that a solution exists?
link |
More precisely, I had figured out a way to put labels on so that all the edges were labels
link |
somewhere between one and 117. But there were some gaps in theirs. Because I should really
link |
have gone from one to 105 or whatever the number is. So I gave myself a lot of slack. He did it
link |
without any slack whatsoever, a perfect graceful labeling. And so I called out the contest
link |
because the problem is already solved and too easy in a sense because Tom was able to do it in an
link |
afternoon. Sorry, he gave the algorithm or for this particular? For the United States.
link |
For the United States. This problem is incredibly hard. I mean,
link |
for the general. But it's like coloring. But it was very lucky that we worked for the United
link |
States, I think. But the theory is still very incomplete. But anyway, then Tom came back
link |
a couple of days later and he had been able to not only find a graceful labeling, but the label
link |
of Washington was 31. The label of Idaho was 41, following the digits of Pi. Going across the
link |
topic of the United States, he has the digits of Pi perfectly.
link |
Did he do it on purpose? He was able to still get a graceful labeling with that extra thing.
link |
What? Wow. It's a miracle. Okay. But I like to use Pi in my book, you see.
link |
All roads lead to Pi. Somehow often hidden in the middle of the most difficult problems.
link |
Can I ask you about productivity? Productivity. Yeah. You said that, quote,
link |
my scheduling principle is to do the thing I hate most on my to do list. By weeks end,
link |
I'm very happy. Can you explain this process to a productive life? Oh, I see. Well,
link |
but all the time I'm working on what I want, what I don't want to do. But still,
link |
I'm glad to have all those unpleasant tasks finished. Yes. Is that something you would advise
link |
to others? Well, yeah, I don't know how to say it. During the pandemic, I feel my productivity
link |
actually went down by half because I have to communicate by writing, which is slow. I don't
link |
like to send out a bad sentence. So I go through and reread what I've written and edit and fix it.
link |
So everything takes a lot longer when I'm communicating by text messages instead of just
link |
together with somebody in a room. And it's also slower because the libraries are closed and stuff.
link |
But there's another thing about scheduling that I learned from my mother that I should probably
link |
tell you. And that is different from what people in robotics feel do, which is called planning.
link |
So she had this principle that was see something that needs to be done and do it.
link |
Instead of saying, I'm going to do this first and do this first, just,
link |
just do it. Oh, yeah, pick this up. But at any one moment, there's a set of tasks
link |
that you can do. And you're saying a good heuristic is to do the one you want to do least.
link |
Right. The one I haven't got any good reasons. I'll never be able to do it any better than I
link |
am now. There are some things that I know if I do something else first, I'll be able to do that one
link |
better. But there's some that are going to be harder because I've forgotten some of the
link |
groundwork that went into it or something like that. So I just finished a pretty tough part of
link |
the book. And so now I'm doing the parts that are more fun. But the other thing is,
link |
as I'm writing the book, of course, I want the reader to think that I'm happy all the time I'm
link |
writing the book. It's upbeat. I can have humor. I can say, this is cool. Well, this, I have to
link |
disguise the fact that it was painful in any way to come up. The road to that excitement is painful.
link |
Yeah. It's laden with pain. Okay. Is there, you've given some advice to people before,
link |
but can you? You give me too much credit. But anyway, this is my turn to say things that I
link |
believe, but I want to preface it by saying, I also believe that other people do a lot of these
link |
things much better than I do. So I can only tell you my side of it. So can I ask you to give advice
link |
to young people today, to high school students, to college students, whether they're geeks
link |
or the other kind about how to live a life that they can be proud of, how to have a successful
link |
career, how to have a successful life? It's always the same as I've said before, I guess,
link |
not to do something because it's trendy, but it's something that you personally feel that you were
link |
called to do rather than somebody else expects you to do. How do you know you're called to do
link |
something? You try it and it works or it doesn't work. I mean, you learn about yourself. Life is
link |
a binary search. You try something and you find out, oh yeah, I have a background that helped me
link |
with this, or maybe I could do this if I worked a little bit harder, but you try something else
link |
and you say, well, I have really no intuition for this and it looks like it doesn't have my name
link |
on it. Was there advice along the way that you got about what you should and shouldn't work on,
link |
or do you just try to listen to yourself? Yeah, I probably overreacted another way. When
link |
something, when I see everybody else going some way, I probably say, hmm, too much competition.
link |
But mostly I played with things that were interesting to me and then later on I found,
link |
oh, actually, the most important thing I learned was how to be interested in almost anything.
link |
Yeah. I mean, not to be bored. It makes me very sad when I see kids talking to each other and they
link |
say that was boring. And to me, a person should feel upset if he had to admit that he wasn't
link |
able to find something interesting. I haven't learned how to enjoy life. I have to have somebody
link |
entertain me instead of... That's really interesting. It is a skill. David Foster Wallace,
link |
I really like the thing he says about this, which is the key to life is to be unboreable.
link |
And I do really like you saying that it's a skill because I think that's a really good advice,
link |
which is if you find something boring, that's not... I don't believe it's because
link |
it's boring. It's because you haven't developed a skill. I have learned how to find the beauty
link |
and how to find the fun in it. Yeah, that's a really good point. Sometimes it's more difficult
link |
than others to do this. I mean, during the COVID, lots of days when I never saw another human being,
link |
but I still find other ways to... It still was a pretty fun time. Yeah. I came earlier,
link |
I came a few minutes early today and I walked around Foster City. I didn't know what was going
link |
on in Foster City. I saw some beautiful flowers at the nursery at Home Depot a few blocks away.
link |
Life is amazing. It's full of amazing things like this. Yeah, sometimes I'll sit there and
link |
just stare at a tree. Nature is beautiful. Let me ask you the big ridiculous question. I don't
link |
think I asked you last time. I have to ask this time in case you have a good answer. What is the
link |
meaning of life? Our existence here on earth, the whole thing. No, you can't. I will not allow you
link |
to try to escape the answer in this question. You have to answer definitively because there's
link |
surely, surely, Don Knuth. There must be an answer. What is the answer? Is it 42?
link |
Yeah, I don't think it's a numerical. That's the answer. That was in Zen and...
link |
All right, so anyway, it's only for me, but I personally
link |
think of my belief that God exists, although I have no idea what that means,
link |
but I believe that there is something beyond human capabilities. It might be some AI,
link |
but whatever it is, but I do believe that there is something that goes beyond the realm of human
link |
understanding, but that I can try to learn more about how to resonate with whatever that
link |
being would like me to do. So you think you can have occasional glimpses of that being?
link |
I strive for that. Not that I ever think I'm going to get close to it, but it's not for me.
link |
It's saying, what should I do that that being wants me to do? I'm trying to ask,
link |
I mean, does that being want me to be talking to Lex Fridman right now? And I said, yes.
link |
Okay, but... Thank you. Well, thank you.
link |
What I'm trying to say is, I'm not trying to say, of all the strategies I could choose or
link |
something, which one... I try to do it not strategically, but I try to imagine that I'm
link |
following somebody's wishes. Even though you're not smart enough to... To know what they are.
link |
Yeah. It's a funny little dance. Well, I mean, this AI or whatever is probably
link |
is smart enough to help to give me clues. And do you make the whole journey from clue to clue?
link |
A fun one. Yeah. I mean, as so many people have said, it's the journey, not the destination.
link |
And people live through crises, help each other. Things come up, history repeats itself.
link |
You try to say, in the world today, is there any government that's working? I read history. I know
link |
that things were... There were a lot worse in many ways. There's a lot of bad things all the time.
link |
And I read about... I look at things and people had good ideas and they were working
link |
on great projects. And then I know that it didn't succeed, though, in the end.
link |
But the new insight I've gotten, actually, in that way was... I was reading...
link |
What book was I reading recently? It was by Ken Follett, and it was called The Man from St.
link |
Petersburg. But it was talking about the prequel to World War I. And Winston Churchill, according
link |
to this book, sees that Germany has been spending all its gold reserves building up a huge military.
link |
And there's no question that if Germany would attack England, that England would be wiped out.
link |
So he wants Russia to help to attack Germany from the other side, because Germany doesn't
link |
have enough of an army to be fighting two wars at one. Okay. Now, then there's an anarchist in Russia
link |
who sees that wars are something that leaders start, but actually people get killed.
link |
And so he wants to stop any alliance between England and Russia, because that would mean that
link |
thousands and thousands of people of Russia would be killed that wouldn't be otherwise killed.
link |
All right. And so his life's goal is to assassinate a Russian prince who's visiting England,
link |
because that will mean the Tsar will not form the alliance. All right. So we have this
link |
question about what should the government do? Should it actually do something that will lead to,
link |
is the war inevitable, or is there a way to have people? And it struck me that if I were
link |
in a position of responsibility for people's lives, in most cases, I wouldn't have any confidence
link |
that any of my decisions were good, that these questions are too hard, probably for any human
link |
being, but certainly for me. Well, I think coupling the not being sure that the decisions are right,
link |
so that that's actually a really good thing, coupled with the fact that you do have to make a
link |
decision and carry the burden of that. And ultimately, I have faith in human beings,
link |
in the great leaders to arise and help build a better world. I mean, that's the hope of democracy.
link |
Yeah. And let's hope that we can enhance their abilities with algorithms.
link |
Well put, Don. It's such a huge honor. You've been an inspiration to me and to millions for such
link |
a long time. Thank you for spending your really valuable time with me. Once again, it's a huge
link |
honor. I really enjoyed this conversation. Thanks for listening to this conversation with Donald
link |
Knuth. To support this podcast, please check out our sponsors in the description. And now,
link |
let me leave you with some words from Don Knuth himself. Science is what we understand well
link |
enough to explain to a computer. Art is everything else we do. Thank you for listening. I hope to
link |
see you next time.