Donald Knuth | AI Podcast by Lex Fridman

[00:00]
the following is a conversation with

[00:01]
donald knuth one of the greatest and

[00:04]
most impactful computer scientists and

[00:06]
mathematicians ever he's the recipient

[00:10]
of the 1974 Turing award considered the

[00:14]
Nobel Prize of computing he's the author

[00:16]
of the multi-volume work the magnum opus

[00:19]
the art of computer programming he made

[00:23]
several key contributions to the

[00:25]
rigorous analysis of computational

[00:27]
complexity of algorithms including the

[00:30]
popularization of asymptotic notation

[00:33]
that we all affectionately know as the

[00:35]
Big O notation he also created the tech

[00:39]
typesetting system which most computer

[00:41]
scientists physicists mathematicians and

[00:44]
scientists and engineers in general used

[00:47]
to write technical papers and make them

[00:49]
look beautiful I can imagine no better

[00:53]
guest to in 2019 with than Don one of

[00:57]
the kindest most brilliant people in our

[00:59]
field this podcast was recorded many

[01:02]
months ago it's one I avoided because

[01:04]
perhaps counter-intuitively the

[01:06]
conversation meant so much to me if you

[01:09]
can believe it I knew even less about

[01:11]
recording back then so the camera angle

[01:13]
is a bit off I hope that's okay with you

[01:15]
the office space was a bit cramped for

[01:18]
filming but it was a magical space Ordon

[01:22]
does most of his work it meant a lot to

[01:24]
me that he would welcome me into his

[01:26]
home it was quite a journey to get there

[01:28]
as many people know he doesn't check

[01:30]
email so I had to get creative the

[01:33]
effort was worth it I've been doing this

[01:36]
podcast on the side for just over a year

[01:38]
sometimes I had to sacrifice a bit of

[01:40]
sleep but always happy to do it and to

[01:42]
be part of an amazing community of

[01:44]
curious minds thank you for your kind

[01:47]
words support for the interesting

[01:49]
discussions and I look forward to many

[01:51]
more of those in 2020 this is the

[01:55]
artificial intelligence podcast if you

[01:57]
enjoy it subscribe on YouTube give it

[02:00]
five stars an Apple podcast follow on

[02:02]
Spotify support on patreon or simply

[02:04]
connect with me on Twitter at lex

[02:06]
friedman spelled fri d-m am

[02:10]
I recently started doing ads at the end

[02:12]
of the introduction I'll do one or two

[02:14]
minutes after introducing the episode

[02:16]
and never any ads in the middle that

[02:18]
break the flow of the conversation I

[02:19]
hope that works for you and doesn't hurt

[02:21]
the listening experience I provide time

[02:24]
stamps for the start of the conversation

[02:25]
that you can skip to but it helps if you

[02:28]
listen to the ad and support this

[02:30]
podcast by trying out the product the

[02:32]
service being advertised this show is

[02:34]
presented by cash app the number one

[02:37]
finance app in the App Store

[02:38]
I personally use cash app to send money

[02:40]
to friends but you can also use it to

[02:43]
buy sell and deposit Bitcoin in just

[02:45]
seconds cash app also has a new

[02:48]
investing feature you can buy a fraction

[02:50]
of a stock say $1 worth no matter what

[02:53]
the stock price is brokerage services

[02:55]
are provided by cash app investing a

[02:57]
subsidiary of square and member s IBC

[03:00]
I'm excited to be working with cash app

[03:03]
to support one of my favorite

[03:04]
organizations called first best known

[03:07]
for their first robotics and Lego

[03:09]
competitions they educate and inspire

[03:11]
hundreds of thousands of students in

[03:14]
over 110 countries and have a perfect

[03:16]
rating and charity navigator which means

[03:18]
that donated money is used to maximum

[03:21]
effectiveness when you get cash app from

[03:24]
the App Store or Google Play

[03:26]
and use code Lex podcast you'll get ten

[03:29]
dollars in cash up will also donate ten

[03:31]
dollars the first which again is an

[03:34]
organization that I've personally seen

[03:35]
inspire girls and boys to dream of

[03:38]
engineering a better world and now

[03:40]
here's my conversation with Donald Knuth

[03:43]
in 1957 atcase tech you were once

[03:50]
allowed to spend several evenings with a

[03:53]
IBM 650 computer as you've talked about

[03:56]
in the past then you fell in love with

[03:57]
computing then

[03:59]
can you take me back to that moment with

[04:02]
the IBM 650 what was it that grabs you

[04:07]
about that computer so the IBM 650 was

[04:11]
this this machine that

[04:14]
well it didn't fill a room but it it was

[04:17]
it was big and noisy but when I first

[04:21]
saw it it was through a window and there

[04:23]
were just a lot of lights flashing on it

[04:25]
and I was a freshman I had a job with

[04:32]
the statistics group and I was supposed

[04:35]
to punch cards and pour data and then

[04:38]
sort them on another machine but then

[04:40]
they got this new computer came in and I

[04:44]
and it had interesting like you know

[04:47]
lights okay so well but I had it kind of

[04:50]
key to the building so I can you know

[04:52]
like I could get in and look at it and

[04:53]
got a manual for it and and my first

[04:57]
experience was based on the fact that I

[04:58]
could punch cards basically would you a

[05:00]
big thing for though deal with thick but

[05:02]
the is
 [6:50 ]was you know big in size but

[05:06]
but incredibly small in power in memory

[05:12]
it had it had 2,000 words of memory and

[05:16]
in a word of memory was 10 decimal

[05:18]
digits plus a sign and it it would do to

[05:22]
add two numbers together you could

[05:24]
probably expect that would take oh say

[05:28]
three milliseconds so that's pretty fast

[05:31]
it's the memories that constraint the

[05:33]
memories the problem that was why it was

[05:35]
three millisecond because it took five

[05:37]
milliseconds for the drum to go around

[05:39]
and you had to wait I don't know five

[05:43]
cycle times if you have an instruction

[05:46]
one position on the drum then it would

[05:49]
be ready to read the data for the

[05:50]
instruction and three notches the drum

[05:55]
is 50 cycles around and you go three

[05:58]
cycles and you can get the data and then

[06:00]
you can go another three cycles and get

[06:02]
and get to next instruction if the

[06:04]
instruction is there otherwise otherwise

[06:06]
you spin until you get to there

[06:08]
play and and we had no random-access

[06:12]
memory whatsoever until my senior year

[06:13]
you see here we got fifty words of

[06:16]
random access memory which were which

[06:17]
were priceless and we would and we would

[06:19]
move stuff up to the up to the random

[06:23]
access memory in 60 word chunks and then

[06:26]
we would start again so it's separating

[06:29]
when to go up there and could you have

[06:31]
predicted the future 60 years later of

[06:35]
computing from then you know in fact the

[06:38]
hardest question I was ever asked was

[06:42]
what could I have predicted in other

[06:44]
words the interviewer asked me she said

[06:47]
you know what about computing has

[06:50]
surprised you you know and immediately I

[06:51]
ran I rattled off a couple dozen things

[06:54]
and inches okay so what didn't surprise

[06:56]
and I was I tried for five minutes to

[07:00]
think of something that I thought I

[07:01]
would have predicted and I and I and I

[07:03]
couldn't but I let me say that this

[07:07]
machine I didn't know well it there

[07:10]
wasn't there wasn't much else in the

[07:12]
world at that time the 650 was the first

[07:14]
machine that was that there were more

[07:17]
than a thousand of ever before that

[07:19]
there were you know there was each

[07:22]
machine there might be a half a dozen

[07:23]
examples maybe my first mass-market

[07:26]
mass-produced the first one yeah done in

[07:30]
quantity and and IBM I didn't sell them

[07:35]
they they rented them but but they they

[07:38]
rented them to universities that at

[07:40]
great you know I had a great deal and

[07:44]
and so that's why a lot of students

[07:48]
learned about computers at that time so

[07:51]
you refer to people including yourself

[07:54]
who gravitate toward a kind of

[07:57]
computational thinking as geeks for at

[08:00]
least I've heard you used that

[08:02]
terminology it true that I think there's

[08:05]
something that happened to me as I was

[08:07]
growing up that made my brain structure

[08:10]
in a certain way that resonates with

[08:12]
with computers so there's the space of

[08:15]
people it's 2% of the population you

[08:17]
empirically estimate that's a prick

[08:21]
it's been proven fairly constant over

[08:23]
most of my career however it might be

[08:27]
different now because kids have

[08:28]
different experiences when they're young

[08:30]
so what does the world look like to a

[08:34]
geek what is what is this aspect of

[08:38]
thinking that is unique to their makes

[08:42]
it yeah that makes a geek this is cuter

[08:47]
the important question in in the 50s

[08:51]
IBM noticed that that there were geeks

[08:57]
and non geeks and so they tried to hire

[08:59]
geeks and they put out as worth papers

[09:01]
saying you know if you play chess come

[09:03]
to Madison Avenue and for an interview

[09:05]
or something like this they were they

[09:06]
were trying for some things so what it

[09:08]
what what is it that I find easy and

[09:11]
other people tend to find harder and and

[09:14]
I think there's two main things one is

[09:17]
this with is ability to jump jump levels

[09:23]
of abstraction so you see something in

[09:27]
the large and you see something in the

[09:30]
small and and can you pass between those

[09:34]
unconsciously so you know that in order

[09:37]
to solve some big problem what you need

[09:41]
to do is add one to a into a certain

[09:44]
register or anything that gets you to

[09:46]
another step and you can and we and

[09:48]
below the yeah I mean I don't go down to

[09:50]
the electron level but I knew what those

[09:53]
milliseconds were what the drum was like

[09:55]
on the 650 I knew how I was gonna factor

[09:59]
her number or or find a root of an

[10:01]
equation or something be alavés because

[10:03]
of what was doing and and as I'm

[10:05]
debugging I'm going through you know did

[10:08]
I make a key punch err did I did I write

[10:12]
the wrong instruction do I have the

[10:13]
wrong wrong thing in a register and each

[10:16]
level at each level it is different and

[10:20]
so this idea of being able to see

[10:23]
something at all at lots of levels and

[10:27]
fluently go between them it seems to me

[10:30]
to be more pronounced much more

[10:32]
pronounced in in the people that

[10:34]
with computers like I got so in my books

[10:38]
I also don't stick after the high level

[10:41]
but but i but i mix low level stuff with

[10:47]
high level and this means that some

[10:50]
people think you know that I that I

[10:54]
should write better books and it's

[10:57]
probably true but but other people say

[11:00]
well but that's if you think like like

[11:03]
that then that's the way to train

[11:04]
yourself like to keep mixing the levels

[11:06]
and and learn more and more how to jump

[11:10]
between so that that's the one thing the

[11:11]
other the other thing is that it's more

[11:14]
of a talent it to be able to deal with

[11:19]
non-uniformity where there's case one

[11:22]
case two case three instead of instead

[11:26]
of having one or two rules that govern

[11:28]
everything so if so it doesn't bother me

[11:32]
if I need like an algorithm has ten

[11:37]
steps to it you know each step is does

[11:39]
something else that doesn't bother me

[11:40]
but a lot of a lot of pure mathematics

[11:43]
is based on one or two rules which which

[11:46]
are universal and and and so this means

[11:49]
that people like me sometimes work with

[11:52]
systems that are more complicated than

[11:54]
necessary because it doesn't bother us

[11:55]
that we don't that we didn't figure out

[11:58]
the simple rule and you mentioned that

[12:01]
while Jacobi boule Abel and all the

[12:05]
mathematicians in 19th century may have

[12:08]
had symptoms of geek the first hundred

[12:12]
percent legit geek was touring Alan

[12:15]
Torrie I I think he had yeah a lot more

[12:17]
of this quality than anyone could from

[12:23]
reading the kind of stuff he didn't so

[12:27]
hot as touring what influence has

[12:31]
touring had on you well well your way

[12:34]
and so I didn't know that aspect of him

[12:38]
until after I graduated some years I it

[12:40]
has undergraduate we had a class that

[12:43]
talked about computability theory and

[12:45]
Turing machines and and that was all it

[12:49]
sounded like a very specific kind of

[12:52]
purely theoretical approach to stuff

[12:55]
so when how old was I when I when I

[12:58]
learned that he thought he had you know

[13:02]
designed when she and that he wrote the

[13:06]
you know you wrote a wonderful manual

[13:09]
for for Manchester machines and and he

[13:13]
invented all the subroutines and and and

[13:19]
he was a real hacker that that he had

[13:22]
his hands dirty

[13:23]
I thought for many years that he had

[13:27]
only done purely formal work as I

[13:31]
started reading his own publications I

[13:32]
could yeah you know I could feel this

[13:34]
kinship and and of course he had a lot

[13:39]
of peculiarities like he wrote numbers

[13:42]
backwards because I mean left to right

[13:46]
to the right to left because that's the

[13:48]
that's it was easier for computers to

[13:50]
process him that way what do you mean

[13:53]
left to right he would write PI as you

[13:57]
know nine five one four point three I

[14:01]
mean okay right forget it for one point

[14:08]
three on the blackboard I mean when he

[14:12]
he we had trained himself to to do that

[14:16]
because the computers he was working

[14:18]
with I worked that way inside trained

[14:21]
himself to think like a computer well

[14:22]
there you go that's nuts geek thinking

[14:26]
you've practiced some of the most

[14:28]
elegant formalism in computer science

[14:30]
and yet you're the creator of a concept

[14:34]
like literate programming which seems to

[14:37]
move closer to natural language type of

[14:41]
description of programming yep yeah

[14:44]
absolutely so how do you see those two

[14:45]
as conflicting as the formalism of

[14:48]
theory and the idea of literate

[14:50]
programming so there we are in a non

[14:53]
uniform system well I don't think one

[14:56]
one-size-fits-all and I don't and I

[14:58]
don't think all truth lies in one in one

[15:02]
kind of expertise and so somehow in a

[15:05]
way you'd say my what my life is a

[15:07]
convex combination of English and

[15:11]
mathematics and you're okay with that

[15:14]
and not only that I think thriving I

[15:16]
wish you know I want my kids to be that

[15:18]
way I want cetera not used left-brain

[15:21]
right-brain at the same time you got a

[15:24]
lot more done that's that was part of

[15:25]
the and I've heard that you didn't

[15:31]
really read for pleasure until into your

[15:33]
30s literature true you know more about

[15:38]
me than I do but I'll try to be

[15:40]
consistent with what you're really ya

[15:41]
know just believe me

[15:42]
yeah just go with whatever story I tell

[15:45]
you it'll be easier that way the

[15:46]
conversation I've heard mentioned a

[15:50]
Philip Roth's American pastoral which I

[15:53]
love as a book I don't know if it was it

[15:58]
was mentioned as something I think that

[15:59]
was meaningful to you as well in either

[16:03]
case what literary books had a lasting

[16:06]
impact on you what okay good so I so I

[16:09]
met Russ already well we both got

[16:14]
doctors from Harvard on the same day so

[16:16]
I so we were yeah we had lunch together

[16:20]
and stuff like that and but he knew that

[16:22]
you know computer books would never sell

[16:24]
well well all right so you say you you

[16:28]
you you're a teenager when you left

[16:32]
Russia so I I have to say that Tolstoy

[16:36]
was one of the big influences on me

[16:38]
I especially like Anna Karenina not

[16:42]
because of a particular area of the plot

[16:46]
of the story where but because there's

[16:51]
this character who you know did the

[16:54]
philosophical discussions it's all it's

[16:58]
a whole way of life is worked out there

[17:02]
it's among the characters until in and

[17:04]
so it that I thought was was especially

[17:07]
beautiful on the other hand does they

[17:09]
have ski I I didn't like at all because

[17:13]
I I felt that he his genius was mostly

[17:16]
because he kept forgetting what he what

[17:17]
he had started out to do and he was just

[17:19]
sloppy I didn't think that that it then

[17:23]
that he polished his stuff at all and

[17:26]
and I tend to admire somebody who who

[17:30]
Todd's the i's and cross the t's so that

[17:32]
the music of the prose this way you

[17:34]
admire more and that I certainly do

[17:37]
admire the music of the language which I

[17:39]
couldn't appreciate in the Russian

[17:41]
original but but I can and Victor Hugo

[17:44]
Glenn's close friendships much his

[17:46]
closer but but Tolstoy I like the same

[17:51]
reason I like Herman Wouk as a as a

[17:53]
novelist I that I think I like his book

[17:58]
Marjorie Morningstar has a similar

[18:00]
character in who who who developed his

[18:02]
own personal philosophy and export and

[18:05]
it called goes in in was consistent yeah

[18:10]
right and it's worth worth pondering uh

[18:14]
so zo like Nietzsche and like what you

[18:18]
don't like Friedrich Nietzsche or age

[18:20]
yeah no no you like this has like I keep

[18:24]
seeing quotations for Nietzsche and and

[18:26]
you never tempt me to read any further

[18:29]
please full of contradictions we will

[18:32]
certainly not appreciate him but

[18:34]
Schiller you know I'm trying to get the

[18:37]
cross what I appreciate in literature

[18:39]
and part of it is the is is as you say

[18:44]
the music of the language of the way it

[18:46]
flows and take Raymond Chandler versus

[18:51]
Dashiell Hammett Dashiell Hammett

[18:53]
sentences are awful and Raymond

[18:56]
Chandler's are beautiful they just flow

[18:59]
so I I don't I don't read literature

[19:04]
because it's supposed to be good for me

[19:07]
or because somebody said it's great but

[19:09]
but it I could find things that I like I

[19:14]
mean you mentioned you address like

[19:17]
James Bond so like I love Ian Fleming I

[19:20]
think he's got a he had a really great

[19:22]
gift for if he has a golf game or game

[19:26]
of bridge or something and this comes

[19:28]
into a story it'll it'll be the most

[19:30]
exciting golf game or or you know the

[19:33]
absolute best possible hands a bridge

[19:36]
that that exists and and any he exploits

[19:41]
it and tells it beautifully as well so

[19:45]
in connecting some things here looking

[19:49]
at literate programming and being able

[19:51]
to it convey encode algorithms to a

[19:59]
computer in a way that mimics how humans

[20:03]
speak how what do you think about

[20:06]
natural language in general and the

[20:08]
messiness of our human world about

[20:11]
trying to express yeah difficult things

[20:14]
so the idea of literate programming is

[20:17]
to is really to try to understand

[20:24]
something better by seeing it from these

[20:26]
two perspectives the formal and the

[20:28]
informal if we try to understand a

[20:31]
complicated thing if we can look at it

[20:33]
in different ways and so this is in fact

[20:36]
the key to technical writing a good

[20:39]
technical writer

[20:40]
try not to be obvious about it but says

[20:42]
everything twice formally and informally

[20:45]
or maybe three times but you try to give

[20:48]
the reader a way to put the concept into

[20:55]
his own brain or her own brain is that

[20:57]
better for the writer or the reader or

[21:00]
both well the writer just tries to

[21:05]
understand the reader that's the goal of

[21:07]
a writer is to have a good mental image

[21:10]
of the reader and to say what the reader

[21:13]
expects next and to to impress the

[21:18]
reader with what has impressed the

[21:19]
writer why something is interesting so

[21:24]
when you have a computer program we try

[21:26]
to instead of looking at it as something

[21:29]
that we're just trying to give an

[21:30]
instruction to the computer what we

[21:32]
really want to be is giving giving

[21:35]
insight to the person who's who's gonna

[21:39]
be maintaining this program or to the

[21:41]
programmer himself when he's debugging

[21:44]
it as to why this stuff is being done

[21:46]
and so all the techniques of exposition

[21:50]
that a teacher uses or book writers make

[21:54]
you better program or if your if your

[21:56]
program is going to be not just a

[21:59]
one-shot deal so how difficult is that

[22:03]
do you see hope for the combination of

[22:07]
informal and formal for the programming

[22:11]
task yeah I I'm the wrong person to ask

[22:14]
I guess because I'm a geek but but I

[22:17]
think for a geek it's easy I don't know

[22:19]
I don't know see not some people have

[22:23]
difficulty writing and that might be

[22:26]
because there's something in their brain

[22:29]
structure that makes it hard for them to

[22:32]
write or or it might be something just

[22:34]
that they haven't had enough practice

[22:35]
I'm not the right one to to uh to judge

[22:39]
but I don't think you teach any person

[22:42]
any particular skill like I do think

[22:45]
that that writing is is half of my life

[22:49]
and so I put it together and let

[22:51]
program he won't even when I'm writing a

[22:53]
one-shot program I I write it in

[22:58]
literate way because I get it right

[23:02]
faster though now does it get compiled

[23:05]
automatically or so I guess on the

[23:09]
technical side my question was how

[23:12]
difficult is a design a system where

[23:15]
much of the programming is done

[23:17]
informally informally yeah informally I

[23:21]
think whatever works to make it

[23:25]
understandable is good but then you have

[23:28]
to also understand how informal is you

[23:33]
have to know the limitations you have to

[23:35]
connect so so by putting the formula and

[23:38]
informal together this this is where

[23:41]
this is where it gets locked into your

[23:43]
into your brain now you can you can say

[23:48]
informally well I'm working on a problem

[23:51]
right now so let's go there I get that

[23:54]
can you give me an example of of

[23:57]
connecting the informal in the formal

[23:59]
well it's a little too complicated an

[24:02]
example there's a puzzle that that's

[24:05]
self referential it's called a Japanese

[24:07]
arrow puzzle and and and you're given a

[24:11]
a bunch of boxes each one points north

[24:14]
east south or west and at the end you're

[24:18]
supposed to fill in each box with the

[24:20]
number of distinct numbers that it

[24:23]
points to so if I put a three in a box

[24:26]
that means that and it's pointing to

[24:29]
five other boxes that means that there's

[24:30]
going to be three different numbers in

[24:32]
those five bucks and and those boxes are

[24:36]
pointing what I might be pointing to me

[24:38]
one of my might be pointing the other

[24:39]
way but anyway I kind of defined a set

[24:44]
of numbers that obeys this complicated

[24:47]
condition that each number counts how

[24:50]
many distinct numbers if it points do

[24:52]
well and still a guy sent me his

[24:57]
solution to this problem where he where

[25:00]
he presents

[25:03]
formal statements that that say either

[25:06]
this is true or this is true this is

[25:07]
true and and and so I try to render that

[25:10]
formal statement informally and I try

[25:14]
say I contain a three and and the guys

[25:20]
I'm pointing to contain the numbers one

[25:23]
two and six so by putting it in formally

[25:26]
and also I converted into a into a

[25:29]
dialogue statement that helps me

[25:32]
understand the logical statement that

[25:35]
he's written down as a string of numbers

[25:37]
in terms of some abstract variables

[25:40]
Eddie yeah

[25:40]
that's really interesting so maybe an

[25:43]
extension of that there has been a

[25:46]
resurgence in computer science and

[25:48]
machine learning and neural networks so

[25:52]
using data to construct algorithms so

[25:56]
it's another way to construct algorithms

[25:58]
really yes you can think of it that way

[26:03]
so as opposed to natural language to

[26:05]
construct algorithms use data to

[26:06]
construct other so what what's the view

[26:10]
of this branch of computer science where

[26:13]
data is almost more important than the

[26:16]
mechanism of the algorithm it seems to

[26:19]
be suited to a certain kind of non geek

[26:23]
and would you know which is probably why

[26:25]
it's it's like it's taken off that it

[26:29]
has its own community that I thought

[26:31]
really that really resonates with that

[26:33]
but it's hard to you know to trust

[26:37]
something like that because nobody even

[26:40]
the people who who work with it that

[26:43]
they have no idea what is what has been

[26:45]
learned that's a really interesting

[26:48]
thought that it's it makes algorithms

[26:53]
more accessible to a different community

[26:56]
a different type of brain yep and that's

[26:59]
really interesting because just like

[27:03]
literate programming perhaps could make

[27:06]
programming more accessible to a certain

[27:09]
kind of brain there are people who think

[27:11]
it's just a matter of Education and

[27:13]
anybody can learn to be a great program

[27:16]
or anybody can

[27:17]
to be a great skier uh yeah you know I I

[27:23]
wish that were true but but I know that

[27:25]
there's a lot of things that I've tried

[27:27]
to do and I and like I was well motivate

[27:30]
an icon and I kept trying to build

[27:33]
myself up and I never got past a certain

[27:35]
level I can't use for example I can't

[27:38]
view three-dimensional objects in my in

[27:43]
my head I have to I have to make a model

[27:45]
and look at it and study it from all

[27:47]
points of view and then I start to get

[27:49]
some idea but other people are good at

[27:52]
four dimensions I mean physicists yeah

[27:57]
so let's go to the art of computer

[28:03]
programming in 1962 you set the table of

[28:07]
contents for this magnum opus right yeah

[28:13]
it was supposed to be a single book for

[28:15]
12 chapters now today what is it

[28:19]
57 years later you're in the middle of

[28:23]
volume 4 of 7 and in the middle of going

[28:27]
for B is 4 B precisely can ask you for

[28:31]
an impossible task which is try to

[28:34]
summarize the book so far maybe by

[28:39]
giving a little examples so from the

[28:42]
sorting and the search in the

[28:43]
combinatorial algorithms if you were to

[28:46]
give a summary a quick elevator summary

[28:51]
yeah right what depending how many

[28:53]
floors that are in the building yes

[28:55]
the first volume called fundamental

[28:57]
algorithms talks about something that

[29:01]
you can't the stuff you can't do without

[29:03]
I guess that you have to know the basic

[29:07]
concepts of what is a program now what

[29:10]
is it what is it algorithm and and and

[29:13]
it also talks about a low-level machine

[29:15]
so you can have some some kind of an

[29:17]
idea what's going on and it has basic

[29:22]
concepts of input/output and subroutines

[29:26]
induction induction writes mathematical

[29:30]
so so the thing that makes my book

[29:33]
different from a lot of others is that

[29:37]
all that I try to not only present the

[29:40]
algún but I try to analyze them and

[29:42]
which means to quantitatively I say not

[29:44]
only does it work but it works this fast

[29:46]
okay and so I need math for them and

[29:49]
then there's the standard way to

[29:51]
structure data inside and represent

[29:53]
information in the computer so that's

[29:56]
all volume 1 volume 2 talks

[29:59]
it's called semi numerical algorithms

[30:01]
and here we're here we're writing

[30:03]
programs but we're also dealing with

[30:06]
numbers algorithms deal with with with

[30:09]
any kinds of objects but but specific

[30:11]
when there's objects or numbers well

[30:13]
then then we have certain special

[30:17]
paradigms that apply to things that have

[30:19]
12 numbers and so there's there's what

[30:21]
there's like there's arithmetic on

[30:24]
numbers and and there's matrices full of

[30:26]
numbers there's random numbers and

[30:29]
there's power series full of numbers

[30:31]
there's different algebraic concepts

[30:34]
that have numbers in structured ways and

[30:37]
the arithmetic in the way a computer

[30:38]
would think about arithmetic is a

[30:40]
floating point floating point arithmetic

[30:42]
a high precision arithmetic not only

[30:45]
addition subtraction multiplication but

[30:47]
also comparison up number

[30:50]
so then check then volume three talks

[30:53]
about I like that one sort insert

[30:55]
sorting a circle of sorting right so so

[30:58]
here you know we're not getting

[30:59]
necessarily with numbers because you

[31:01]
slipped you saw it letters and other

[31:03]
objects and searching we're doing all

[31:04]
the time we googled nowadays but I mean

[31:06]
we have to find stuff

[31:08]
so again algorithms that that underlie

[31:13]
all kinds of applications like you know

[31:16]
none of these volumes it's about a

[31:17]
particular application but the

[31:19]
applications are examples of of why

[31:22]
people want to know about sorting why

[31:23]
people want to know about random numbers

[31:25]
so then volume 4 goes into combinatorial

[31:29]
I'll again this is where we have

[31:32]
zillions of things to deal with and we

[31:35]
and here we keep finding cases where one

[31:41]
good idea can can make something go more

[31:43]
than a million times faster and and and

[31:48]
we're dealing with problems that are

[31:50]
probably never going to be solved

[31:52]
efficiently but that doesn't mean we

[31:55]
give up on them and and and we have this

[31:58]
chance to have good ideas and and go

[32:00]
much much faster on them so so that's

[32:03]
comets are all algorithms and those are

[32:05]
the ones that are yeah I'm using

[32:07]
charting is most fun for you well how

[32:11]
many toriel algorithms are the ones that

[32:14]
I always that I always enjoyed the most

[32:17]
because that's when my skillet

[32:20]
programming had most payoff you know the

[32:23]
different the difference between an

[32:24]
obvious algorithm that you think up

[32:26]
first thing and you know and a good you

[32:29]
know an interesting subtle out algorithm

[32:32]
that not so obvious but but run circles

[32:36]
around the other one that's that's where

[32:39]
computer science 3d comes comes in and

[32:42]
and a lot of these comets are methods

[32:45]
were found first in applications to

[32:49]
artificial intelligence or cryptography

[32:53]
and in my case I I just liked him and it

[32:58]
was associated more with puzzles that

[33:00]
you like the most in the domain of

[33:02]
graphs and graph theory graphs are great

[33:05]
because they're terrific models of so

[33:08]
many things in the real world and and

[33:10]
and and you you throw numbers on a graph

[33:13]
you got a network and so there you're

[33:15]
right there you have but many more

[33:18]
things so but comma toriel in general is

[33:22]
in any arrangement of objects that that

[33:26]
has some kind of a higher structure non

[33:30]
non random structure and it's okay

[33:34]
it is possible to put something together

[33:37]
satisfying all these conditions like I

[33:39]
mentioned arrows a minute ago you know

[33:41]
is there a way to to put these numbers

[33:44]
on a bunch of boxes that that are

[33:46]
pointing to each other is that going to

[33:47]
be possible at all that's volume four

[33:49]
that's volume four what is a sage of

[33:52]
Hawaiian for a was part one and and what

[33:56]
happened was in 1962 when I started

[33:59]
writing down a table of contents it

[34:03]
wasn't going to be a book about computer

[34:06]
programming in general it was going to

[34:07]
be a book about how to write compilers

[34:09]
and I was asked to write a book

[34:13]
explaining how to how to write a

[34:15]
compiler and at that time there were

[34:20]
only a few dozen people in the world who

[34:22]
had written compilers and I happen to be

[34:24]
one of them so and I also had some

[34:29]
experience for writing for like the

[34:33]
campus newspaper and things like that so

[34:35]
so I said okay great I'm the only person

[34:39]
I know who who's written a compiler but

[34:42]
hasn't invented any new techniques for

[34:43]
writing compilers and and all the other

[34:45]
people I knew had super ideas but I

[34:50]
couldn't see that they would be able to

[34:51]
write a book that wouldn't that would

[34:53]
describe anybody else's ideas with their

[34:55]
own so I could be the I could be the

[34:57]
journalist and I could explained what

[34:59]
all these cool ideas about compiler

[35:02]
writing that were and and then I I

[35:06]
started pretty

[35:07]
well yeah let me you need and have a

[35:09]
chapter about data structures you need

[35:11]
to have some introductory material I

[35:13]
want to talk about searching because a

[35:15]
compiler writer has to it has to look up

[35:19]
the variables in a symbol table and find

[35:22]
out you know which which when you when

[35:27]
you write the name of a variable in one

[35:29]
place it's supposed to be the same as

[35:31]
the one you put somewhere else so you

[35:33]
need all these basic techniques and I

[35:35]
and I you know kind of know some

[35:38]
arithmetic to stuff so I throw I threw

[35:40]
in these chapters and I threw in a

[35:42]
chapter on comma talks because that was

[35:46]
what I really enjoyed programming the

[35:48]
most but there weren't many algorithms

[35:49]
and known about combinatorial methods in

[35:51]
1962 so that was a kind of a short

[35:54]
chapter but it was sort of thrown in

[35:56]
just for fun and Chapter twelve was

[35:59]
going to be actual compilers applying

[36:01]
all the stuff in chapters 1 to 11 to

[36:05]
make compilers well ok so that was my

[36:07]
table of contents from 1962 and during

[36:11]
the 70s the whole field of combinatoric

[36:14]
s-- went through a huge explosion people

[36:18]
talk about it comet oil explosion and

[36:20]
they usually mean by that that the

[36:22]
number of cases goes up you know you

[36:25]
change n to n plus 1 and all of a sudden

[36:27]
you your problem has gotten more than

[36:29]
ten times harder but there was an

[36:33]
explosion of ideas about combinatoric

[36:36]
s-- in the 70s and to the point that but

[36:39]
Mike's take 1975 I bet you more than

[36:44]
half of all the journals of computer

[36:45]
science we're about combinatorial method

[36:48]
and what kind of problems were occupying

[36:50]
people's minds what kind of problems in

[36:53]
combinatorics was it's it's that gravity

[36:56]
graph theory yeah gravity was was quite

[36:59]
dominant I mean no but all of the

[37:03]
np-hard problems that you have like

[37:07]
Hamiltonian path or foul sail going

[37:10]
beyond yeah yeah going beyond graphs you

[37:12]
had a operation research whenever it was

[37:16]
a small class of problems that had

[37:18]
efficient solutions and they were

[37:19]
associated with Maitre D' a special

[37:22]
mathematical construction but once we

[37:25]
went to things that involve three things

[37:28]
at a time instead of instead of two all

[37:30]
of a sudden the things got harder so we

[37:32]
had satisfiability problems or if you

[37:35]
have if you have clauses every Clause

[37:38]
has two logical elements in it then we

[37:40]
can satisfy it linear time we can test

[37:43]
for satisfy building linear time but if

[37:45]
you allow yourself three variables in

[37:48]
the clause then nobody knows how to do

[37:52]
it so these articles were about trying

[37:54]
to find better or better ways to to

[37:58]
solve cryptography problems and graph

[38:00]
three problems where the we have lots of

[38:03]
data but we didn't know how to find the

[38:05]
best subset so the data like with

[38:08]
sorting we could get the answer didn't

[38:12]
take long so how did they continue to

[38:14]
change from the 70s to today yeah so now

[38:17]
there may be half a dozen conferences

[38:20]
whose topic is cognate arcs different

[38:24]
kind but fortunately I don't have to

[38:26]
rewrite my book every month you know

[38:28]
like I had to in in the 70 but still

[38:31]
there's huge amount of work being done

[38:33]
and people getting better ideas on these

[38:37]
problems that don't seem to have really

[38:40]
efficient solutions but we can still get

[38:42]
into a lot more with him and so this

[38:45]
book that I'm finishing now is I've got

[38:48]
a whole bunch of brand new methods that

[38:51]
the fires I know there's no other

[38:53]
there's no other book that covers that

[38:57]
covers this particular approach and and

[39:00]
so I'm trying to do my best of exploring

[39:04]
the tip of the iceberg and and and I try

[39:08]
out lots of things and and keep keep

[39:11]
rewriting finding as I find better

[39:14]
better method so what's your writing

[39:17]
process like what's your thinking and

[39:19]
writing process like every day so what's

[39:24]
your routine even

[39:25]
yeah I guess it's actually the best

[39:29]
question because I spent seven days a

[39:31]
week

[39:32]
you're doing it the most prepares to

[39:35]
answer it yeah yeah but okay so the

[39:41]
chair I'm sitting in is where I do

[39:44]
that's where the magic happens well

[39:47]
reading and writing that many chairs

[39:49]
usually sitting over there where I have

[39:50]
other books some reference book but but

[39:53]
I I found his chair which was designed

[39:58]
by a Swedish guy anyway it turns out

[40:01]
this was the only chair I can really sit

[40:02]
in for hours and hours and not know that

[40:04]
I'm in a chair but then I have the

[40:06]
stand-up desk right next next to us and

[40:08]
and so after I write something with

[40:11]
pencil and eraser I get up and I type it

[40:15]
and revise and rewrite the kernel the

[40:21]
idea is first put on paper yep

[40:24]
that's worth right and I call right

[40:27]
maybe five programs a week of course

[40:31]
literate programming and these are

[40:34]
before I describe something in my book I

[40:36]
always program it to see how it's

[40:38]
working and I and I tried a lot so for

[40:42]
example I learned at the end of January

[40:44]
I learned of a breakthrough by for

[40:48]
Japanese people who had extended one of

[40:51]
the one of my methods in in a new

[40:53]
direction and so I I spent the next five

[40:56]
days writing a program to implement what

[40:59]
they did and then I you know but they

[41:01]
had only generalized part of what I had

[41:04]
done so that I had to see if I could

[41:06]
generalize more parts of it and then I

[41:08]
had to take their approach and I had to

[41:11]
I had to try it out on a couple of dozen

[41:13]
of the other problems I had already

[41:15]
worked out with that with my old methods

[41:17]
and so that took another couple of weeks

[41:19]
and then I would you know then I then I

[41:22]
started to see the light nicely and and

[41:26]
I started writing the final draft and

[41:29]
and then I would you know type it up

[41:32]
involves some new mathematical questions

[41:34]
and so I wrote to my friends and might

[41:37]
be good at solving those problems and

[41:39]
and they solve some of them so I put

[41:43]
that in his exercises and and so a month

[41:46]
later I had absorbed one new idea that I

[41:50]
that I learned and you know I'm glad I

[41:53]
heard about it in time otherwise my I

[41:55]
wouldn't put my book out before I heard

[41:57]
about the idea on the other hand this

[41:59]
book was supposed to come in at 300

[42:01]
pages and I'm up to 350 now that added

[42:04]
10 pages to the book but if I learn

[42:07]
about another one I probably first gonna

[42:10]
shoot me well so in the process in that

[42:15]
one month process are some days harder

[42:18]
than others are some days harder than

[42:20]
others well yeah my work is fun but I

[42:23]
also work hard and every big job has

[42:26]
parts that are a lot more fun than

[42:28]
others and so many days I'll say why do

[42:32]
I have to have such high standards like

[42:35]
why couldn't I just be sloppy and not

[42:36]
try this out and you know just just

[42:38]
report the answer but I but I know that

[42:42]
people are conning me to do this and so

[42:45]
okay so okay Donald grit my teeth and do

[42:49]
it and and and then the joy comes out

[42:52]
when I see that actually you know I'm

[42:54]
getting good results and and and I get

[42:56]
and I even more when I see that somebody

[43:00]
has actually read and understood what I

[43:02]
wrote and told me how to make it even

[43:04]
better I did want to mention something

[43:08]
about the about the method so I got this

[43:12]
tablet here where I do the first you

[43:19]
know the first writing of concepts okay

[43:23]
so so and what language I didn't write

[43:28]
so hey take a look at but you know here

[43:30]
random say explain how to draw such

[43:33]
skewed pixel diagrams okay so I got this

[43:36]
paper about 40 years ago when I was

[43:40]
visiting my sister in Canada and they

[43:42]
make tablets of paper with this nice

[43:45]
large size and just the right very small

[43:48]
space between like oh yeah yeah

[43:50]
particularly also just yeah

[43:58]
you know I've got these manuscripts

[44:00]
going back to the 60s and and and those

[44:06]
are when I get my ideas on paper okay

[44:09]
but I'm a good typist in fact I went to

[44:11]
type in school when I was when I was in

[44:14]
high school and so I can type faster

[44:15]
than I think so then when I do the

[44:18]
editing you know stand up and type then

[44:21]
I then I revise this and it comes out a

[44:24]
lot different than what you look for

[44:27]
style and rhythm and things like that

[44:28]
come out at the at the typing state and

[44:30]
you type in tack and I type in tack and

[44:34]
can you can you think in tech No so to a

[44:38]
certain extent I have I have only a

[44:40]
small number of idioms that I use like

[44:44]
you know a beginning or theorem I do

[44:45]
something for displayed equation I do

[44:47]
something and and so on but I but I I

[44:50]
have to see it and in the way that it's

[44:54]
on here yeah right for example touring

[44:56]
wrote what the other direction

[44:59]
you don't write macros you don't think

[45:03]
in macros particularly but when I need a

[45:05]
macro I'll go ahead and and these and do

[45:09]
it but but the thing is they I also

[45:11]
write to fit I mean I'll I'll change

[45:15]
something if I can if I can save a line

[45:17]
I've got you know it's like haiku I'll

[45:19]
figure out a way to rewrite the sentence

[45:21]
so that it'll look better on the page

[45:24]
and I shouldn't be wasting my time on

[45:26]
that but but I can't resist because I

[45:29]
know it's only another three percent of

[45:32]
the time or something like that and it

[45:34]
could also be argued that that is what

[45:36]
life is about

[45:38]
ah yes in fact that's true like like I

[45:43]
worked in the garden one day a week and

[45:45]
that's that's kind of a description of

[45:47]
my life is getting rid of weeds you know

[45:50]
removing bugs for programs in so you

[45:53]
know a lot of writers talk about you

[45:55]
know basically suffering the writing

[45:57]
processes yeah having you know it's

[46:00]
extremely difficult and I think of

[46:02]
programming especially the or technical

[46:05]
writing that you're doing can be like

[46:08]
that do you find yourself

[46:11]
methodologically how do you every day

[46:14]
sit down to do the work is it a

[46:17]
challenge you kind of say it's you know

[46:20]
oh yeah it's fun

[46:24]
but it'd be interesting to hear if there

[46:27]
are non fun parts that you really

[46:29]
struggle with yes the fun comes with

[46:32]
when I'm able to put together ideas of

[46:36]
to two people who didn't know about each

[46:38]
other and and and so I might be the

[46:41]
first person that saw both of their

[46:42]
ideas and so then you know then I get to

[46:46]
make the synthesis and that gives me a

[46:49]
chance to be creative but the dredge

[46:52]
work is where I act I've got a chase

[46:55]
everything down to its root this leads

[46:58]
me into really interesting stuff i mean

[47:00]
like i learned about sanskrit nice yeah

[47:02]
and again you know I try to give credit

[47:05]
to all the authors and so I write like

[47:07]
so I write to people who know that the

[47:11]
people thought as if they're dead I

[47:13]
communicate this way I and I gotta get

[47:17]
the math right and I got a tack all my

[47:19]
programs try to find holes in them and I

[47:23]
rewrite the programs over after I get a

[47:25]
better idea

[47:26]
is there ever dead-ends data and so yeah

[47:29]
I throw stuff out yeah look one of the

[47:32]
things that I spent a lot of time

[47:35]
preparing a major example based on the

[47:38]
game of baseball and I know a lot of

[47:41]
people who for whom baseball is the most

[47:44]
important thing in the world you know

[47:46]
yes but it's but I also know a lot of

[47:47]
people from cricket is the most

[47:49]
important in the world or suck or

[47:52]
something you know and and I realized

[47:55]
that if if I had a big sample I mean it

[47:58]
was gonna have a fold-out illustration

[47:59]
and everything I was saying well what

[48:01]
what am I really teaching about

[48:02]
algorithms here where I had this this is

[48:05]
this baseball example and if I was a

[48:07]
person who who knew only cricket

[48:10]
wouldn't think what would they think

[48:12]
about this and and so I ripped the whole

[48:14]
thing out but I you know I had I had a

[48:17]
something that would really appeal to

[48:19]
people who grew up with baseball as as

[48:21]
has a major theme in their life which is

[48:24]
a lot of people but yeah so I said on

[48:27]
minority the small minority I took out

[48:30]
bowling to

[48:32]
even a smaller my noise what's the art

[48:37]
in the art of programming why why is

[48:42]
there of the few words in the title why

[48:45]
is art one of them yeah well that's

[48:47]
that's what I wrote my Turing lecture

[48:49]
about and and so when people talk about

[48:53]
art it really I mean what the word means

[48:57]
is something that's not a nature so when

[49:02]
you have artificial intelligence that

[49:05]
that art come from the same root saying

[49:09]
that this is something that was created

[49:11]
by by human beings and then it's gotten

[49:16]
a further meaning often a fine art which

[49:19]
has this beauty to the to the mix and

[49:21]
says you know we have things that are

[49:23]
artistically done and and this means not

[49:26]
only done by humans but also done in a

[49:29]
way that's elegant and brings joy and

[49:33]
and has has I guess what

[49:39]
Tolstoy burrs dusky but anyway it it's

[49:46]
that part that that says that it's done

[49:49]
well as well as not only a different

[49:53]
from nature in general then alright is

[49:58]
what human beings are specifically good

[50:01]
at and when they say hey like artificial

[50:03]
intelligence well they're trying to

[50:05]
mimic human beings but there's an

[50:07]
element of fine art and beauty you are

[50:11]
well that's what I that's what I try to

[50:13]
also say that you can write a program

[50:16]
and make a work of art so now in terms

[50:22]
of surprising you know what ideas in

[50:28]
writing from sort and search to the

[50:32]
combinatorial algorithms what ideas have

[50:35]
you come across that were particularly

[50:40]
surprising to you that that change the

[50:44]
way you see a space of

[50:47]
I get a surprise every time I have a bug

[50:49]
in my program but but that isn't really

[50:52]
what your transformational surprises for

[50:57]
example in volume for a I was especially

[51:00]
surprised when I learned about data

[51:03]
structure called B BDD boolean decision

[51:06]
diagram because I sort of had the

[51:10]
feeling that as an old-timer and you

[51:15]
know I've been programming since this

[51:16]
since the 50s and bTW these weren't

[51:21]
invented until 1986 and here comes a

[51:24]
brand new idea that revolutionized the

[51:27]
way to represent a boolean function and

[51:29]
boolean functions are so basic to all

[51:32]
kinds of things in it I mean logically

[51:37]
underlies it everything we can describe

[51:40]
all of what we know in terms of logic

[51:43]
somehow and and here and and

[51:46]
propositional logic I thought that was

[51:51]
cutting Dryden everything was known but

[51:54]
but but he but here comes a Randy Bryant

[51:59]
and oh and discovers that BDDs are

[52:03]
incredibly powerful then then that's all

[52:07]
so I that mean means I have a whole new

[52:11]
section to the book that I never would

[52:13]
have thought of until 1986

[52:15]
not until 1990s when I went when people

[52:18]
started to got to use it for you know

[52:23]
billion dollar of applications and it

[52:26]
was it was the standard way to design

[52:28]
computers for a long time until until

[52:31]
sad solvers came along when in the year

[52:33]
2000 so that's another great big

[52:35]
surprise so uh a lot of these things

[52:38]
have have totally changed the structure

[52:40]
of my book and the middle third of

[52:44]
volume four B's is about that solvers

[52:46]
and that's

[52:49]
300 plus pages which is which is all

[52:53]
about material mostly about material

[52:56]
that was discovered in this century and

[52:59]
I had to start from scratch and meet all

[53:03]
the people in the field and right

[53:05]
I have 15 different sets Alvers that i

[53:07]
wrote while preparing that seven of them

[53:10]
are described in the book others were

[53:13]
for my own experience so newly invented

[53:16]
data structures or ways to represent a

[53:20]
whole new class of algorithm calling you

[53:22]
classified yeah and the interesting

[53:24]
thing about the BD DS was that the

[53:28]
theoretician started looking at it and

[53:31]
started to describe all the things you

[53:33]
couldn't do with BD DS and so they were

[53:37]
getting a bad they were getting a bad

[53:39]
name because you know okay they were

[53:43]
they were useful but they didn't solve

[53:46]
everything I'm sure that the

[53:48]
theoreticians are in the next 10 years

[53:51]
are gonna show why machine learning

[53:54]
doesn't solve everything but I not only

[53:58]
worried about the worst case I get a

[54:00]
huge delight when I can actually solve a

[54:02]
problem that I couldn't solve before

[54:04]
yeah even though I can't solve the

[54:07]
problem that's that it suggests as a

[54:09]
further problem like I know that I'm Way

[54:12]
better than I was before and so I found

[54:14]
out that BD DS could do all kinds of

[54:17]
miraculous things and so I had been

[54:24]
quite a few years learning about the

[54:28]
that territory so in general what brings

[54:32]
you more pleasure in proving or showing

[54:37]
a worst case analysis of an algorithm or

[54:40]
showing a good average case or just

[54:43]
showing a good case that you know

[54:46]
something good pragmatically can be done

[54:47]
with this algorithm yeah I like a good

[54:50]
case that that is maybe only a million

[54:53]
times faster than I was able to do

[54:54]
before but and not worried about the

[54:57]
fact that

[54:58]
and that is still that is still gonna

[55:01]
take too long if I double the size of

[55:03]
the problem so that said you popularize

[55:08]
the asymptotic notation for describing

[55:10]
running time obviously in the analysis

[55:14]
of algorithms worst cases such as such

[55:17]
an important part do you see any aspects

[55:20]
of that kind of analysis is lacking so

[55:24]
and notation - well the main purpose you

[55:28]
have notations that that help us for the

[55:32]
problems we want to solve and so that

[55:33]
they match our they match our intuitions

[55:36]
and people who worked in number theory

[55:38]
had used asymptotic notation in what

[55:41]
Ennis in a certain way but it was only

[55:44]
known to a small group of people and and

[55:46]
I realized that in fact it was very

[55:50]
useful to be able to have a notation for

[55:52]
something that we don't know exactly

[55:54]
what it is but we only know partial

[55:56]
about it and so on stick so for example

[56:00]
instead of Big O notation let's just

[56:02]
let's just take us a much simpler

[56:04]
notation where I say 0 or 1 or 0 1 or 2

[56:09]
and suppose that suppose that when I had

[56:13]
been in high school we would be allowed

[56:15]
to put in the middle of our formula x +

[56:18]
0 1 or 2 equals y okay and then then we

[56:24]
would learn how to multiply two such

[56:27]
expressions together and and you know

[56:30]
deal with them

[56:32]
well the same thing Big O notation says

[56:34]
here's something that's I'm not sure

[56:38]
what it is but I know it's not too big I

[56:40]
know it's not bigger than some constant

[56:43]
times N squared or something like that

[56:44]
fine so I write Big O of N squared and

[56:47]
now I learned how to add Big O of N

[56:49]
squared to Big O of N cubed and I know

[56:51]
how to add Big O of N squared 2 plus

1[56:54]
and square that and how to take

[56:56]
logarithms and Exponential's to have big

[56:58]
O's in the middle of them and that

[57:01]
turned out to be hugely valuable in all

[57:04]
of the work that I was trying to do is

[57:06]
I'm trying to figure out how good

[57:08]
so I have there been algorithms in your

[57:12]
journey that perform very differently in

[57:15]
practice than they do in theory well the

[57:19]
worst case of a comet our logarithm is

[57:21]
almost always horrible but but we have

[57:26]
sad solvers that are solving where one

[57:28]
of the one of the last exercises in that

[57:31]
part of my book was to figure out a

[57:34]
problem that has a hundred variables

[57:37]
that's that's difficult for us at solver

[57:40]
but uh but you would think that a

[57:42]
problem with the hundred boolean

[57:44]
variables has required to do 2 to the

[57:47]
100th operations because that's the

[57:51]
number of possibilities when you have

[57:53]
200 boolean variables in 2 to the 100th

[57:56]
to the 100th is way bigger than then we

[57:59]
can handle 10 to the 17th is a lot

[58:02]
you've mentioned over the past few years

[58:04]
that you believe P may be equal to NP

[58:07]
but that it's not really you know

[58:11]
somebody does prove that P equals NP it

[58:14]
will not directly lead to an actual

[58:16]
algorithm to solve difficult problems

[58:19]
can you explain your intuition here has

[58:21]
it been changed and in general on the

[58:24]
difference between easy and difficult

[58:26]
problems of P and NP and so on yes so

[58:29]
the popular idea is if an algorithm

[58:33]
exists then somebody will find it and

[58:38]
it's just a matter of writing it down

[58:42]
one point well but many more algorithms

[58:47]
exist than anybody can end understand or

[58:51]
ever make you discover yeah because

[58:53]
they're just way beyond human

[58:55]
comprehension of the total number of

[58:57]
algorithms is more than mind-boggling

[59:03]
so so we have situations now where we

[59:06]
know that algorithm exists but we don't

[59:09]
know we don't the foggiest idea what the

[59:11]
algorithms are there's there are simple

[59:14]
examples based on on game playing where

[59:18]
you have

[59:20]
where you say well there must be an

[59:23]
algorithm that exists to win in the game

[59:25]
of hex because for the first player to

[59:28]
win in the game of hex because hex is

[59:31]
always either an a win for the first

[59:33]
player of the second player well what's

[59:35]
the game of hack there's a game of hex

[59:37]
which is which based on putting pebbles

[59:39]
onto a hexagonal board and and the white

[59:42]
player tries to get a light path from

[59:45]
left to right and the black player tries

[59:47]
to get a black path from bottom to top

[59:48]
and how does capture occur just so and

[59:51]
and and there's no capture you just put

[59:53]
levels down what one at a time but

[59:56]
there's no drawers because they after

[59:58]
all the white and black are played

[59:59]
there's either going to be a white path

[60:01]
across from each to west or a black path

[60:03]
from from bottom to top so there's

[60:06]
always you know it's the perfect

[60:08]
information game and people people play

[60:10]
take turns like like tic-tac-toe and hex

[60:16]
or it can be different sizes but we

[60:19]
there's no possibility of a draw and

[60:21]
player to move one at a time and so it's

[60:24]
got to be either a first player win or a

[60:26]
second player win

[60:27]
mathematically you follow out all the

[60:30]
trees and and either either there's

[60:33]
always the win for the percolator

[60:34]
second player okay and it's finite the

[60:37]
game is finite so there's an algorithm

[60:39]
that will decide you can show it has to

[60:42]
be one of the other because the second

[60:44]
player could mimic the first player with

[60:47]
kind of a pairing strategy and so you

[60:50]
can show that it has to be what it has

[60:55]
to be one or that but we don't know any

[60:57]
algorithm no way there there a case

[61:01]
where you can prove the existence of the

[61:05]
solution but we but nobody knows anyway

[61:07]
how to find it but more like the

[61:09]
algorithm question there's a very

[61:13]
powerful theorem and graph theory by

[61:15]
Robinson to see more that says that

[61:18]
every class of graphs that is closed

[61:23]
under taking minors

[61:26]
has a polynomial time algorithm to

[61:29]
determine whether it's in this class or

[61:30]
not now a class of graphs for example

[61:32]
planar graphs these are graphs that you

[61:34]
can draw in a plane without crossing

[61:36]
lines and and a planar graph is close

[61:39]
taking minors means that you can shrink

[61:42]
an edging into a point or you can delete

[61:46]
an edge and so you start with a planar

[61:50]
graph and drink any edge to a point is

[61:52]
still planar deleting edges to a planner

[61:55]
okay now but there are millions of

[62:02]
different ways to describe family of

[62:08]
graph that still is remains the same

[62:12]
undertaking minor and Robertson Nassim

[62:15]
are proved that any such family of

[62:17]
graphs there is a finite number of

[62:20]
minimum graphs that are obstructions so

[62:26]
that if it's not in the family then then

[62:31]
it has to contain then there has to be a

[62:34]
way to shrink it down and until you get

[62:37]
one of these bad minimum graphs that's

[62:39]
not in the family for in plate case for

[62:42]
planar graph the minimum graph is a is a

[62:45]
five-pointed star where there everything

[62:47]
pointed to another and the minimum graph

[62:49]
consisting of trying to connect three

[62:51]
utilities to three houses without

[62:53]
crossing lines and so there are two

[62:55]
there are two bad graphs that are not

[62:57]
planar and every every non planar graph

[63:00]
contains one of these two bad graphs by

[63:03]
by shrinking and he said again so he

[63:09]
proved that there's a finite number of

[63:11]
these bad guys always a finite know

[63:13]
somebody says here's a family it's hard

[63:15]
to believe and they present its sequence

[63:20]
of 20 papers I mean in there it's deep

[63:22]
work but it you know it's because that's

[63:25]
for any arbitrary class so it's for any

[63:28]
arbitrary class that's closed under

[63:29]
taking minors that's closed under maybe

[63:32]
I'm not understanding because it seems

[63:34]
like a lot of them are closed

[63:35]
taking minors almost all the important

[63:37]
classes of graphs are

[63:39]
there are tons of of such graphs but

[63:42]
also hundreds of them that arise in

[63:46]
applications like I have a book over

[63:48]
here called classes of graphs and then

[63:51]
and it it's amazing how many different

[63:56]
classes people have looked at so why do

[63:59]
you bring up this theorem lower this

[64:01]
proof so you know there are lots of

[64:04]
algorithms that that are known for

[64:06]
special class of graphs for example if I

[64:08]
have a certain if I have a chordal graph

[64:10]
then I can color it efficiently if I

[64:13]
have some kinds of graphs it'll make a

[64:16]
great Network very soon like you'd like

[64:19]
to test you somebody gives you a graph

[64:22]
that's always it in this family of grass

[64:24]
if so then I hope then I can I can go to

[64:27]
the library and find an algorithm that's

[64:29]
gonna solve my problem on that graph

[64:32]
okay so we we have we want to have a

[64:35]
graph that says number than that says

[64:41]
give me a graph I'll tell you whether

[64:43]
it's and whether it's in this family or

[64:46]
not okay and so all I have to do is test

[64:51]
whether or not that does this given

[64:54]
graph have a minor that's one of the bad

[64:56]
ones a minor is is everything you can

[64:58]
get by shrinking and removing edges and

[65:01]
given any minor there's a polynomial

[65:03]
time algorithm saying I can tell whether

[65:06]
this is a minor of you and there's a

[65:09]
finite number of bad cases so I just

[65:12]
tried you know does it have this bad

[65:13]
case by polynomial time I got the answer

[65:16]
does he have this bad case probably time

[65:18]
I got the answer a total polynomial time

[65:22]
and so I've solved the problem however

[65:25]
all we know is that the number of minors

[65:27]
is finite we don't know what we might

[65:31]
only know one or two of those minors but

[65:32]
we don't know that if we got it if we

[65:34]
got 20 of them we don't know there might

[65:36]
be 20 125 the Halloween all we know is

[65:40]
that is that it's finite so here we have

[65:43]
a polynomial time algorithm that we

[65:44]
don't know

[65:45]
mm-hm that's a really great example of

[65:47]
what you worry about or why you think P

[65:50]
equals NP won't be useful

[65:52]
but still why do you hold the intuition

[65:56]
that P equals NP because you have to

[66:02]
rule out so many possible algorithms

[66:05]
have been not working you know you can

[66:11]
you can take the graph and you can

[66:13]
represent it as in terms of certain

[66:17]
prime numbers and then you can multiply

[66:19]
those together and then you can then you

[66:21]
can take the bitwise and and and you

[66:25]
know and construct some certain constant

[66:29]
in polynomial time and then that's you

[66:31]
know perfectly valid algorithm and that

[66:33]
there's so many algorithms of that kind

[66:36]
a lot of times we see random you take

[66:42]
data and and and we get coincidences

[66:46]
that that that some fairly random

[66:49]
looking number actually is useful

[66:51]
because because it god it happens to it

[66:57]
happens to self it happens to solve a

[66:59]
problem just because you know there's

[67:02]
there's so many hairs on your head

[67:05]
but it seems like unlikely that two

[67:10]
people are going to have the same number

[67:11]
of hairs on their head but but they're

[67:16]
obvious but you can count how many

[67:17]
people there are and how many hairs on

[67:19]
there so there must be people walking

[67:21]
around in the country to have the same

[67:23]
number of hairs on their head well

[67:24]
that's the kind of a coincidence that

[67:26]
you might say also you know this this

[67:29]
particular combination of operations

[67:31]
just happens to prove that a graph is

[67:34]
has a Hamiltonian path and I see lots of

[67:37]
cases where unexpected things happen

[67:41]
when you have enough enough

[67:42]
possibilities but because the space of

[67:45]
possibility is so huge I have to rule

[67:48]
them all out and so that's the reason

[67:50]
for my intuition is good by no means

[67:52]
approve I mean some people say you know

[67:56]
well P can't equal NP because you've had

[67:59]
all these smart people you know the

[68:03]
smartest designers of algorithms that

[68:05]
have been

[68:06]
wrecking their brains for years and

[68:07]
years and and there's million-dollar

[68:10]
prizes out there and you know none of

[68:11]
them nobody has thought of the algorithm

[68:16]
so it must must be no such job on the

[68:19]
other hand I can use exactly the same

[68:22]
logic and I can say well P must be equal

[68:25]
to NP because there's so many smart

[68:27]
people out here been trying to prove it

[68:28]
unequal to NP and they've all failed you

[68:32]
know this kind of reminds me of the

[68:36]
discussion about the search for aliens

[68:38]
they've been trying to look for them and

[68:40]
we haven't found them yet therefore they

[68:42]
don't exist

[68:42]
yeah but you can show that there's so

[68:45]
many planets out there that they very

[68:46]
possibly could exist yeah and right and

[68:50]
then there's also the possibility that

[68:52]
that they exist but they they all

[68:55]
discovered machine learning or something

[68:57]
and and and then blew each other up well

[69:01]
on that small quick danger

[69:03]
let me ask do you think there's

[69:04]
intelligent life out there in the

[69:05]
universe I have no idea do you hope so

[69:09]
do you think about it it I I don't I

[69:12]
don't spend my time thinking about

[69:14]
things that I could never know really

[69:16]
and yet you do enjoy the fact that there

[69:18]
are many things you don't know you do

[69:20]
enjoy the mystery of things I enjoy the

[69:24]
fact that there that I have limits yeah

[69:26]
but I don't but but I don't take time to

[69:31]
answer unsolvable questions I got it

[69:35]
well because you've taken on some tough

[69:38]
questions that may seem unsolvable you

[69:40]
have taken on some tough questions and

[69:42]
you seem unsolvable if there is because

[69:44]
we are thrilled when I can get further

[69:46]
than I ever thought I could right yeah

[69:48]
but but I don't what much like was

[69:51]
religion these I'm glad the dirt that

[69:54]
that there are no proof that God exists

[69:57]
or not I mean I think it would spoil the

[69:59]
mystery it it would be too dull yeah so

[70:05]
to quickly talk about the other art of

[70:08]
artificial intelligence

[70:10]
what is if you what's your view

[70:13]
you know artificial intelligence

[70:15]
community has developed as part of

[70:17]
computer science and in parallel with

[70:18]
computer science

[70:19]
since the 60s what's your view of the AI

[70:22]
community from the 60s to now so all the

[70:27]
way through it was the people who were

[70:29]
inspired by trying to mimic intelligence

[70:35]
or to do things that that were somehow

[70:37]
the greatest achievements of

[70:39]
intelligence that had been inspiration

[70:41]
to people who have pushed the envelope

[70:43]
of computer science maybe more than any

[70:48]
other group of people so it's all the

[70:51]
way through it's been a great source of

[70:53]
of good problems to to sink teeth into

[70:59]
and and getting getting partial answers

[71:06]
and then more and more successful

[71:08]
answers over the year so this has this

[71:12]
has been the inspiration for lots of the

[71:14]
great discoveries of computer science

[71:16]
are you yourself captivated by the

[71:18]
possibility of creating of algorithms

[71:20]
having echoes of intelligence in them

[71:26]
not as much as most of the people in the

[71:29]
field I guess I would say but but that's

[71:32]
not to say that they're wrong or that

[71:34]
it's just you asked about my own

[71:36]
personal preferences and yeah but but

[71:39]
the thing that I that I worry about is

[71:47]
when people start believing that they've

[71:49]
actually succeeded and because the seems

[71:56]
to me this huge gap between really

[71:59]
understanding something and being able

[72:02]
to pretend to understand something and

[72:05]
give these give the illusion of

[72:06]
understanding something do you think

[72:08]
it's possible to create without

[72:10]
understanding yeah

[72:12]
so to uh I do that all the time to run I

[72:15]
mean that's why I use random members I

[72:18]
like yeah but I but but there's there's

[72:23]
still what this great gap I don't know

[72:25]
certain it's impossible but I'm like but

[72:27]
I don't see a anything coming any closer

[72:31]
to really

[72:33]
the the kind of stuff that I would

[72:36]
consider intelligence say you've

[72:39]
mentioned something that on that line of

[72:41]
thinking which I very much agree with so

[72:45]
the art of computer programming as the

[72:48]
book is focused on single processor

[72:51]
algorithms and for the most part and you

[72:56]
mentioned that's only because I set the

[72:59]
table of contents in 1962 you have to

[73:01]
remember for sure there's no I'm glad I

[73:05]
didn't wait until 1965 or one book maybe

[73:11]
will touch in the Bible but one book

[73:13]
can't always cover the entirety of

[73:15]
everything so I'm glad yeah I'm glad the

[73:20]
the table of contents for the art of

[73:24]
computer programming is what it is but

[73:26]
you did mention that that you thought

[73:29]
that an understanding of the way ant

[73:30]
colonies are able to perform incredibly

[73:33]
organized tasks might well be the key to

[73:36]
understanding human cognition

[73:38]
so these fundamentally distributed

[73:40]
systems so what do you think is the

[73:43]
difference between the way Don Knuth

[73:46]
would sort a list and an ant colony

[73:48]
would sort a list or performing

[73:51]
algorithm sorting a list isn't same as

[73:54]
cognition though but but I know what

[73:57]
you're getting at is well the advantage

[74:00]
of ant colony at least we can see what

[74:04]
they're doing we we know which ant has

[74:06]
talked to which other ant and and and

[74:08]
and it's much harder with the quick

[74:11]
brains to just to know how to what

[74:14]
extent of neurons are passing signal so

[74:18]
I understand that aunt Connie might be a

[74:21]
if they have the secret of cognition

[74:24]
think of an ant colony as a cognitive

[74:27]
single being rather than as a colony of

[74:31]
lots of different ants I mean just like

[74:32]
the cells of our brain are and and the

[74:37]
microbiome and all that is interacting

[74:41]
entities but but somehow I consider

[74:46]
myself to be

[74:46]
single person well you know aunt Connie

[74:50]
you can say might be cognitive is

[74:54]
somehow and it's yeah I mean you know I

[74:57]
okay I like I smash a certain aunt and

[75:03]
mmm that's stung what was that right you

[75:06]
know but if we're going to crack the the

[75:08]
the secret of cognition it might be that

[75:11]
we could do so by but my psyche note how

[75:16]
ants do it because we have a better

[75:18]
chance to measure and they're

[75:19]
communicating by pheromones and by

[75:21]
touching each other and sight but but

[75:24]
not by much more subtle phenomenon Mike

[75:27]
electric currents going through but even

[75:30]
a simpler version of that what are your

[75:32]
thoughts of maybe Conway's Game of Life

[75:34]
okay so Conway's Game of Life is is able

[75:39]
to simulate any any computable process

[75:43]
and any deterministic process is like

[75:47]
how you went there I mean that's not its

[75:49]
most powerful thing I would say I mean

[75:54]
you can simulate it but the magic is

[75:58]
that the individual units are

[76:00]
distributed yes and extremely simple yes

[76:03]
we can we understand exactly what the

[76:06]
primitives are the permit is the just

[76:07]
like with the anthology even simple but

[76:09]
if we but still it doesn't say that I

[76:12]
understand I understand life I mean I

[76:16]
understand it it gives me an it gives me

[76:23]
a better insight into what does it mean

[76:24]
to to have a deterministic universe what

[76:30]
does it mean to to have free choice for

[76:34]
example do you think God plays dice yes

[76:38]
I don't see any reason why God should be

[76:40]
forbidden from using the most efficient

[76:42]
ways to to to I mean we we know that

[76:51]
dice are extremely important and

[76:53]
inefficient algorithms there are things

[76:55]
like that couldn't be done well without

[76:57]
randomness and so I don't see any reason

[76:59]
why

[77:00]
my god should be prohibited but when the

[77:03]
when the algorithm requires it

[77:05]
you don't see why the know the physics

[77:09]
should constrain it yeah

[77:11]
so in 2001 you gave a series of lectures

[77:13]
at MIT about religion and science

[77:17]
well that would 1999 but you published

[77:19]
the book came out in Cooper so in 1999

[77:23]
you spent a little bit of time in Boston

[77:26]
enough to give those lectures yeah and I

[77:31]
read in the 2001 version that most of it

[77:36]
it's quite fascinating read I recommend

[77:37]
people its transcription of your

[77:39]
lectures so what did you learn about how

[77:43]
ideas get started and grow from studying

[77:45]
the history of the Bible sieve

[77:47]
rigorously studied a very particular

[77:49]
part of the Bible what did you learn

[77:52]
from this process about the way us human

[77:54]
beings as a society develop and grow

[77:57]
ideas share ideas and I'm by those idea

[78:01]
I I tried to summarize that I wouldn't

[78:05]
say that I that I learned a great deal

[78:08]
of really definite things like right

[78:10]
where I could make conclusions but I

[78:12]
learned more about what I don't know you

[78:15]
have a complex subject which is really

[78:17]
beyond human understanding so so we give

[78:22]
up on saying I'm never going to get to

[78:24]
the end of the road and I'm never going

[78:25]
to understand it but you say but but

[78:27]
maybe it might be good for me to to get

[78:31]
closer and closer and learn more about

[78:33]
more and more about something and so you

[78:35]
know oh how can I do that efficiently

[78:38]
and the answer is well use randomness

[78:43]
and so to try a random subset of the

[78:49]
that that is within my grasp and and and

[78:53]
and study that in detail instead of just

[78:57]
studying parts that somebody tells me to

[79:00]
study or instead of studying nothing

[79:03]
because it's too hard so I I i decided

[79:11]
for my own amusement that one ones that

[79:14]
I would I would take a subset of the of

[79:18]
the verses of the Bible

[79:21]
and I would try to find out what the

[79:25]
best thinkers have said about that small

[79:28]
subset and I had had about let's say 660

[79:32]
verses out of out of 3,000 I think it's

[79:35]
one out of 500 or something like this

[79:37]
and so then I went to the libraries

[79:39]
which which are well indexed uh you can

[79:42]
you you know I spent for example at at

[79:46]
Boston Public Library I I would go once

[79:49]
a week for a year and I went to I went I

[79:54]
have done time stuff and over Harvard

[79:57]
library to look at this yes that weren't

[80:01]
in the Boston Public where they where

[80:04]
scholars had looked at and you can call

[80:06]
in the eight and you can go down the

[80:08]
shelves and and you can pretty you can

[80:11]
look at the index and say oh there it is

[80:12]
this verse I mentioned anywhere in this

[80:15]
book if so look at page 105 so I was

[80:18]
like I could learn not only about the

[80:20]
Bible but about the secondary literature

[80:22]
about the Bible the things that scholars

[80:24]
have written about it and so that that

[80:26]
gave me a way to uh to zoom in on parts

[80:32]
of the things so that I could get more

[80:34]
more insight and and so I look at it as

[80:37]
a way of giving me some firm pegs which

[80:43]
icon which I could hang pieces of

[80:44]
information but not as as things where I

[80:47]
would say and therefore this is true in

[80:50]
this random approach of sampling the

[80:54]
Bible what did you learn about the the

[80:58]
most you know central oh one of the

[81:03]
biggest accumulation of ideas you know

[81:05]
to me that the that the main thrust was

[81:08]
not the one that most people think of as

[81:11]
saying you know you know don't have sex

[81:13]
or something like this but that the main

[81:16]
thrust was to try to to try to figure

[81:22]
out how to live in harmony

[81:24]
with God's wishes I'm assuming that God

[81:27]
exists and I say I'm glad that I that

[81:31]
there's no way to prove this because

[81:32]
that would that would I would run

[81:36]
through the proof once and then I'd

[81:37]
forget it and and it would and and I

[81:40]
would never just speculate about

[81:44]
spiritual things and mysteries otherwise

[81:48]
and I think my life would be very

[81:50]
incomplete so I so I'm assuming that God

[81:55]
exists but it if but a lot of things the

[81:59]
people say God doesn't exist but that's

[82:02]
still important to them and so in a way

[82:04]
in a way that might still be other God

[82:07]
is there or not in some sense so it it

[82:11]
guys important to them it's one of the

[82:14]
one of the verses I studied act is you

[82:17]
can interpret as saying you know it's

[82:19]
much better to be an atheist that not to

[82:22]
care at all so I would say it's yeah

[82:26]
it's similar to the P equals NP

[82:27]
discussion yeah you you mentioned a

[82:30]
mental exercise that I'd love it if you

[82:33]
could partake in yourself a mental

[82:37]
exercise of being God and so how would

[82:39]
you if you were God dot Knuth how would

[82:42]
you present yourself to the people of

[82:43]
Earth you mentioned your love of

[82:47]
literature and there was it there's this

[82:48]
book that would that really uh I can

[82:50]
recommend to you if I can't think yeah

[82:53]
the title I think is blasphemy it talks

[82:56]
about God revealing himself through a

[82:58]
computer in in in Los Alamos and and it

[83:06]
it's the only book that I've ever read

[83:09]
where the punchline was really the very

[83:13]
last word of the book and it explained

[83:16]
the whole idea of the book and so I

[83:18]
don't want to give that away but it but

[83:21]
it's really very much about this

[83:22]
question that that she raised

[83:26]
but but suppose God said okay that my

[83:31]
previous on means of communication with

[83:35]
the world are and not the best for the

[83:37]
21st century so what should I do now and

[83:40]
and and it's conceivable that that it

[83:45]
would that that God would choose the way

[83:48]
that's described in this book and

[83:50]
another way to look at this exercise is

[83:52]
looking at the human mind looking at the

[83:55]
human spirit the human life in a

[83:57]
systematic way I think it mostly you

[84:00]
want to learn humility you want to

[84:02]
realize that once we solve one problem

[84:03]
that doesn't mean it worked at all so no

[84:06]
other problems are going to drop out and

[84:08]
and and and we have to realize that that

[84:15]
that there are there are things beyond

[84:17]
our beyond our ability I see hubris all

[84:24]
around yeah well said if you were to run

[84:29]
program analysis on your own life how

[84:33]
did you do in terms of correctness

[84:35]
running time resource use asymptotically

[84:39]
speaking of course okay yeah well I

[84:42]
would say that question has not been

[84:46]
asked me before and i i i started out

[84:57]
with library subroutines and and

[85:04]
learning how to be a automaton that was

[85:07]
obedient and i had the great advantage

[85:10]
that i didn't have anybody to blame for

[85:14]
my failures if I started getting not

[85:20]
understanding something I I knew that I

[85:23]
should stop playing ping pong and that

[85:24]
was that into it was my fault that I was

[85:26]
that I wasn't studying hard enough or

[85:28]
something rather than that somebody was

[85:30]
discriminating against me in some way

[85:32]
and

[85:33]
I don't know how to avoid this the

[85:37]
existence of biases in the world but i

[85:38]
but i but i know that that's an extra

[85:41]
burden that i didn't have to suffer from

[85:45]
and and and then i I found the from from

[85:54]
parents I learned the idea of of

[85:58]
altruist to other people as being more

[86:03]
important than then when I get out of

[86:08]
stuff myself I you know that I need to I

[86:11]
need to be happy enough enough in order

[86:16]
to be able to speed up service but I

[86:18]
thought but I you know but I I came to a

[86:21]
philosophy for finally that that I

[86:23]
phrased as point eight is enough there

[86:29]
was a TV show once called hate is enough

[86:31]
which was about a you know somebody had

[86:33]
eight kids but but I I say point a is

[86:38]
enough which means if I can have a way

[86:41]
of rating happiness I think it's good

[86:45]
design that to have to have an organism

[86:51]
that's happy about eighty percent of the

[86:53]
time and if it was a hundred percent of

[86:58]
the time it would be like every like

[87:00]
everybody's on drugs and and never and

[87:02]
and and and everything collapses nothing

[87:06]
works because everybody's just too happy

[87:08]
do you think you've achieved that point

[87:10]
eight optimal work there are times when

[87:13]
I when I'm down and I you know and I

[87:17]
think I mean I know that I'm chemically

[87:19]
right I know that I've actually been

[87:21]
programmed to be I to be depressed a

[87:26]
certain amount of time and and and if

[87:28]
that gets out of kilter and I'm more

[87:30]
depressed and you know sometimes like

[87:32]
like I find myself trying to say now who

[87:34]
should I be mad at today there must be a

[87:36]
reason why

[87:38]
but I but then I realize you know it's

[87:41]
just my it's just my chemistry telling

[87:43]
me that I'm supposed to be mad at

[87:45]
somebody and so and so I triggered up

[87:47]
say okay go to sleep and get better but

[87:50]
but if I'm but if I'm not a hundred

[87:53]
percent happy that doesn't mean that I

[87:56]
should find somebody that that's

[87:57]
screaming and and try to size them up

[88:00]
but I'd be like I'm saying you know okay

[88:04]
I'm not 100% happy but but I'm happy

[88:08]
enough to death to be a you know part of

[88:11]
a sustainable situation so so that's

[88:15]
kind of the numerical analysis I do you

[88:21]
invert stores the human life is a point

[88:24]
eight yeah I hope it's okay to talk

[88:27]
about as you talked about previously in

[88:29]
two thousand six six you were diagnosed

[88:32]
with prostate cancer has that encounter

[88:35]
with mortality changed you in some way

[88:38]
or the way you see the world the first

[88:42]
encounter with mortality with Mike when

[88:44]
my dad died and I I went through a month

[88:47]
when I sort of came to kink you know be

[88:56]
comfortable with the fact that I was

[88:57]
going to die someday and during that

[88:59]
month I don't know I I felt okay but I

[89:06]
couldn't sing and you know I and I and I

[89:11]
couldn't do original research either

[89:14]
like tighten right I sort of remember

[89:16]
after three or four weeks the first time

[89:19]
I started having a technical thought

[89:21]
that made sense and was maybe slightly

[89:23]
creative I could sort of feel they know

[89:25]
that and that something was starting to

[89:28]
move again but that was you know so I

[89:31]
felt very empty for until I came to

[89:35]
grips with the I yes I learned that this

[89:39]
is a sort of a standard grief process

[89:40]
that people go through ok so then now

[89:43]
I'm at a point in my life even more so

[89:47]
than in 2006 where where all of my go

[89:50]
have been fulfilled except for finishing

[89:52]
narrative computer programming

[89:54]
i I I had one made unfulfilled goal that

[90:01]
I'd wanted all my life to write a piece

[90:04]
of a piece piece of music that and I had

[90:08]
an idea for for a certain kind of music

[90:12]
that I thought ought to be written at

[90:13]
least somebody ought to try to do it and

[90:15]
I and I felt that it was a that it

[90:19]
wasn't going to be easy but I wanted to

[90:20]
I wanted it proof of concept I wanted to

[90:24]
know if it was going to work or not and

[90:25]
so I spent a lot of time and finally I

[90:29]
finished that piece and we had the we

[90:31]
had the world premiere last year on my

[90:34]
80th birthday and we had another

[90:36]
premiere in Canada and there's talk of

[90:39]
concerts in Europe and various things so

[90:41]
that but that's done it's part of the

[90:44]
world's music now and it's either good

[90:45]
or bad but I did what I was hoping to do

[90:49]
so the only thing that I know that that

[90:53]
I have on my agenda is to is to try to

[90:58]
do as well as I can with the art of

[91:00]
computer programming until I go see now

[91:02]
do you think there's an element of point

[91:05]
eight that might point eight yeah well I

[91:08]
look at it more that I got actually took

[91:13]
21.0 with when that concert was over

[91:18]
with I mean I you know I so in 2006 I

[91:25]
was at point eight um so when I was

[91:28]
diagnosed with prostate cancer then I

[91:30]
said okay well maybe this is yet you

[91:33]
know I've I've had all kinds of good

[91:37]
luck all my life and there's no I'm

[91:39]
nothing to complain about so I might die

[91:41]
now and we'll see what happened and so

[91:45]
so it's quite seriously I went and I

[91:49]
didn't I had no expectation that I

[91:54]
deserved better

[91:56]
I didn't make any plans for the future I

[91:59]
had my surgery I came out of the surgery

[92:03]
and and spend some time learning how to

[92:09]
walk again and so on is painful for a

[92:13]
while but I got home and I realized I

[92:17]
hadn't really thought about what what to

[92:20]
do next I hadn't I hadn't any

[92:22]
expectation and I'm still alive okay now

[92:27]
I can write some more books but it but I

[92:29]
didn't come with the attitude that you

[92:30]
know I you know this was this was

[92:34]
terribly unfair and and I just said okay

[92:39]
I was accepting whatever it turned out

[92:43]
you know I look like I gotten I got more

[92:48]
than my shirt already so why should I

[92:54]
and I didn't and I really when I got

[92:58]
home I read I realized that I had really

[93:00]
not thought about the next step what I

[93:01]
would do after I would doubt after I

[93:03]
would be able to work and I had sort of

[93:05]
thought of it as if as this might you

[93:08]
know I was comfortable with with the

[93:11]
fact that it was at the end but but I

[93:14]
was hoping that I would still you know

[93:18]
be able to learn about satisfiability

[93:23]
and and also someday even write music I

[93:29]
didn't start I didn't started seriously

[93:31]
on the music project until 2012 so I'm

[93:35]
gonna be in huge trouble if I don't talk

[93:37]
to you about this in in the 70s you've

[93:41]
created the tech typesetting system

[93:43]
together with meta font language for

[93:45]
font description and computer modern

[93:47]
family of typefaces that has basically

[93:50]
defined the methodology in the aesthetic

[93:53]
of the countless research fields right

[93:57]
math physics well beyond design and so

[94:02]
on okay well first of all thank you I

[94:04]
think I speak for a lot of people in

[94:07]
saying that but question in terms of

[94:10]
beauty there's a beauty to typography

[94:12]
that you've created and yet beauty is

[94:16]
hard to

[94:16]
five right how does one create beautiful

[94:22]
letters and beautiful equations like

[94:25]
what what

[94:26]
so I mean perhaps there's no words to be

[94:30]
describing you know be described in the

[94:33]
process but so the great Harvard

[94:38]
mathematician Georg deeper cut wrote a

[94:43]
book in the 30s called the aesthetic

[94:44]
measure rate where he would have

[94:47]
pictures of vases and underneath would

[94:49]
be a number and this was how beautiful

[94:51]
the vase was and he had a formula for

[94:53]
this and and he actually also right over

[94:56]
brought about music and so he could he

[94:59]
could you know so I thought maybe I

[95:01]
would part of my musical composition I

[95:04]
would try to program his algorithms and

[95:08]
and you know so that I would I would

[95:11]
write something that had the highest

[95:13]
number by his score well it wasn't quite

[95:15]
rigorous enough work for a computer to

[95:18]
to do but anyway people have tried to

[95:21]
put numerical value on beauty but and

[95:24]
and he did probably the most serious

[95:28]
attempt and and George Gershwin's

[95:32]
teacher also wrote two volumes where he

[95:34]
talked about his method of of composing

[95:38]
music but but you're talking about

[95:40]
another kind of beauty and beauty and

[95:42]
letters and letter fell against and

[95:44]
whatever that overture is right so so

[95:47]
and so that's the beholder as they say

[95:52]
but kinder striving for excellence in

[95:55]
whatever definition you want to give to

[95:57]
beauty then you try to get as close to

[95:59]
that as you can somehow with it I guess

[96:02]
I guess I'm trying to ask and there may

[96:04]
not be a good answer

[96:06]
what loose definitions were you're

[96:09]
operating under with the community of

[96:11]
people that you're working on oh the

[96:13]
loose definition I wanted I wanted it to

[96:18]
appeal to me to me I knew you personally

[96:21]
yeah that's a good start

[96:23]
yeah no and it failed that test went

[96:25]
when I got volume two came out with this

[96:28]
with the new printing and

[96:30]
I was expecting to be the happiest day

[96:31]
of my life and I felt like burning like

[96:37]
how angry I was that I opened the book

[96:40]
and it it was in the same beige covers

[96:44]
and and but but it didn't look right on

[96:47]
the page the number two was particularly

[96:52]
ugly I couldn't stand any page that had

[96:54]
a to in his page number and I was

[96:57]
expecting that it was you know I spent

[96:59]
all this time making measurements and I

[97:01]
and I had Kent had looked at dolphins in

[97:05]
different different ways and I hate I

[97:08]
had great technology but but it did you

[97:12]
know but I but I wasn't done I had I had

[97:16]
to retune the whole thing after 196

1[97:19]
has it ever made you happy finally oh oh

[97:22]
yes

[97:24]
or is it appointing oh no no and so many

[97:27]
books have come out that would never

[97:29]
have been written without this I just

[97:31]
didn't just draw it's just it's a joy

[97:34]
but I could but now I I mean all these

[97:37]
pages that are sitting up there I don't

[97:40]
have a it if I didn't like him I would

[97:43]
change him like that's my nobody else

[97:47]
has this ability they have to stick with

[97:49]
what I gave them

[97:50]
yes so in terms of the other side of it

[97:53]
there's the typography so the look of

[97:55]
the top of the type and the curves and

[97:57]
the lines what about the spacing but

[98:01]
what about the spacing because you know

[98:04]
the white space you know it seems like

[98:07]
you could be a little bit more

[98:08]
systematic about the layout or oh yeah

[98:12]
you can always go further

[98:13]
III I didn't I didn't stop at point

[98:17]
eight I stopped I stopped about point

[98:19]
nine eight seems like you're not

[98:22]
following your own rule for happiness or

[98:25]
is no no no I

[98:29]
there's okay the course there's just

[98:32]
what is the Japanese word wabi-sabi or

[98:35]
something they wear the

[98:38]
the most beautiful works of art are

[98:40]
those that have flaws because then the

[98:42]
person who who perceives them as their

[98:46]
own

[98:47]
appreciation and that gives the viewer

[98:50]
more satisfaction or a so on but but I

[98:54]
but no no with typography I wanted it to

[98:57]
look as good as I could in in the vast

[99:00]
majority of cases and then when it

[99:03]
doesn't then I I say okay that's 2% more

[99:08]
work for the wrote for the author but

[99:11]
but I didn't want to I didn't want to

[99:14]
say that my job was to get 200% with and

[99:18]
take all the work away from the author

[99:20]
that's what I meant by that so if you

[99:23]
were to venture a guess how much of the

[99:27]
nature of reality do you think we humans

[99:29]
understand so you mentioned you

[99:32]
appreciate mystery how much of the world

[99:35]
about us is shrouded in mystery are we

[99:38]
are we if you were to put a number on it

[99:41]
what what percent of it all do we

[99:44]
understand oh we totally how many

[99:46]
leading zeroes any point zero point zero

[99:48]
zero there I don't know now I think it's

[99:50]
infinitesimal how do we think about that

[99:53]
what do we do about that do we continue

[99:55]
one step at a time yeah we muddle

[99:58]
through I mean we do our best we

[100:01]
realized that one that nobody's perfect

[100:03]
then we and we try to keep advancing but

[100:07]
we don't spend time saying we're not

[100:12]
there we're not all the way to the end

[100:14]
some some mathematicians that that would

[100:18]
be in the office next to me when I was

[100:19]
in the math department they would never

[100:21]
think about anything smaller than

[100:23]
countable infinity and I never you know

[100:26]
we intersect that countable infinity

[100:28]
because I really got up to countable

[100:31]
infinity I was always talking about

[100:32]
finite stuff but but even even limiting

[100:36]
to finite stuff which was which is which

[100:40]
the universe might be there's no way to

[100:43]
really know what whether the universe is

[100:47]
in

[100:48]
isn't just made out of capital in

[100:56]
whenever you want to call them quarks or

[100:59]
whatever where capital n is some fun a

[101:01]
number all of the numbers that are

[101:03]
comprehensible are still way smaller

[101:05]
than most almost all finite numbers III

[101:08]
I got this one paper called supernatural

[101:13]
numbers where I what I guess you've

[101:16]
probably ran into something called Knuth

[101:18]
arrow notation did you ever run into

[101:19]
that where anyway so you take the number

[101:22]
I think it's like I and I called it

[101:25]
super K but I named it after myself but

[101:29]
it's it's but in arrow notation is

[101:31]
something like ten and then four arrows

[101:34]
and a three or something might not okay

[101:36]
no the arrow notation if you have if you

[101:40]
have no arrows that means multiplication

[101:41]
XY means x times X times X times X Y

[101:46]
times if you have one arrow that means

[101:49]
exponentiation so x one arrow Y means X

[101:51]
to the X to the X to the X to the X Y

[101:55]
times so I find out by the way that this

[101:58]
is notation was invented by a guy in

[102:02]
1830 and and he was like he was a a a

[102:08]
[Music]

[102:10]
one of the English nobility who who

[102:13]
spent his time thinking about stuff like

[102:14]
this and it was exactly the same concept

[102:18]
that I that I'm that I used arrows and

[102:21]
he used a slightly different notation

[102:23]
but anyway this and then this Ackerman's

[102:25]
function is is based on the same kind of

[102:28]
ideas but Ackerman was 1920s but anyway

[102:31]
you got this number 10

[102:34]
quadruple arrow 3 so that's that says

[102:37]
well we take you know we take 10 to the

[102:41]
10 to the 10 to the 10 to the 10 to the

[102:44]
10th anyway how many times do we do that

[102:46]
oh Ken double arrow two times or

[102:49]
something I mean how tall is that stack

[102:51]
but but but then we do that again

[102:54]
because that was the only 10 triple

[102:56]
quadruple arrow to we take quadruple

[102:59]
three large number it

[103:01]
gets way beyond comprehension okay yeah

[103:06]
and and and so but it's so small

[103:11]
compared to what finite numbers really

[103:13]
are because I want to using four arrows

[103:15]
and you know in ten and a three I mean

[103:18]
let's have that let's have that many

[103:21]
number arrows I mean the boundary

[103:23]
between infinite and finite is

[103:26]
incomprehensible for us humans anyway

[103:29]
infinity is a good is a useful way for

[103:32]
us to think about extremely large

[103:36]
extremely large things and and and and

[103:42]
we we can manipulate it but but we can

[103:46]
never know that the universe is actually

[103:49]
and we're near that so it just so I

[103:57]
realize how little we know but but but

[104:03]
what we we found an awful lot of things

[104:09]
that are too hard for any one person to

[104:11]
know even with even in our small

[104:13]
universe yeah and we did pretty good so

[104:17]
when you go up to heaven and meet God

[104:19]
and get to ask one question that would

[104:23]
get answered what question would you ask

[104:29]
what kind of browser do you have up here

[104:32]
[Laughter]

[104:41]
[Music]

[104:48]
okay and then oh that's beautiful

[104:51]
actually Don thank you so much it was a

[104:54]
huge honor to talk to you I really well

[104:56]
thanks for the gamut of questions yeah

[104:59]
it was fun

[105:00]
thanks for listening to this

[105:01]
conversation with donald knuth thank you

[105:04]
to our presenting sponsor cash app

[105:07]
downloaded use cold Luck's podcast

[105:09]
you'll get ten dollars and ten dollars

[105:11]
will go to first a stem education

[105:13]
nonprofit that inspires hundreds of

[105:15]
thousands of young minds to learn and to

[105:18]
dream of engineering our future if you

[105:21]
enjoy this podcast subscribe on YouTube

[105:23]
give it five stars an apple podcast

[105:25]
supported on patreon or connect with me

[105:27]
on Twitter and now let me leave you with

[105:30]
some words of wisdom from donald knuth

[105:33]
we should continually be striving to

[105:35]
transform every art into a science and

[105:38]
in the process we advance the art thank

[105:43]
you for listening and hope to see you

[105:45]
next time