Kind: captions
Language: en
the following is a conversation with
donald knuth one of the greatest and
most impactful computer scientists and
mathematicians ever he's the recipient
of the 1974 Turing award considered the
Nobel Prize of computing he's the author
of the multi-volume work the magnum opus
the art of computer programming he made
several key contributions to the
rigorous analysis of computational
complexity of algorithms including the
popularization of asymptotic notation
that we all affectionately know as the
Big O notation he also created the tech
typesetting system which most computer
scientists physicists mathematicians and
scientists and engineers in general used
to write technical papers and make them
look beautiful I can imagine no better
guest to in 2019 with than Don one of
the kindest most brilliant people in our
field this podcast was recorded many
months ago it's one I avoided because
perhaps counter-intuitively the
conversation meant so much to me if you
can believe it I knew even less about
recording back then so the camera angle
is a bit off I hope that's okay with you
the office space was a bit cramped for
filming but it was a magical space Ordon
does most of his work it meant a lot to
me that he would welcome me into his
home it was quite a journey to get there
as many people know he doesn't check
email so I had to get creative the
effort was worth it I've been doing this
podcast on the side for just over a year
sometimes I had to sacrifice a bit of
sleep but always happy to do it and to
be part of an amazing community of
curious minds thank you for your kind
words support for the interesting
discussions and I look forward to many
more of those in 2020 this is the
artificial intelligence podcast if you
enjoy it subscribe on YouTube give it
five stars an Apple podcast follow on
Spotify support on patreon or simply
connect with me on Twitter at lex
friedman spelled fri d-m am
I recently started doing ads at the end
of the introduction I'll do one or two
minutes after introducing the episode
and never any ads in the middle that
break the flow of the conversation I
hope that works for you and doesn't hurt
the listening experience I provide time
stamps for the start of the conversation
that you can skip to but it helps if you
listen to the ad and support this
podcast by trying out the product the
service being advertised this show is
presented by cash app the number one
finance app in the App Store
I personally use cash app to send money
to friends but you can also use it to
buy sell and deposit Bitcoin in just
seconds cash app also has a new
investing feature you can buy a fraction
of a stock say $1 worth no matter what
the stock price is brokerage services
are provided by cash app investing a
subsidiary of square and member s IBC
I'm excited to be working with cash app
to support one of my favorite
organizations called first best known
for their first robotics and Lego
competitions they educate and inspire
hundreds of thousands of students in
over 110 countries and have a perfect
rating and charity navigator which means
that donated money is used to maximum
effectiveness when you get cash app from
the App Store or Google Play
and use code Lex podcast you'll get ten
dollars in cash up will also donate ten
dollars the first which again is an
organization that I've personally seen
inspire girls and boys to dream of
engineering a better world and now
here's my conversation with Donald Knuth
in 1957 atcase tech you were once
allowed to spend several evenings with a
IBM 650 computer as you've talked about
in the past then you fell in love with
computing then
can you take me back to that moment with
the IBM 650 what was it that grabs you
about that computer so the IBM 650 was
this this machine that
well it didn't fill a room but it it was
it was big and noisy but when I first
saw it it was through a window and there
were just a lot of lights flashing on it
and I was a freshman I had a job with
the statistics group and I was supposed
to punch cards and pour data and then
sort them on another machine but then
they got this new computer came in and I
and it had interesting like you know
lights okay so well but I had it kind of
key to the building so I can you know
like I could get in and look at it and
got a manual for it and and my first
experience was based on the fact that I
could punch cards basically would you a
big thing for though deal with thick but
the is 6:50 was you know big in size but
but incredibly small in power in memory
it had it had 2,000 words of memory and
in a word of memory was 10 decimal
digits plus a sign and it it would do to
add two numbers together you could
probably expect that would take oh say
three milliseconds so that's pretty fast
it's the memories that constraint the
memories the problem that was why it was
three millisecond because it took five
milliseconds for the drum to go around
and you had to wait I don't know five
cycle times if you have an instruction
one position on the drum then it would
be ready to read the data for the
instruction and three notches the drum
is 50 cycles around and you go three
cycles and you can get the data and then
you can go another three cycles and get
and get to next instruction if the
instruction is there otherwise otherwise
you spin until you get to there
play and and we had no random-access
memory whatsoever until my senior year
you see here we got fifty words of
random access memory which were which
were priceless and we would and we would
move stuff up to the up to the random
access memory in 60 word chunks and then
we would start again so it's separating
when to go up there and could you have
predicted the future 60 years later of
computing from then you know in fact the
hardest question I was ever asked was
what could I have predicted in other
words the interviewer asked me she said
you know what about computing has
surprised you you know and immediately I
ran I rattled off a couple dozen things
and inches okay so what didn't surprise
and I was I tried for five minutes to
think of something that I thought I
would have predicted and I and I and I
couldn't but I let me say that this
machine I didn't know well it there
wasn't there wasn't much else in the
world at that time the 650 was the first
machine that was that there were more
than a thousand of ever before that
there were you know there was each
machine there might be a half a dozen
examples maybe my first mass-market
mass-produced the first one yeah done in
quantity and and IBM I didn't sell them
they they rented them but but they they
rented them to universities that at
great you know I had a great deal and
and so that's why a lot of students
learned about computers at that time so
you refer to people including yourself
who gravitate toward a kind of
computational thinking as geeks for at
least I've heard you used that
terminology it true that I think there's
something that happened to me as I was
growing up that made my brain structure
in a certain way that resonates with
with computers so there's the space of
people it's 2% of the population you
empirically estimate that's a prick
it's been proven fairly constant over
most of my career however it might be
different now because kids have
different experiences when they're young
so what does the world look like to a
geek what is what is this aspect of
thinking that is unique to their makes
it yeah that makes a geek this is cuter
the important question in in the 50s
IBM noticed that that there were geeks
and non geeks and so they tried to hire
geeks and they put out as worth papers
saying you know if you play chess come
to Madison Avenue and for an interview
or something like this they were they
were trying for some things so what it
what what is it that I find easy and
other people tend to find harder and and
I think there's two main things one is
this with is ability to jump jump levels
of abstraction so you see something in
the large and you see something in the
small and and can you pass between those
unconsciously so you know that in order
to solve some big problem what you need
to do is add one to a into a certain
register or anything that gets you to
another step and you can and we and
below the yeah I mean I don't go down to
the electron level but I knew what those
milliseconds were what the drum was like
on the 650 I knew how I was gonna factor
her number or or find a root of an
equation or something be alavés because
of what was doing and and as I'm
debugging I'm going through you know did
I make a key punch err did I did I write
the wrong instruction do I have the
wrong wrong thing in a register and each
level at each level it is different and
so this idea of being able to see
something at all at lots of levels and
fluently go between them it seems to me
to be more pronounced much more
pronounced in in the people that
with computers like I got so in my books
I also don't stick after the high level
but but i but i mix low level stuff with
high level and this means that some
people think you know that I that I
should write better books and it's
probably true but but other people say
well but that's if you think like like
that then that's the way to train
yourself like to keep mixing the levels
and and learn more and more how to jump
between so that that's the one thing the
other the other thing is that it's more
of a talent it to be able to deal with
non-uniformity where there's case one
case two case three instead of instead
of having one or two rules that govern
everything so if so it doesn't bother me
if I need like an algorithm has ten
steps to it you know each step is does
something else that doesn't bother me
but a lot of a lot of pure mathematics
is based on one or two rules which which
are universal and and and so this means
that people like me sometimes work with
systems that are more complicated than
necessary because it doesn't bother us
that we don't that we didn't figure out
the simple rule and you mentioned that
while Jacobi boule Abel and all the
mathematicians in 19th century may have
had symptoms of geek the first hundred
percent legit geek was touring Alan
Torrie I I think he had yeah a lot more
of this quality than anyone could from
reading the kind of stuff he didn't so
hot as touring what influence has
touring had on you well well your way
and so I didn't know that aspect of him
until after I graduated some years I it
has undergraduate we had a class that
talked about computability theory and
Turing machines and and that was all it
sounded like a very specific kind of
purely theoretical approach to stuff
so when how old was I when I when I
learned that he thought he had you know
designed when she and that he wrote the
you know you wrote a wonderful manual
for for Manchester machines and and he
invented all the subroutines and and and
he was a real hacker that that he had
his hands dirty
I thought for many years that he had
only done purely formal work as I
started reading his own publications I
could yeah you know I could feel this
kinship and and of course he had a lot
of peculiarities like he wrote numbers
backwards because I mean left to right
to the right to left because that's the
that's it was easier for computers to
process him that way what do you mean
left to right he would write PI as you
know nine five one four point three I
mean okay right forget it for one point
three on the blackboard I mean when he
he we had trained himself to to do that
because the computers he was working
with I worked that way inside trained
himself to think like a computer well
there you go that's nuts geek thinking
you've practiced some of the most
elegant formalism in computer science
and yet you're the creator of a concept
like literate programming which seems to
move closer to natural language type of
description of programming yep yeah
absolutely so how do you see those two
as conflicting as the formalism of
theory and the idea of literate
programming so there we are in a non
uniform system well I don't think one
one-size-fits-all and I don't and I
don't think all truth lies in one in one
kind of expertise and so somehow in a
way you'd say my what my life is a
convex combination of English and
mathematics and you're okay with that
and not only that I think thriving I
wish you know I want my kids to be that
way I want cetera not used left-brain
right-brain at the same time you got a
lot more done that's that was part of
the and I've heard that you didn't
really read for pleasure until into your
30s literature true you know more about
me than I do but I'll try to be
consistent with what you're really ya
know just believe me
yeah just go with whatever story I tell
you it'll be easier that way the
conversation I've heard mentioned a
Philip Roth's American pastoral which I
love as a book I don't know if it was it
was mentioned as something I think that
was meaningful to you as well in either
case what literary books had a lasting
impact on you what okay good so I so I
met Russ already well we both got
doctors from Harvard on the same day so
I so we were yeah we had lunch together
and stuff like that and but he knew that
you know computer books would never sell
well well all right so you say you you
you you're a teenager when you left
Russia so I I have to say that Tolstoy
was one of the big influences on me
I especially like Anna Karenina not
because of a particular area of the plot
of the story where but because there's
this character who you know did the
philosophical discussions it's all it's
a whole way of life is worked out there
it's among the characters until in and
so it that I thought was was especially
beautiful on the other hand does they
have ski I I didn't like at all because
I I felt that he his genius was mostly
because he kept forgetting what he what
he had started out to do and he was just
sloppy I didn't think that that it then
that he polished his stuff at all and
and I tend to admire somebody who who
Todd's the i's and cross the t's so that
the music of the prose this way you
admire more and that I certainly do
admire the music of the language which I
couldn't appreciate in the Russian
original but but I can and Victor Hugo
Glenn's close friendships much his
closer but but Tolstoy I like the same
reason I like Herman Wouk as a as a
novelist I that I think I like his book
Marjorie Morningstar has a similar
character in who who who developed his
own personal philosophy and export and
it called goes in in was consistent yeah
right and it's worth worth pondering uh
so zo like Nietzsche and like what you
don't like Friedrich Nietzsche or age
yeah no no you like this has like I keep
seeing quotations for Nietzsche and and
you never tempt me to read any further
please full of contradictions we will
certainly not appreciate him but
Schiller you know I'm trying to get the
cross what I appreciate in literature
and part of it is the is is as you say
the music of the language of the way it
flows and take Raymond Chandler versus
Dashiell Hammett Dashiell Hammett
sentences are awful and Raymond
Chandler's are beautiful they just flow
so I I don't I don't read literature
because it's supposed to be good for me
or because somebody said it's great but
but it I could find things that I like I
mean you mentioned you address like
James Bond so like I love Ian Fleming I
think he's got a he had a really great
gift for if he has a golf game or game
of bridge or something and this comes
into a story it'll it'll be the most
exciting golf game or or you know the
absolute best possible hands a bridge
that that exists and and any he exploits
it and tells it beautifully as well so
in connecting some things here looking
at literate programming and being able
to it convey encode algorithms to a
computer in a way that mimics how humans
speak how what do you think about
natural language in general and the
messiness of our human world about
trying to express yeah difficult things
so the idea of literate programming is
to is really to try to understand
something better by seeing it from these
two perspectives the formal and the
informal if we try to understand a
complicated thing if we can look at it
in different ways and so this is in fact
the key to technical writing a good
technical writer
try not to be obvious about it but says
everything twice formally and informally
or maybe three times but you try to give
the reader a way to put the concept into
his own brain or her own brain is that
better for the writer or the reader or
both well the writer just tries to
understand the reader that's the goal of
a writer is to have a good mental image
of the reader and to say what the reader
expects next and to to impress the
reader with what has impressed the
writer why something is interesting so
when you have a computer program we try
to instead of looking at it as something
that we're just trying to give an
instruction to the computer what we
really want to be is giving giving
insight to the person who's who's gonna
be maintaining this program or to the
programmer himself when he's debugging
it as to why this stuff is being done
and so all the techniques of exposition
that a teacher uses or book writers make
you better program or if your if your
program is going to be not just a
one-shot deal so how difficult is that
do you see hope for the combination of
informal and formal for the programming
task yeah I I'm the wrong person to ask
I guess because I'm a geek but but I
think for a geek it's easy I don't know
I don't know see not some people have
difficulty writing and that might be
because there's something in their brain
structure that makes it hard for them to
write or or it might be something just
that they haven't had enough practice
I'm not the right one to to uh to judge
but I don't think you teach any person
any particular skill like I do think
that that writing is is half of my life
and so I put it together and let
program he won't even when I'm writing a
one-shot program I I write it in
literate way because I get it right
faster though now does it get compiled
automatically or so I guess on the
technical side my question was how
difficult is a design a system where
much of the programming is done
informally informally yeah informally I
think whatever works to make it
understandable is good but then you have
to also understand how informal is you
have to know the limitations you have to
connect so so by putting the formula and
informal together this this is where
this is where it gets locked into your
into your brain now you can you can say
informally well I'm working on a problem
right now so let's go there I get that
can you give me an example of of
connecting the informal in the formal
well it's a little too complicated an
example there's a puzzle that that's
self referential it's called a Japanese
arrow puzzle and and and you're given a
a bunch of boxes each one points north
east south or west and at the end you're
supposed to fill in each box with the
number of distinct numbers that it
points to so if I put a three in a box
that means that and it's pointing to
five other boxes that means that there's
going to be three different numbers in
those five bucks and and those boxes are
pointing what I might be pointing to me
one of my might be pointing the other
way but anyway I kind of defined a set
of numbers that obeys this complicated
condition that each number counts how
many distinct numbers if it points do
well and still a guy sent me his
solution to this problem where he where
he presents
formal statements that that say either
this is true or this is true this is
true and and and so I try to render that
formal statement informally and I try
say I contain a three and and the guys
I'm pointing to contain the numbers one
two and six so by putting it in formally
and also I converted into a into a
dialogue statement that helps me
understand the logical statement that
he's written down as a string of numbers
in terms of some abstract variables
Eddie yeah
that's really interesting so maybe an
extension of that there has been a
resurgence in computer science and
machine learning and neural networks so
using data to construct algorithms so
it's another way to construct algorithms
really yes you can think of it that way
so as opposed to natural language to
construct algorithms use data to
construct other so what what's the view
of this branch of computer science where
data is almost more important than the
mechanism of the algorithm it seems to
be suited to a certain kind of non geek
and would you know which is probably why
it's it's like it's taken off that it
has its own community that I thought
really that really resonates with that
but it's hard to you know to trust
something like that because nobody even
the people who who work with it that
they have no idea what is what has been
learned that's a really interesting
thought that it's it makes algorithms
more accessible to a different community
a different type of brain yep and that's
really interesting because just like
literate programming perhaps could make
programming more accessible to a certain
kind of brain there are people who think
it's just a matter of Education and
anybody can learn to be a great program
or anybody can
to be a great skier uh yeah you know I I
wish that were true but but I know that
there's a lot of things that I've tried
to do and I and like I was well motivate
an icon and I kept trying to build
myself up and I never got past a certain
level I can't use for example I can't
view three-dimensional objects in my in
my head I have to I have to make a model
and look at it and study it from all
points of view and then I start to get
some idea but other people are good at
four dimensions I mean physicists yeah
so let's go to the art of computer
programming in 1962 you set the table of
contents for this magnum opus right yeah
it was supposed to be a single book for
12 chapters now today what is it
57 years later you're in the middle of
volume 4 of 7 and in the middle of going
for B is 4 B precisely can ask you for
an impossible task which is try to
summarize the book so far maybe by
giving a little examples so from the
sorting and the search in the
combinatorial algorithms if you were to
give a summary a quick elevator summary
yeah right what depending how many
floors that are in the building yes
the first volume called fundamental
algorithms talks about something that
you can't the stuff you can't do without
I guess that you have to know the basic
concepts of what is a program now what
is it what is it algorithm and and and
it also talks about a low-level machine
so you can have some some kind of an
idea what's going on and it has basic
concepts of input/output and subroutines
induction induction writes mathematical
so so the thing that makes my book
different from a lot of others is that
all that I try to not only present the
algún but I try to analyze them and
which means to quantitatively I say not
only does it work but it works this fast
okay and so I need math for them and
then there's the standard way to
structure data inside and represent
information in the computer so that's
all volume 1 volume 2 talks
it's called semi numerical algorithms
and here we're here we're writing
programs but we're also dealing with
numbers algorithms deal with with with
any kinds of objects but but specific
when there's objects or numbers well
then then we have certain special
paradigms that apply to things that have
12 numbers and so there's there's what
there's like there's arithmetic on
numbers and and there's matrices full of
numbers there's random numbers and
there's power series full of numbers
there's different algebraic concepts
that have numbers in structured ways and
the arithmetic in the way a computer
would think about arithmetic is a
floating point floating point arithmetic
a high precision arithmetic not only
addition subtraction multiplication but
also comparison up number
so then check then volume three talks
about I like that one sort insert
sorting a circle of sorting right so so
here you know we're not getting
necessarily with numbers because you
slipped you saw it letters and other
objects and searching we're doing all
the time we googled nowadays but I mean
we have to find stuff
so again algorithms that that underlie
all kinds of applications like you know
none of these volumes it's about a
particular application but the
applications are examples of of why
people want to know about sorting why
people want to know about random numbers
so then volume 4 goes into combinatorial
I'll again this is where we have
zillions of things to deal with and we
and here we keep finding cases where one
good idea can can make something go more
than a million times faster and and and
we're dealing with problems that are
probably never going to be solved
efficiently but that doesn't mean we
give up on them and and and we have this
chance to have good ideas and and go
much much faster on them so so that's
comets are all algorithms and those are
the ones that are yeah I'm using
charting is most fun for you well how
many toriel algorithms are the ones that
I always that I always enjoyed the most
because that's when my skillet
programming had most payoff you know the
different the difference between an
obvious algorithm that you think up
first thing and you know and a good you
know an interesting subtle out algorithm
that not so obvious but but run circles
around the other one that's that's where
computer science 3d comes comes in and
and a lot of these comets are methods
were found first in applications to
artificial intelligence or cryptography
and in my case I I just liked him and it
was associated more with puzzles that
you like the most in the domain of
graphs and graph theory graphs are great
because they're terrific models of so
many things in the real world and and
and and you you throw numbers on a graph
you got a network and so there you're
right there you have but many more
things so but comma toriel in general is
in any arrangement of objects that that
has some kind of a higher structure non
non random structure and it's okay
it is possible to put something together
satisfying all these conditions like I
mentioned arrows a minute ago you know
is there a way to to put these numbers
on a bunch of boxes that that are
pointing to each other is that going to
be possible at all that's volume four
that's volume four what is a sage of
Hawaiian for a was part one and and what
happened was in 1962 when I started
writing down a table of contents it
wasn't going to be a book about computer
programming in general it was going to
be a book about how to write compilers
and I was asked to write a book
explaining how to how to write a
compiler and at that time there were
only a few dozen people in the world who
had written compilers and I happen to be
one of them so and I also had some
experience for writing for like the
campus newspaper and things like that so
so I said okay great I'm the only person
I know who who's written a compiler but
hasn't invented any new techniques for
writing compilers and and all the other
people I knew had super ideas but I
couldn't see that they would be able to
write a book that wouldn't that would
describe anybody else's ideas with their
own so I could be the I could be the
journalist and I could explained what
all these cool ideas about compiler
writing that were and and then I I
started pretty
well yeah let me you need and have a
chapter about data structures you need
to have some introductory material I
want to talk about searching because a
compiler writer has to it has to look up
the variables in a symbol table and find
out you know which which when you when
you write the name of a variable in one
place it's supposed to be the same as
the one you put somewhere else so you
need all these basic techniques and I
and I you know kind of know some
arithmetic to stuff so I throw I threw
in these chapters and I threw in a
chapter on comma talks because that was
what I really enjoyed programming the
most but there weren't many algorithms
and known about combinatorial methods in
1962 so that was a kind of a short
chapter but it was sort of thrown in
just for fun and Chapter twelve was
going to be actual compilers applying
all the stuff in chapters 1 to 11 to
make compilers well ok so that was my
table of contents from 1962 and during
the 70s the whole field of combinatoric
s-- went through a huge explosion people
talk about it comet oil explosion and
they usually mean by that that the
number of cases goes up you know you
change n to n plus 1 and all of a sudden
you your problem has gotten more than
ten times harder but there was an
explosion of ideas about combinatoric
s-- in the 70s and to the point that but
Mike's take 1975 I bet you more than
half of all the journals of computer
science we're about combinatorial method
and what kind of problems were occupying
people's minds what kind of problems in
combinatorics was it's it's that gravity
graph theory yeah gravity was was quite
dominant I mean no but all of the
np-hard problems that you have like
Hamiltonian path or foul sail going
beyond yeah yeah going beyond graphs you
had a operation research whenever it was
a small class of problems that had
efficient solutions and they were
associated with Maitre D' a special
mathematical construction but once we
went to things that involve three things
at a time instead of instead of two all
of a sudden the things got harder so we
had satisfiability problems or if you
have if you have clauses every Clause
has two logical elements in it then we
can satisfy it linear time we can test
for satisfy building linear time but if
you allow yourself three variables in
the clause then nobody knows how to do
it so these articles were about trying
to find better or better ways to to
solve cryptography problems and graph
three problems where the we have lots of
data but we didn't know how to find the
best subset so the data like with
sorting we could get the answer didn't
take long so how did they continue to
change from the 70s to today yeah so now
there may be half a dozen conferences
whose topic is cognate arcs different
kind but fortunately I don't have to
rewrite my book every month you know
like I had to in in the 70 but still
there's huge amount of work being done
and people getting better ideas on these
problems that don't seem to have really
efficient solutions but we can still get
into a lot more with him and so this
book that I'm finishing now is I've got
a whole bunch of brand new methods that
the fires I know there's no other
there's no other book that covers that
covers this particular approach and and
so I'm trying to do my best of exploring
the tip of the iceberg and and and I try
out lots of things and and keep keep
rewriting finding as I find better
better method so what's your writing
process like what's your thinking and
writing process like every day so what's
your routine even
yeah I guess it's actually the best
question because I spent seven days a
week
you're doing it the most prepares to
answer it yeah yeah but okay so the
chair I'm sitting in is where I do
that's where the magic happens well
reading and writing that many chairs
usually sitting over there where I have
other books some reference book but but
I I found his chair which was designed
by a Swedish guy anyway it turns out
this was the only chair I can really sit
in for hours and hours and not know that
I'm in a chair but then I have the
stand-up desk right next next to us and
and so after I write something with
pencil and eraser I get up and I type it
and revise and rewrite the kernel the
idea is first put on paper yep
that's worth right and I call right
maybe five programs a week of course
literate programming and these are
before I describe something in my book I
always program it to see how it's
working and I and I tried a lot so for
example I learned at the end of January
I learned of a breakthrough by for
Japanese people who had extended one of
the one of my methods in in a new
direction and so I I spent the next five
days writing a program to implement what
they did and then I you know but they
had only generalized part of what I had
done so that I had to see if I could
generalize more parts of it and then I
had to take their approach and I had to
I had to try it out on a couple of dozen
of the other problems I had already
worked out with that with my old methods
and so that took another couple of weeks
and then I would you know then I then I
started to see the light nicely and and
I started writing the final draft and
and then I would you know type it up
involves some new mathematical questions
and so I wrote to my friends and might
be good at solving those problems and
and they solve some of them so I put
that in his exercises and and so a month
later I had absorbed one new idea that I
that I learned and you know I'm glad I
heard about it in time otherwise my I
wouldn't put my book out before I heard
about the idea on the other hand this
book was supposed to come in at 300
pages and I'm up to 350 now that added
10 pages to the book but if I learn
about another one I probably first gonna
shoot me well so in the process in that
one month process are some days harder
than others are some days harder than
others well yeah my work is fun but I
also work hard and every big job has
parts that are a lot more fun than
others and so many days I'll say why do
I have to have such high standards like
why couldn't I just be sloppy and not
try this out and you know just just
report the answer but I but I know that
people are conning me to do this and so
okay so okay Donald grit my teeth and do
it and and and then the joy comes out
when I see that actually you know I'm
getting good results and and and I get
and I even more when I see that somebody
has actually read and understood what I
wrote and told me how to make it even
better I did want to mention something
about the about the method so I got this
tablet here where I do the first you
know the first writing of concepts okay
so so and what language I didn't write
so hey take a look at but you know here
random say explain how to draw such
skewed pixel diagrams okay so I got this
paper about 40 years ago when I was
visiting my sister in Canada and they
make tablets of paper with this nice
large size and just the right very small
space between like oh yeah yeah
particularly also just yeah
you know I've got these manuscripts
going back to the 60s and and and those
are when I get my ideas on paper okay
but I'm a good typist in fact I went to
type in school when I was when I was in
high school and so I can type faster
than I think so then when I do the
editing you know stand up and type then
I then I revise this and it comes out a
lot different than what you look for
style and rhythm and things like that
come out at the at the typing state and
you type in tack and I type in tack and
can you can you think in tech No so to a
certain extent I have I have only a
small number of idioms that I use like
you know a beginning or theorem I do
something for displayed equation I do
something and and so on but I but I I
have to see it and in the way that it's
on here yeah right for example touring
wrote what the other direction
you don't write macros you don't think
in macros particularly but when I need a
macro I'll go ahead and and these and do
it but but the thing is they I also
write to fit I mean I'll I'll change
something if I can if I can save a line
I've got you know it's like haiku I'll
figure out a way to rewrite the sentence
so that it'll look better on the page
and I shouldn't be wasting my time on
that but but I can't resist because I
know it's only another three percent of
the time or something like that and it
could also be argued that that is what
life is about
ah yes in fact that's true like like I
worked in the garden one day a week and
that's that's kind of a description of
my life is getting rid of weeds you know
removing bugs for programs in so you
know a lot of writers talk about you
know basically suffering the writing
processes yeah having you know it's
extremely difficult and I think of
programming especially the or technical
writing that you're doing can be like
that do you find yourself
methodologically how do you every day
sit down to do the work is it a
challenge you kind of say it's you know
oh yeah it's fun
but it'd be interesting to hear if there
are non fun parts that you really
struggle with yes the fun comes with
when I'm able to put together ideas of
to two people who didn't know about each
other and and and so I might be the
first person that saw both of their
ideas and so then you know then I get to
make the synthesis and that gives me a
chance to be creative but the dredge
work is where I act I've got a chase
everything down to its root this leads
me into really interesting stuff i mean
like i learned about sanskrit nice yeah
and again you know I try to give credit
to all the authors and so I write like
so I write to people who know that the
people thought as if they're dead I
communicate this way I and I gotta get
the math right and I got a tack all my
programs try to find holes in them and I
rewrite the programs over after I get a
better idea
is there ever dead-ends data and so yeah
I throw stuff out yeah look one of the
things that I spent a lot of time
preparing a major example based on the
game of baseball and I know a lot of
people who for whom baseball is the most
important thing in the world you know
yes but it's but I also know a lot of
people from cricket is the most
important in the world or suck or
something you know and and I realized
that if if I had a big sample I mean it
was gonna have a fold-out illustration
and everything I was saying well what
what am I really teaching about
algorithms here where I had this this is
this baseball example and if I was a
person who who knew only cricket
wouldn't think what would they think
about this and and so I ripped the whole
thing out but I you know I had I had a
something that would really appeal to
people who grew up with baseball as as
has a major theme in their life which is
a lot of people but yeah so I said on
minority the small minority I took out
bowling to
even a smaller my noise what's the art
in the art of programming why why is
there of the few words in the title why
is art one of them yeah well that's
that's what I wrote my Turing lecture
about and and so when people talk about
art it really I mean what the word means
is something that's not a nature so when
you have artificial intelligence that
that art come from the same root saying
that this is something that was created
by by human beings and then it's gotten
a further meaning often a fine art which
has this beauty to the to the mix and
says you know we have things that are
artistically done and and this means not
only done by humans but also done in a
way that's elegant and brings joy and
and has has I guess what
Tolstoy burrs dusky but anyway it it's
that part that that says that it's done
well as well as not only a different
from nature in general then alright is
what human beings are specifically good
at and when they say hey like artificial
intelligence well they're trying to
mimic human beings but there's an
element of fine art and beauty you are
well that's what I that's what I try to
also say that you can write a program
and make a work of art so now in terms
of surprising you know what ideas in
writing from sort and search to the
combinatorial algorithms what ideas have
you come across that were particularly
surprising to you that that change the
way you see a space of
I get a surprise every time I have a bug
in my program but but that isn't really
what your transformational surprises for
example in volume for a I was especially
surprised when I learned about data
structure called B BDD boolean decision
diagram because I sort of had the
feeling that as an old-timer and you
know I've been programming since this
since the 50s and bTW these weren't
invented until 1986 and here comes a
brand new idea that revolutionized the
way to represent a boolean function and
boolean functions are so basic to all
kinds of things in it I mean logically
underlies it everything we can describe
all of what we know in terms of logic
somehow and and here and and
propositional logic I thought that was
cutting Dryden everything was known but
but but he but here comes a Randy Bryant
and oh and discovers that BDDs are
incredibly powerful then then that's all
so I that mean means I have a whole new
section to the book that I never would
have thought of until 1986
not until 1990s when I went when people
started to got to use it for you know
billion dollar of applications and it
was it was the standard way to design
computers for a long time until until
sad solvers came along when in the year
2000 so that's another great big
surprise so uh a lot of these things
have have totally changed the structure
of my book and the middle third of
volume four B's is about that solvers
and that's
300 plus pages which is which is all
about material mostly about material
that was discovered in this century and
I had to start from scratch and meet all
the people in the field and right
I have 15 different sets Alvers that i
wrote while preparing that seven of them
are described in the book others were
for my own experience so newly invented
data structures or ways to represent a
whole new class of algorithm calling you
classified yeah and the interesting
thing about the BD DS was that the
theoretician started looking at it and
started to describe all the things you
couldn't do with BD DS and so they were
getting a bad they were getting a bad
name because you know okay they were
they were useful but they didn't solve
everything I'm sure that the
theoreticians are in the next 10 years
are gonna show why machine learning
doesn't solve everything but I not only
worried about the worst case I get a
huge delight when I can actually solve a
problem that I couldn't solve before
yeah even though I can't solve the
problem that's that it suggests as a
further problem like I know that I'm Way
better than I was before and so I found
out that BD DS could do all kinds of
miraculous things and so I had been
quite a few years learning about the
that territory so in general what brings
you more pleasure in proving or showing
a worst case analysis of an algorithm or
showing a good average case or just
showing a good case that you know
something good pragmatically can be done
with this algorithm yeah I like a good
case that that is maybe only a million
times faster than I was able to do
before but and not worried about the
fact that
and that is still that is still gonna
take too long if I double the size of
the problem so that said you popularize
the asymptotic notation for describing
running time obviously in the analysis
of algorithms worst cases such as such
an important part do you see any aspects
of that kind of analysis is lacking so
and notation - well the main purpose you
have notations that that help us for the
problems we want to solve and so that
they match our they match our intuitions
and people who worked in number theory
had used asymptotic notation in what
Ennis in a certain way but it was only
known to a small group of people and and
I realized that in fact it was very
useful to be able to have a notation for
something that we don't know exactly
what it is but we only know partial
about it and so on stick so for example
instead of Big O notation let's just
let's just take us a much simpler
notation where I say 0 or 1 or 0 1 or 2
and suppose that suppose that when I had
been in high school we would be allowed
to put in the middle of our formula x +
0 1 or 2 equals y okay and then then we
would learn how to multiply two such
expressions together and and you know
deal with them
well the same thing Big O notation says
here's something that's I'm not sure
what it is but I know it's not too big I
know it's not bigger than some constant
times N squared or something like that
fine so I write Big O of N squared and
now I learned how to add Big O of N
squared to Big O of N cubed and I know
how to add Big O of N squared 2 plus 1
and square that and how to take
logarithms and Exponential's to have big
O's in the middle of them and that
turned out to be hugely valuable in all
of the work that I was trying to do is
I'm trying to figure out how good
so I have there been algorithms in your
journey that perform very differently in
practice than they do in theory well the
worst case of a comet our logarithm is
almost always horrible but but we have
sad solvers that are solving where one
of the one of the last exercises in that
part of my book was to figure out a
problem that has a hundred variables
that's that's difficult for us at solver
but uh but you would think that a
problem with the hundred boolean
variables has required to do 2 to the
100th operations because that's the
number of possibilities when you have
200 boolean variables in 2 to the 100th
to the 100th is way bigger than then we
can handle 10 to the 17th is a lot
you've mentioned over the past few years
that you believe P may be equal to NP
but that it's not really you know
somebody does prove that P equals NP it
will not directly lead to an actual
algorithm to solve difficult problems
can you explain your intuition here has
it been changed and in general on the
difference between easy and difficult
problems of P and NP and so on yes so
the popular idea is if an algorithm
exists then somebody will find it and
it's just a matter of writing it down
one point well but many more algorithms
exist than anybody can end understand or
ever make you discover yeah because
they're just way beyond human
comprehension of the total number of
algorithms is more than mind-boggling
so so we have situations now where we
know that algorithm exists but we don't
know we don't the foggiest idea what the
algorithms are there's there are simple
examples based on on game playing where
you have
where you say well there must be an
algorithm that exists to win in the game
of hex because for the first player to
win in the game of hex because hex is
always either an a win for the first
player of the second player well what's
the game of hack there's a game of hex
which is which based on putting pebbles
onto a hexagonal board and and the white
player tries to get a light path from
left to right and the black player tries
to get a black path from bottom to top
and how does capture occur just so and
and and there's no capture you just put
levels down what one at a time but
there's no drawers because they after
all the white and black are played
there's either going to be a white path
across from each to west or a black path
from from bottom to top so there's
always you know it's the perfect
information game and people people play
take turns like like tic-tac-toe and hex
or it can be different sizes but we
there's no possibility of a draw and
player to move one at a time and so it's
got to be either a first player win or a
second player win
mathematically you follow out all the
trees and and either either there's
always the win for the percolator
second player okay and it's finite the
game is finite so there's an algorithm
that will decide you can show it has to
be one of the other because the second
player could mimic the first player with
kind of a pairing strategy and so you
can show that it has to be what it has
to be one or that but we don't know any
algorithm no way there there a case
where you can prove the existence of the
solution but we but nobody knows anyway
how to find it but more like the
algorithm question there's a very
powerful theorem and graph theory by
Robinson to see more that says that
every class of graphs that is closed
under taking minors
has a polynomial time algorithm to
determine whether it's in this class or
not now a class of graphs for example
planar graphs these are graphs that you
can draw in a plane without crossing
lines and and a planar graph is close
taking minors means that you can shrink
an edging into a point or you can delete
an edge and so you start with a planar
graph and drink any edge to a point is
still planar deleting edges to a planner
okay now but there are millions of
different ways to describe family of
graph that still is remains the same
undertaking minor and Robertson Nassim
are proved that any such family of
graphs there is a finite number of
minimum graphs that are obstructions so
that if it's not in the family then then
it has to contain then there has to be a
way to shrink it down and until you get
one of these bad minimum graphs that's
not in the family for in plate case for
planar graph the minimum graph is a is a
five-pointed star where there everything
pointed to another and the minimum graph
consisting of trying to connect three
utilities to three houses without
crossing lines and so there are two
there are two bad graphs that are not
planar and every every non planar graph
contains one of these two bad graphs by
by shrinking and he said again so he
proved that there's a finite number of
these bad guys always a finite know
somebody says here's a family it's hard
to believe and they present its sequence
of 20 papers I mean in there it's deep
work but it you know it's because that's
for any arbitrary class so it's for any
arbitrary class that's closed under
taking minors that's closed under maybe
I'm not understanding because it seems
like a lot of them are closed
taking minors almost all the important
classes of graphs are
there are tons of of such graphs but
also hundreds of them that arise in
applications like I have a book over
here called classes of graphs and then
and it it's amazing how many different
classes people have looked at so why do
you bring up this theorem lower this
proof so you know there are lots of
algorithms that that are known for
special class of graphs for example if I
have a certain if I have a chordal graph
then I can color it efficiently if I
have some kinds of graphs it'll make a
great Network very soon like you'd like
to test you somebody gives you a graph
that's always it in this family of grass
if so then I hope then I can I can go to
the library and find an algorithm that's
gonna solve my problem on that graph
okay so we we have we want to have a
graph that says number than that says
give me a graph I'll tell you whether
it's and whether it's in this family or
not okay and so all I have to do is test
whether or not that does this given
graph have a minor that's one of the bad
ones a minor is is everything you can
get by shrinking and removing edges and
given any minor there's a polynomial
time algorithm saying I can tell whether
this is a minor of you and there's a
finite number of bad cases so I just
tried you know does it have this bad
case by polynomial time I got the answer
does he have this bad case probably time
I got the answer a total polynomial time
and so I've solved the problem however
all we know is that the number of minors
is finite we don't know what we might
only know one or two of those minors but
we don't know that if we got it if we
got 20 of them we don't know there might
be 20 125 the Halloween all we know is
that is that it's finite so here we have
a polynomial time algorithm that we
don't know
mm-hm that's a really great example of
what you worry about or why you think P
equals NP won't be useful
but still why do you hold the intuition
that P equals NP because you have to
rule out so many possible algorithms
have been not working you know you can
you can take the graph and you can
represent it as in terms of certain
prime numbers and then you can multiply
those together and then you can then you
can take the bitwise and and and you
know and construct some certain constant
in polynomial time and then that's you
know perfectly valid algorithm and that
there's so many algorithms of that kind
a lot of times we see random you take
data and and and we get coincidences
that that that some fairly random
looking number actually is useful
because because it god it happens to it
happens to self it happens to solve a
problem just because you know there's
there's so many hairs on your head
but it seems like unlikely that two
people are going to have the same number
of hairs on their head but but they're
obvious but you can count how many
people there are and how many hairs on
there so there must be people walking
around in the country to have the same
number of hairs on their head well
that's the kind of a coincidence that
you might say also you know this this
particular combination of operations
just happens to prove that a graph is
has a Hamiltonian path and I see lots of
cases where unexpected things happen
when you have enough enough
possibilities but because the space of
possibility is so huge I have to rule
them all out and so that's the reason
for my intuition is good by no means
approve I mean some people say you know
well P can't equal NP because you've had
all these smart people you know the
smartest designers of algorithms that
have been
wrecking their brains for years and
years and and there's million-dollar
prizes out there and you know none of
them nobody has thought of the algorithm
so it must must be no such job on the
other hand I can use exactly the same
logic and I can say well P must be equal
to NP because there's so many smart
people out here been trying to prove it
unequal to NP and they've all failed you
know this kind of reminds me of the
discussion about the search for aliens
they've been trying to look for them and
we haven't found them yet therefore they
don't exist
yeah but you can show that there's so
many planets out there that they very
possibly could exist yeah and right and
then there's also the possibility that
that they exist but they they all
discovered machine learning or something
and and and then blew each other up well
on that small quick danger
let me ask do you think there's
intelligent life out there in the
universe I have no idea do you hope so
do you think about it it I I don't I
don't spend my time thinking about
things that I could never know really
and yet you do enjoy the fact that there
are many things you don't know you do
enjoy the mystery of things I enjoy the
fact that there that I have limits yeah
but I don't but but I don't take time to
answer unsolvable questions I got it
well because you've taken on some tough
questions that may seem unsolvable you
have taken on some tough questions and
you seem unsolvable if there is because
we are thrilled when I can get further
than I ever thought I could right yeah
but but I don't what much like was
religion these I'm glad the dirt that
that there are no proof that God exists
or not I mean I think it would spoil the
mystery it it would be too dull yeah so
to quickly talk about the other art of
artificial intelligence
what is if you what's your view
you know artificial intelligence
community has developed as part of
computer science and in parallel with
computer science
since the 60s what's your view of the AI
community from the 60s to now so all the
way through it was the people who were
inspired by trying to mimic intelligence
or to do things that that were somehow
the greatest achievements of
intelligence that had been inspiration
to people who have pushed the envelope
of computer science maybe more than any
other group of people so it's all the
way through it's been a great source of
of good problems to to sink teeth into
and and getting getting partial answers
and then more and more successful
answers over the year so this has this
has been the inspiration for lots of the
great discoveries of computer science
are you yourself captivated by the
possibility of creating of algorithms
having echoes of intelligence in them
not as much as most of the people in the
field I guess I would say but but that's
not to say that they're wrong or that
it's just you asked about my own
personal preferences and yeah but but
the thing that I that I worry about is
when people start believing that they've
actually succeeded and because the seems
to me this huge gap between really
understanding something and being able
to pretend to understand something and
give these give the illusion of
understanding something do you think
it's possible to create without
understanding yeah
so to uh I do that all the time to run I
mean that's why I use random members I
like yeah but I but but there's there's
still what this great gap I don't know
certain it's impossible but I'm like but
I don't see a anything coming any closer
to really
the the kind of stuff that I would
consider intelligence say you've
mentioned something that on that line of
thinking which I very much agree with so
the art of computer programming as the
book is focused on single processor
algorithms and for the most part and you
mentioned that's only because I set the
table of contents in 1962 you have to
remember for sure there's no I'm glad I
didn't wait until 1965 or one book maybe
will touch in the Bible but one book
can't always cover the entirety of
everything so I'm glad yeah I'm glad the
the table of contents for the art of
computer programming is what it is but
you did mention that that you thought
that an understanding of the way ant
colonies are able to perform incredibly
organized tasks might well be the key to
understanding human cognition
so these fundamentally distributed
systems so what do you think is the
difference between the way Don Knuth
would sort a list and an ant colony
would sort a list or performing
algorithm sorting a list isn't same as
cognition though but but I know what
you're getting at is well the advantage
of ant colony at least we can see what
they're doing we we know which ant has
talked to which other ant and and and
and it's much harder with the quick
brains to just to know how to what
extent of neurons are passing signal so
I understand that aunt Connie might be a
if they have the secret of cognition
think of an ant colony as a cognitive
single being rather than as a colony of
lots of different ants I mean just like
the cells of our brain are and and the
microbiome and all that is interacting
entities but but somehow I consider
myself to be
single person well you know aunt Connie
you can say might be cognitive is
somehow and it's yeah I mean you know I
okay I like I smash a certain aunt and
mmm that's stung what was that right you
know but if we're going to crack the the
the secret of cognition it might be that
we could do so by but my psyche note how
ants do it because we have a better
chance to measure and they're
communicating by pheromones and by
touching each other and sight but but
not by much more subtle phenomenon Mike
electric currents going through but even
a simpler version of that what are your
thoughts of maybe Conway's Game of Life
okay so Conway's Game of Life is is able
to simulate any any computable process
and any deterministic process is like
how you went there I mean that's not its
most powerful thing I would say I mean
you can simulate it but the magic is
that the individual units are
distributed yes and extremely simple yes
we can we understand exactly what the
primitives are the permit is the just
like with the anthology even simple but
if we but still it doesn't say that I
understand I understand life I mean I
understand it it gives me an it gives me
a better insight into what does it mean
to to have a deterministic universe what
does it mean to to have free choice for
example do you think God plays dice yes
I don't see any reason why God should be
forbidden from using the most efficient
ways to to to I mean we we know that
dice are extremely important and
inefficient algorithms there are things
like that couldn't be done well without
randomness and so I don't see any reason
why
my god should be prohibited but when the
when the algorithm requires it
you don't see why the know the physics
should constrain it yeah
so in 2001 you gave a series of lectures
at MIT about religion and science
well that would 1999 but you published
the book came out in Cooper so in 1999
you spent a little bit of time in Boston
enough to give those lectures yeah and I
read in the 2001 version that most of it
it's quite fascinating read I recommend
people its transcription of your
lectures so what did you learn about how
ideas get started and grow from studying
the history of the Bible sieve
rigorously studied a very particular
part of the Bible what did you learn
from this process about the way us human
beings as a society develop and grow
ideas share ideas and I'm by those idea
I I tried to summarize that I wouldn't
say that I that I learned a great deal
of really definite things like right
where I could make conclusions but I
learned more about what I don't know you
have a complex subject which is really
beyond human understanding so so we give
up on saying I'm never going to get to
the end of the road and I'm never going
to understand it but you say but but
maybe it might be good for me to to get
closer and closer and learn more about
more and more about something and so you
know oh how can I do that efficiently
and the answer is well use randomness
and so to try a random subset of the
that that is within my grasp and and and
and study that in detail instead of just
studying parts that somebody tells me to
study or instead of studying nothing
because it's too hard so I I i decided
for my own amusement that one ones that
I would I would take a subset of the of
the verses of the Bible
and I would try to find out what the
best thinkers have said about that small
subset and I had had about let's say 660
verses out of out of 3,000 I think it's
one out of 500 or something like this
and so then I went to the libraries
which which are well indexed uh you can
you you know I spent for example at at
Boston Public Library I I would go once
a week for a year and I went to I went I
have done time stuff and over Harvard
library to look at this yes that weren't
in the Boston Public where they where
scholars had looked at and you can call
in the eight and you can go down the
shelves and and you can pretty you can
look at the index and say oh there it is
this verse I mentioned anywhere in this
book if so look at page 105 so I was
like I could learn not only about the
Bible but about the secondary literature
about the Bible the things that scholars
have written about it and so that that
gave me a way to uh to zoom in on parts
of the things so that I could get more
more insight and and so I look at it as
a way of giving me some firm pegs which
icon which I could hang pieces of
information but not as as things where I
would say and therefore this is true in
this random approach of sampling the
Bible what did you learn about the the
most you know central oh one of the
biggest accumulation of ideas you know
to me that the that the main thrust was
not the one that most people think of as
saying you know you know don't have sex
or something like this but that the main
thrust was to try to to try to figure
out how to live in harmony
with God's wishes I'm assuming that God
exists and I say I'm glad that I that
there's no way to prove this because
that would that would I would run
through the proof once and then I'd
forget it and and it would and and I
would never just speculate about
spiritual things and mysteries otherwise
and I think my life would be very
incomplete so I so I'm assuming that God
exists but it if but a lot of things the
people say God doesn't exist but that's
still important to them and so in a way
in a way that might still be other God
is there or not in some sense so it it
guys important to them it's one of the
one of the verses I studied act is you
can interpret as saying you know it's
much better to be an atheist that not to
care at all so I would say it's yeah
it's similar to the P equals NP
discussion yeah you you mentioned a
mental exercise that I'd love it if you
could partake in yourself a mental
exercise of being God and so how would
you if you were God dot Knuth how would
you present yourself to the people of
Earth you mentioned your love of
literature and there was it there's this
book that would that really uh I can
recommend to you if I can't think yeah
the title I think is blasphemy it talks
about God revealing himself through a
computer in in in Los Alamos and and it
it's the only book that I've ever read
where the punchline was really the very
last word of the book and it explained
the whole idea of the book and so I
don't want to give that away but it but
it's really very much about this
question that that she raised
but but suppose God said okay that my
previous on means of communication with
the world are and not the best for the
21st century so what should I do now and
and and it's conceivable that that it
would that that God would choose the way
that's described in this book and
another way to look at this exercise is
looking at the human mind looking at the
human spirit the human life in a
systematic way I think it mostly you
want to learn humility you want to
realize that once we solve one problem
that doesn't mean it worked at all so no
other problems are going to drop out and
and and and we have to realize that that
that there are there are things beyond
our beyond our ability I see hubris all
around yeah well said if you were to run
program analysis on your own life how
did you do in terms of correctness
running time resource use asymptotically
speaking of course okay yeah well I
would say that question has not been
asked me before and i i i started out
with library subroutines and and
learning how to be a automaton that was
obedient and i had the great advantage
that i didn't have anybody to blame for
my failures if I started getting not
understanding something I I knew that I
should stop playing ping pong and that
was that into it was my fault that I was
that I wasn't studying hard enough or
something rather than that somebody was
discriminating against me in some way
and
I don't know how to avoid this the
existence of biases in the world but i
but i but i know that that's an extra
burden that i didn't have to suffer from
and and and then i I found the from from
parents I learned the idea of of
altruist to other people as being more
important than then when I get out of
stuff myself I you know that I need to I
need to be happy enough enough in order
to be able to speed up service but I
thought but I you know but I I came to a
philosophy for finally that that I
phrased as point eight is enough there
was a TV show once called hate is enough
which was about a you know somebody had
eight kids but but I I say point a is
enough which means if I can have a way
of rating happiness I think it's good
design that to have to have an organism
that's happy about eighty percent of the
time and if it was a hundred percent of
the time it would be like every like
everybody's on drugs and and never and
and and and everything collapses nothing
works because everybody's just too happy
do you think you've achieved that point
eight optimal work there are times when
I when I'm down and I you know and I
think I mean I know that I'm chemically
right I know that I've actually been
programmed to be I to be depressed a
certain amount of time and and and if
that gets out of kilter and I'm more
depressed and you know sometimes like
like I find myself trying to say now who
should I be mad at today there must be a
reason why
but I but then I realize you know it's
just my it's just my chemistry telling
me that I'm supposed to be mad at
somebody and so and so I triggered up
say okay go to sleep and get better but
but if I'm but if I'm not a hundred
percent happy that doesn't mean that I
should find somebody that that's
screaming and and try to size them up
but I'd be like I'm saying you know okay
I'm not 100% happy but but I'm happy
enough to death to be a you know part of
a sustainable situation so so that's
kind of the numerical analysis I do you
invert stores the human life is a point
eight yeah I hope it's okay to talk
about as you talked about previously in
two thousand six six you were diagnosed
with prostate cancer has that encounter
with mortality changed you in some way
or the way you see the world the first
encounter with mortality with Mike when
my dad died and I I went through a month
when I sort of came to kink you know be
comfortable with the fact that I was
going to die someday and during that
month I don't know I I felt okay but I
couldn't sing and you know I and I and I
couldn't do original research either
like tighten right I sort of remember
after three or four weeks the first time
I started having a technical thought
that made sense and was maybe slightly
creative I could sort of feel they know
that and that something was starting to
move again but that was you know so I
felt very empty for until I came to
grips with the I yes I learned that this
is a sort of a standard grief process
that people go through ok so then now
I'm at a point in my life even more so
than in 2006 where where all of my go
have been fulfilled except for finishing
narrative computer programming
i I I had one made unfulfilled goal that
I'd wanted all my life to write a piece
of a piece piece of music that and I had
an idea for for a certain kind of music
that I thought ought to be written at
least somebody ought to try to do it and
I and I felt that it was a that it
wasn't going to be easy but I wanted to
I wanted it proof of concept I wanted to
know if it was going to work or not and
so I spent a lot of time and finally I
finished that piece and we had the we
had the world premiere last year on my
80th birthday and we had another
premiere in Canada and there's talk of
concerts in Europe and various things so
that but that's done it's part of the
world's music now and it's either good
or bad but I did what I was hoping to do
so the only thing that I know that that
I have on my agenda is to is to try to
do as well as I can with the art of
computer programming until I go see now
do you think there's an element of point
eight that might point eight yeah well I
look at it more that I got actually took
21.0 with when that concert was over
with I mean I you know I so in 2006 I
was at point eight um so when I was
diagnosed with prostate cancer then I
said okay well maybe this is yet you
know I've I've had all kinds of good
luck all my life and there's no I'm
nothing to complain about so I might die
now and we'll see what happened and so
so it's quite seriously I went and I
didn't I had no expectation that I
deserved better
I didn't make any plans for the future I
had my surgery I came out of the surgery
and and spend some time learning how to
walk again and so on is painful for a
while but I got home and I realized I
hadn't really thought about what what to
do next I hadn't I hadn't any
expectation and I'm still alive okay now
I can write some more books but it but I
didn't come with the attitude that you
know I you know this was this was
terribly unfair and and I just said okay
I was accepting whatever it turned out
you know I look like I gotten I got more
than my shirt already so why should I
and I didn't and I really when I got
home I read I realized that I had really
not thought about the next step what I
would do after I would doubt after I
would be able to work and I had sort of
thought of it as if as this might you
know I was comfortable with with the
fact that it was at the end but but I
was hoping that I would still you know
be able to learn about satisfiability
and and also someday even write music I
didn't start I didn't started seriously
on the music project until 2012 so I'm
gonna be in huge trouble if I don't talk
to you about this in in the 70s you've
created the tech typesetting system
together with meta font language for
font description and computer modern
family of typefaces that has basically
defined the methodology in the aesthetic
of the countless research fields right
math physics well beyond design and so
on okay well first of all thank you I
think I speak for a lot of people in
saying that but question in terms of
beauty there's a beauty to typography
that you've created and yet beauty is
hard to
five right how does one create beautiful
letters and beautiful equations like
what what
so I mean perhaps there's no words to be
describing you know be described in the
process but so the great Harvard
mathematician Georg deeper cut wrote a
book in the 30s called the aesthetic
measure rate where he would have
pictures of vases and underneath would
be a number and this was how beautiful
the vase was and he had a formula for
this and and he actually also right over
brought about music and so he could he
could you know so I thought maybe I
would part of my musical composition I
would try to program his algorithms and
and you know so that I would I would
write something that had the highest
number by his score well it wasn't quite
rigorous enough work for a computer to
to do but anyway people have tried to
put numerical value on beauty but and
and he did probably the most serious
attempt and and George Gershwin's
teacher also wrote two volumes where he
talked about his method of of composing
music but but you're talking about
another kind of beauty and beauty and
letters and letter fell against and
whatever that overture is right so so
and so that's the beholder as they say
but kinder striving for excellence in
whatever definition you want to give to
beauty then you try to get as close to
that as you can somehow with it I guess
I guess I'm trying to ask and there may
not be a good answer
what loose definitions were you're
operating under with the community of
people that you're working on oh the
loose definition I wanted I wanted it to
appeal to me to me I knew you personally
yeah that's a good start
yeah no and it failed that test went
when I got volume two came out with this
with the new printing and
I was expecting to be the happiest day
of my life and I felt like burning like
how angry I was that I opened the book
and it it was in the same beige covers
and and but but it didn't look right on
the page the number two was particularly
ugly I couldn't stand any page that had
a to in his page number and I was
expecting that it was you know I spent
all this time making measurements and I
and I had Kent had looked at dolphins in
different different ways and I hate I
had great technology but but it did you
know but I but I wasn't done I had I had
to retune the whole thing after 1961
has it ever made you happy finally oh oh
yes
or is it appointing oh no no and so many
books have come out that would never
have been written without this I just
didn't just draw it's just it's a joy
but I could but now I I mean all these
pages that are sitting up there I don't
have a it if I didn't like him I would
change him like that's my nobody else
has this ability they have to stick with
what I gave them
yes so in terms of the other side of it
there's the typography so the look of
the top of the type and the curves and
the lines what about the spacing but
what about the spacing because you know
the white space you know it seems like
you could be a little bit more
systematic about the layout or oh yeah
you can always go further
III I didn't I didn't stop at point
eight I stopped I stopped about point
nine eight seems like you're not
following your own rule for happiness or
is no no no I
there's okay the course there's just
what is the Japanese word wabi-sabi or
something they wear the
the most beautiful works of art are
those that have flaws because then the
person who who perceives them as their
own
appreciation and that gives the viewer
more satisfaction or a so on but but I
but no no with typography I wanted it to
look as good as I could in in the vast
majority of cases and then when it
doesn't then I I say okay that's 2% more
work for the wrote for the author but
but I didn't want to I didn't want to
say that my job was to get 200% with and
take all the work away from the author
that's what I meant by that so if you
were to venture a guess how much of the
nature of reality do you think we humans
understand so you mentioned you
appreciate mystery how much of the world
about us is shrouded in mystery are we
are we if you were to put a number on it
what what percent of it all do we
understand oh we totally how many
leading zeroes any point zero point zero
zero there I don't know now I think it's
infinitesimal how do we think about that
what do we do about that do we continue
one step at a time yeah we muddle
through I mean we do our best we
realized that one that nobody's perfect
then we and we try to keep advancing but
we don't spend time saying we're not
there we're not all the way to the end
some some mathematicians that that would
be in the office next to me when I was
in the math department they would never
think about anything smaller than
countable infinity and I never you know
we intersect that countable infinity
because I really got up to countable
infinity I was always talking about
finite stuff but but even even limiting
to finite stuff which was which is which
the universe might be there's no way to
really know what whether the universe is
in
isn't just made out of capital in
whenever you want to call them quarks or
whatever where capital n is some fun a
number all of the numbers that are
comprehensible are still way smaller
than most almost all finite numbers III
I got this one paper called supernatural
numbers where I what I guess you've
probably ran into something called Knuth
arrow notation did you ever run into
that where anyway so you take the number
I think it's like I and I called it
super K but I named it after myself but
it's it's but in arrow notation is
something like ten and then four arrows
and a three or something might not okay
no the arrow notation if you have if you
have no arrows that means multiplication
XY means x times X times X times X Y
times if you have one arrow that means
exponentiation so x one arrow Y means X
to the X to the X to the X to the X Y
times so I find out by the way that this
is notation was invented by a guy in
1830 and and he was like he was a a a
[Music]
one of the English nobility who who
spent his time thinking about stuff like
this and it was exactly the same concept
that I that I'm that I used arrows and
he used a slightly different notation
but anyway this and then this Ackerman's
function is is based on the same kind of
ideas but Ackerman was 1920s but anyway
you got this number 10
quadruple arrow 3 so that's that says
well we take you know we take 10 to the
10 to the 10 to the 10 to the 10 to the
10th anyway how many times do we do that
oh Ken double arrow two times or
something I mean how tall is that stack
but but but then we do that again
because that was the only 10 triple
quadruple arrow to we take quadruple
three large number it
gets way beyond comprehension okay yeah
and and and so but it's so small
compared to what finite numbers really
are because I want to using four arrows
and you know in ten and a three I mean
let's have that let's have that many
number arrows I mean the boundary
between infinite and finite is
incomprehensible for us humans anyway
infinity is a good is a useful way for
us to think about extremely large
extremely large things and and and and
we we can manipulate it but but we can
never know that the universe is actually
and we're near that so it just so I
realize how little we know but but but
what we we found an awful lot of things
that are too hard for any one person to
know even with even in our small
universe yeah and we did pretty good so
when you go up to heaven and meet God
and get to ask one question that would
get answered what question would you ask
what kind of browser do you have up here
[Laughter]
[Music]
okay and then oh that's beautiful
actually Don thank you so much it was a
huge honor to talk to you I really well
thanks for the gamut of questions yeah
it was fun
thanks for listening to this
conversation with donald knuth thank you
to our presenting sponsor cash app
downloaded use cold Luck's podcast
you'll get ten dollars and ten dollars
will go to first a stem education
nonprofit that inspires hundreds of
thousands of young minds to learn and to
dream of engineering our future if you
enjoy this podcast subscribe on YouTube
give it five stars an apple podcast
supported on patreon or connect with me
on Twitter and now let me leave you with
some words of wisdom from donald knuth
we should continually be striving to
transform every art into a science and
in the process we advance the art thank
you for listening and hope to see you
next time
you