Kind: captions
Language: en
the following is a conversation with
donald knuth his second time on this
podcast
don is a legendary computer scientist
touring award winner
father of algorithm analysis
author of the art of computer
programming creator of tech that led to
late tech and one of the kindest and
most fascinating human beings i've ever
got a chance to talk to
i wrote him a letter a long time ago he
responded and the rest as they say is
history we've interacted many times
since then and every time it's been
joyful and inspiring
to support this podcast please check out
our sponsors in the description
this is the lex friedman podcast and
here is my conversation with donald
knuth
your first large-scale program you wrote
it in ibm 650 assembler in the summer of
1957. i wrote it in decimal machine
language i didn't know about assembler
until a year later but the year 1957 the
year and the program
yeah i might have learned about it
assembler later that summary i probably
did in 1957 hardly anybody had heard of
assemblers you looked at the user
manuals
how did you write a program for this
machine it would be it would
it would say um
you know you would say 69 which meant
load the distributor and and then you
would give the address of the number you
wanted to load into the distributor
uh yesterday
uh my friend that
doug spicer at the computer history
museum sent me a link to
something that just went on youtube it
was the ibm's
progress report from 1956 which is you
know very contemporary with 1957 yes
and in 1956 ibm had donated to stanford
university on ibm 650 one of the first
ones
when they showed a picture of the
assembly line for ibm 650s and they said
you know this is number 500 or something
coming off the assembly line and i had
never
seen so many ibm 650s i did in this
movie that was a it's on youtube now
um
and
and it showed the picture from
stanford
uh that that you know they they said
look you know we donated one of these to
stanford one to mit and they mentioned
one other
another college
and in in december of 56 they donated to
to my university case tech
but anyway
they showed a picture then
a class session
where a guy was teaching programming and
on the blackboard it said 69
8 000 i mean he
it was
he was teaching them how to write
uh
code for this ibm 650 which was in
decimal
numbers
so so the instructions were tended ten
decimal digits you had two digits that
said what
what to do for they just say uh
uh what to do it too
and four more digits to say where to get
your next instruction
and there's a manual that describes what
each of the numbers mean and the manual
was actually one
if the manual had been well written i
probably never would have gone into
computer science but it was so badly
written i figured
that i must have a talent for it because
i'm only a freshman and i and i could
write a better manual
uh
and that he did
and so i i started working at the
computer center um
and
and uh
wrote some manuals then but but yeah but
but this was uh
but this was the way we did it and and
my first program then was june of 1957
the tic-tac-toe
no that was the second program the first
the third program the first program was
factoring
a number okay so you dial a number on
the
on the um
uh their switches that means you sat at
this big mainframe
and
and you turn the dials and set a number
and and then it would punch out uh the
factors of that number on on cars so
that's the input is the number the input
was
yeah the input what was the number yeah
attended a number and
and uh and the output was uh its factors
and and and i wrote that program
uh
i still have a copy of it somewhere
and um how many lines of code do you
remember well yeah it started out as
about
20 but then i kept having to debug it
and i i discovered debugging of course
when i wrote my first program and what
does uh debugging look like
on a program with just all numbers
well you sit there and you uh i don't
remember how i got it into the machine
but i but i think there was a way to
punch punch it on cards so each each
instruction would would be one
one card or maybe i could get seven
instructions on the card eight
instructions i don't know but anyway
so i'm sitting there at the console of
the machine i mean i'm doing this at
night when nobody else is around of
course um and
and so you have one set of switches
where you can dial the number i'm
inputting but there's another switch
that's it that you know that says okay
now execute one instruction and show me
what you thought what you did
or or you or you
there was another four switches and say
stop if you get to those if if you get
to that instruction
so so i can say now go until you get
there again and watch okay so i could
watch
you know it he would take that number
and it would divide it by two and if
it's
you know there's no remainder then okay
two is a factor so
so then i work on the but if if not
divisible by two divide by three okay
keep trying and you know
until you know you're you're at the end
and uh you would find a bug
if uh if you were just surprised that
something weird happened
well certainly i mean
first of all i might have it
you know try to divide by one instead of
two you off by one errors that people
make all the time you know but but maybe
i go to the wrong instruction maybe i
you might maybe i uh
i left left something in a register that
i shouldn't have done but the first bugs
were pretty you know i i i probably
on the first night i was able to i was
able to get the factors of 30 you know
as equal to two three and five okay
um so you're sorry to interrupt you were
so you're sitting there late at night
yeah so
it feels like you spent many years late
at night working on a computer oh yeah
so like what what's that like so most
the world is sleeping
and you have to be there at night
because that's when you get access to
the computer between my freshman
sophomore year i didn't need sleep you
know
i used to do all-nighters when i was in
high school i used to
i used to
do the
uh the whole student newspaper every
monday night i would i would you know i
would just stay up all night and
and it would be done on tuesday morning
um
that was because i i didn't get ulcers
and stuff like that until later you know
but but but uh well the uh i don't know
if you know rodney brooks rod brooks of
course yeah he he he told he told me a
story that
he really you're you know he really
looked up to you he was actually afraid
of you
vice versa i must say
but when he tells a story when you were
working on tech
that they screwed up something with a
machine
i think this might have been mit i don't
know
and you were waiting for them to fix the
machine so you can get back to work late
at night oh oh
that happened all the time
he was really intimidated he's like dr
newt is not happy with this
that's interesting but no no the the
machine at stanford ai lab was
uh uh i
was down
an awful lot because we they had
they had many talented programmers
changing the operating system every day
and so operating system was getting
better every day but
it was also crashing so so so i i wrote
almost the entire manual for tech during
down time
[Music]
that much but that's another story okay
well he was saying they uh it's a
hardware problem they they uh they tried
to fix it and they reinserted something
and smoke was everywhere because he was
hurt well that didn't happen as often as
the operation coming from but yeah
and it was it's a funny story because
you're saying there's this
tall
uh don knuth that i look up to and
there was pressure to i think it's the
computer well
it's funny
okay the kind of things we remember that
stick in our memory well okay yeah well
i i i could tell you a bunch of rod
brooks stories too but let's
let's let let's go back to the 650. so
so um
so i'm debugging this my first program
and and i i
i had more bugs in it than a number of
lines of code i i mean the number of
lines of code kept growing
and let me explain so so i had to punch
the answers on cards all right
so so suppose i suppose i'm factoring
the number 30 then i got then it i got a
i got to put two
somewhere on the card i got to put a
three somewhere on the card i got to put
a five somewhere on the card right and
and you know what my i was my first
program i i probably screwed up and you
know it
it fell off the edge of the card or
something like that but but i didn't
realize that there are some tentative
numbers that have
that have more than eight um factors
and the card has only 80 columns and so
i need 10 columns for every factor
so my first program didn't take account
for the fact that i would have to punch
more than one card
my first program you know just line the
stuff up in memory and then it punched
the card but but after you know so by
the time i finished i had to i had to
deal with lots of lots of things also i
uh uh
if you if you put a large prime number
in there my program might have sat there
for for 10 minutes the 650 was pretty
slow and so it would sit there spinning
its wheels and you wouldn't know if it
was in a loop or whatever you said ten
digit
ten digits yeah so i think the largest
is sort of nine nine nine nine nine nine
nine nine nine seven or something like
that and
that would you know that that would take
me a while
uh
for that first one anyway that was my
first program well what was your goal
with that program well there's something
you were
hoping to
find a large prime maybe or no
the opposite you know my goal was to see
the lights flashing and
understand how how this magical machine
would be able to do something that took
so long by hand so what was your second
program my second program was
uh was
a converted number
from
from binary to decimal or something like
that it was much much simpler it didn't
have that many bugs in it
my third program was tic-tac-toe yeah
and he had some machi so the the the
tic-tac-toe program
is interesting on many levels but one of
them is that it has some
you can call machine learning in it
that's
yeah that's right uh
uh
i don't know how long it's going to be
before
the name of
our field has changed from computer
science to machine learning
but
but anyway uh uh it it was my first
experience with machine learning because
okay so here we had yeah how does the
program well first of all
what is the problem you were solving
what is tic tac toe what are we talking
about and then um right
how was it designed
right so so
you got a three by three grid and each
each each
each could be in three states it can be
empty or it can have an x or an o yeah
right so three to the ninth is a
uh well what is
how big is it i should know
um but it's 80
81 times 81 times three so
um
anyway
eight is like two to the third and so
that would be
uh that would be like two to the sixth
um
uh and then uh but that would be 64 then
you have to anyway i love how you're
doing the calculation
anyway the three comes from the fact
that it's either empty an x or an o
right
and
the 650 what was it was a machine that
had only uh
two thousand
ten digit words
you go from zero zero zero zero to one
nine nine nine and that's it
and and in each word you have a ten
digit number
so that's not many bits i mean i gotta
have three in order to have a memory of
every position i've seen
i need three to the ninth bits
okay but it was a decimal machine too it
didn't have bits but but but it did have
it it did have
strange instruction
where if if you had a tentative number
that but all the digits were either
eight or nine
uh
you you'd be eight nine nine eight or
something like that that would
uh you you could make a test whether it
was eight or nine that was one of the
strange things ibm engineers put into to
the machine i have no idea what well um
hardly ever used but anyway i i needed
one digit for every
every position i'd seen
uh zero meant it was a bad position i
meant it was good position
i i think i started out at five or six
you know but if you if you win a game
then you uh
then you increase the value of that
position for you but you decrease it
for your opponent uh uh so but but i i i
could
i had that much total memory for every
every possible position was one digit
and i had a total of 20 000 digits
which had which had to also include my
program
yes and all the logic and everything
including how to
how to ask
the user what the moves are and things
like this okay so so i think i had to
work it out because get every every
position in tic-tac-toe
it is equivalent to
roughly eight others because you you you
can rotate the board
um
which gives you factor four and you can
also flip it over
and that's another factor two so so i
might you know so i might have needed
only three to the ninth over eight
positions about you know plus
plus a little bit
uh so i had but anyway that was
that was a a part of the program to to
squeeze it into this tiny
so you tried to find an efficient
representation that took account for
that kind of rotation i had to otherwise
i couldn't do the learning
uh wow so so but but i had three
parts to my tic-tac-toe program
uh and i called it brain one brain two
and brain three so brain one
just played
a um
let's see
at random
okay
it's your turn okay you gotta put an x
somewhere he has to go in an empty space
but that's that's it okay
choose
to choose one and and play it uh
brain two
uh
had a canned routine
and i think it was it also
maybe it had
maybe it assumed you were the first
player or maybe it allowed you to be
first i think you were odd to be either
first of a second but had a canned
built-in strategy known to be optimum
for tic-tac-toe
[Music]
before i forget by the way
i learned uh many years later that
charles babbage
had had planned to
had thought about programming
tic-tac-toe for his
for his dream machine that he that he
was never able to finish wow so that was
the program he thought about more than a
hundred years ago yeah yeah he had he
he did that okay
and i had but and and i had however been
influenced by a
demonstration at the at the museum of
science and industry in chicago it's
like it's like boston's science museum i
think bell labs had had prepared a
special exhibit about
telephones and relay technology and they
had a tic-tac-toe playing
uh
machine as part of that exhibit so that
had been one of my
uh you know something i'd seen
before i was a freshman in college and
and inspired me to see if i could write
a program for
okay so so anyway i had brain one
random
you know uh
knowing nothing brain two knowing
everything
then brain three was the learning one
and and i could
i i could play
brain one against brain one brain one
against brain two and so on and so uh
you could also play against the user
against the live members but
but uh so so i started going the the
learning thing and i said okay you know
take two random
random people uh just playing uh uh
tic-tac-toe uh uh knowing nothing
um and
after about i i forget the number now
but but it converged after about 600
games
uh uh to a safe draw
the way
my program learned was actually it
learned how not to make mistakes because
you know how to
it didn't try to do anything
for winning it just tried to yeah drop
losing and not lose so that was probably
because of the way i did i designed the
learning thing i could have you know
had a different
uh reinforcement function that that
would
that would reward brilliant play but
anyway it didn't
and uh and and if if i took a novice
against the uh
you know the skilled player uh it it was
able to learn uh how to play a good game
so that was that and that was really
mike
but after i finished that i i felt i i
understood programming
was there um
did you
did a curiosity and interest in learning
systems persist for you
so
why why did you want brain three to
learn
yeah i i think naturally it's
we're talking about rod brooks like
he he was teaching all kinds of
very small devices
to to learn stuff
um if a leaf drops off of a tree uh uh
you know it
he was saying something well it learns
if there's wind or not
but but i i mean he pushed that a little
bit too far but
he said he could probably train some
little mini bugs to to scour out dishes
if he had enough
financial support i don't know
can i can i ask you about that because
he he also mentioned that during
those years
there was discussion about
inspired by touring about computation
you know of what is computation
yeah
and
yeah i never thought about any stuff
like that that was
that that was way
too philosophical i mean
i i was a
i was a freshman
after all i mean
i i didn't
i was pretty much a machine
so it's almost like yeah i got you it's
a tinkering mindset
uh not a philosophical mindset
it was just exciting to me to
be able to control something but not
but not
but not to say hmm am i solving a big
problem or something like that or is is
this a step for humankind right no no
way
when did you first start thinking about
computation in the big sense
you know like the universal turing
machine well
i mean i had to pass an ex i
had to take i had to take uh
classes on
computability when i was a senior
so you know we read this book by martin
davis and
yeah this is cool stuff but you know i i
learned about it because i you know i
needed to pass the exams but i didn't
i didn't invent any of that before stuff
but but i i had great fun playing with
the machine you know i um i wrote
program because it was fun to write
programs and and
and get
this
i i mean it was like watching miracles
happen
you mentioned in in an interview that
when reading a program you can tell when
the author of the program changed
oh okay uh
how the heck can you do that like what
makes a distinct style for a programmer
do you think
you know there's different hemingway
has a style of writing
versus james joyce or something
well those are pretty yeah those are
pretty easy to imitate but
it's the same with music and whatever
you can
i i i i found uh
well during the pandemic i
spent a lot more time playing the piano
and i i found something that i'd had
i i had it right when i was taking
lessons uh
you know
before i was a teenager and uh
it was
yankee doodle
uh played in the style of
you know and
i you had you had beethoven and you had
wc and chopin and you know and the last
one was gershwin
and
i played over and over again i thought
it was so brilliant because but
but it was so easy but also to
appreciate how
this uh this
author mario somebody or other had
had been able to uh reverse engineer
the styles of of those components so but
now specifically uh to your question i
mean there would be
there it was
it was pretty obvious in this program i
was reading it was it was a compiler
uh and it had been written by a team
at at carnegie mellon
and uh i have no idea
which program
was responsible for but but it you would
get to a part where the guy would just
not know how he how to move things
between registers very efficiently and
so
and so everything that
that could be done in one instruction
would take three or something like that
that would be a pretty obvious uh
change in style but there were but then
there were also you know flashes of
brilliance where you could do in one
instruction normally i used two because
because you knew enough about the way
the machine worked that you could
that that you could accomplish two goals
in one step
so it was mostly the the brilliance of
the concept more than the
uh semicolons and uh or the
the you know the use of short sentences
versus long sentences something like
that so you would see the idea in the
code and you can see the the different
style of thinking experience right it
was yeah so it was stylistic
i mean like i could identify authors by
their
by the amount of technical aptitude they
had but not by
styling the sense of
rhythm or something like that so if you
think about mozart beethoven bach if
somebody looked at don knuth code would
they be able to tell
that this
is a distinct style of thinking going on
here what do you think
and what what would be the defining uh
characteristic of the style
well
my code now is it
is literate programming so i'm it's a
combination of english and c mostly but
but but if you just looked at the c part
of it you would also probably notice
that i don't
got it
you know that i use a lot of global
variables that other people don't and
and and i expand things inline more than
instead of calling
anyway i have different
subset of c that i use okay but this
that's a little bit stylistic yeah
but but with literate programming you
alternate between english and
and c or whatever
and
um and by the way people listening to
this should look up literate programming
it's very interesting uh concept that
you
uh you proposed and developed over the
years
yeah yeah
i'm
that's the most
significant thing
i think to come out of the tech project
is
it is that i uh
i i realized that
uh
my programs
were to be read by people and not not
just by computers and
and that typography could
massively enhance that and
and and so uh
i mean it
they're just wonderful if they're gonna
look it up that they should also look up
this book by
called physically based rendering
by matt farr and
anyway it
got an academy award
but it's but but but all the if
on the graphic effects you see in movies
uh
like
you know are accomplished by algorithms
and this book it is the whole book is a
literate program it tells you not only
how you do all the shading and
and uh
bringing images in that you need for
animation and textures and so on but it
also uh you can run the code
uh
so uh and
and so uh
i find it uh an extension of the way i
uh of of how to teach programming is it
is but by
by telling a story
as part of the program so it's uh it
works as a program but it's also
readable by humans
yes and especially by me
yeah a week later or a year later that's
a good test if you yourself understand
the code yeah
easily a week or more or a year later
yeah
so it it it's uh
what's this piece it's the greatest
thing since sliced bread
programming
or literate literate program okay
uh
you heard it here first okay you uh
dodged this question in an interview i
listened to
uh so let me ask you again here
uh what makes for a beautiful program
what makes for a beautiful program yeah
what are the characteristics you see
like you just said literate programming
what are the characteristics you see in
a program that make you sit back and say
that's pretty good
well the reason i didn't answer is
because there are there are dozens and
dozens of answers to that because
because
each you can define beauty
the same personal defined beauty a
different way from hour to hour i mean
it depends on what
and what you're looking for
at one level you it's it's beautiful
just if it works at all
another level it's beautiful if it's
if it uh
uh
it can be understood easily
it's beautiful if it
if it's illiterate programming it's
beautiful it makes you laugh i mean
yeah i'm actually so i'm with you i
think beauty
if it's readable
readable yeah if you understand what's
going on and also understand
the elegance of thought behind it
and then
also as you said wit and humor i was
always uh i remember having this
conversation i had this conversation on
stack overflow
whether humor is good in comments
and i think it is whether huma is good
in comments like uh when you add
comments in code yeah
i always thought a little bit of humor
is good
it shows personality
it shows character shows wit and fun and
all those kinds of things
of the personality of the programmers
yeah okay so
uh a couple days ago i received
a wonderful present from my former
editor at aston wesley he
he's downsizing his house and he found
uh
that
somebody at the company had
had found all that all of their internal
files about the art of computer
programming from the 1960s and they gave
it to him
uh and then
you know before throwing string in the
garbage
and then so he said oh yeah he
he planned to keep it for posterity but
now he realized that posterity is a
bit too much for him to handle so he
sent it to me
and so
and so i just received uh
this big big stack of
of letters uh
some of which i had written to them but
but many of which they had written to
early guinea pigs who were
telling them whether they should publish
or not you know
and one of the things
was uh
uh
in in the uh in the comments to volume
one uh
uh
the the major the major reader was was
bob floyd
uh
who is my great
uh co-worker in the 60s um died early
unfortunately but but uh
and and he
he commented about the humor
so we had you know he ran it by me you
know says
you know keep this joke in or not you
know um
they also sent it out to focus groups
what do you think about humor in
a book about computer programming what's
the conclusion and i stated my
philosophy is it said you know the ideal
thing
is uh
that it's it's it's something where
the reader knows that there's probably a
joke here if you only understood it and
this is a motivation
to understand
to think about it a little bit um but
anyway it it it's a very delicate humor
i mean it's it's it's really uh
each each century invents a different
kind of humor too i mean
and
different cultures have different
different kinds of humor um yeah like uh
we met we talked about russia a little
bit offline uh you know there's dark
humor
and
you know what
when a country goes to something
different right any of that life and
stuff like this
yo and jack benny i mean
steve allen wrote this book about
humor and it was the most boring book
but he was one of my idols but
but uh
yeah
it's called the funny men or something
like that but yeah okay so anyway i i
think it's important to know that
that this is part of life and and it
should be fun and not yeah and and so
you know i wrote this
this organ composition which uh uh is
based on the bible but i didn't refrain
from putting little jokes in it
also in the music it's hidden in the
music it's it's it's there yeah
a little humor is okay yeah i mean
not egregious humor
so in in this correspondence you know
there were
there were things i said yeah i really
shouldn't have i i really shouldn't have
done that
but uh but other ones i could you know i
insisted on and i've got
jokes in there
that no that
nobody has figured out you in fact
in volume 2
i've got a
cryptogram a message
in cypher
and in order to decipher it you're going
to have to
have to break an rsa key which is
larger than people know how to break
uh and so
you know if computers keep getting
faster and faster then you know might be
100 years but somebody will figure out
what this message is and they will laugh
i mean i've got a joke in there
so that one you really have to work for
uh i i don't know if you've heard about
this
let me explain it maybe you'll find it
interesting
so open ai is a company that
does uh ai work and they have this
language model it's a neural network
that can generate
language pretty well
but they also
of on top of that develop something
called
openai codex
and together with github they developed
a system called openai copilot
let me explain what it does
there's echoes of literate programming
in it
so what you do is you start writing code
and it completes the code for you
so for example you start let's go to
your factoring program you start you
write in javascript and python in any
language
that it trained on uh you start
you write the first line and some
comments like what this code does and it
generates the function for you
and it does an incredibly good job like
it's not provably right but it often
does a really good job of completing the
code for you i see whether
but how do you know whether it did a
good job or not
you could see a lot of examples where he
did a good job
and so you it it's not a thing that
generates the code for you it starts
it gives you uh
so it puts the human in the seat of
fixing
issues versus writing from scratch do
you find that kind of idea at all
interesting
every year we're going to be losing more
and more
control over what machines are doing and
people are saying well it seemed to like
when i was a professor at caltech
uh in this in the 60s we had this
this guy who
who talked a good game
he could give inspiring lectures and
you'd think well
certainly things he was talking about an
hour later you said well what did he say
um
but what but
but he really felt that it didn't matter
whether computers got the right answer
or not it just mattered whether it made
you happy or not in other words if you
you know if
if if your boss paid for it uh he
you know then you had a job you could
you know you could
you could take care of your wife
happiness is more important than truth
exactly he didn't believe in truth but
he was a philosopher
i like
it and somehow you you see uh
we're going that way i mean
so many more things are are taken over
by saying well this seems to work
and so and when there's
when there is uh competing interests
involved neither side understands
why the decision is being made
you know we realize now that it's that
is bad but but consider what happens
five private ten year year down the line
when things get even more
further detached and each thing is based
on
something
from the previous year yeah so you start
to lose the more you automate the more
you start to lose track of uh some deep
experimentally
exponentially but so that's the dark
side the positive side is
the more you automate the more you let
humans do what humans do best
so
maybe programming
this you know maybe
humans should focus on a small part of
programming that requires that genius
the magic of the human mind
and the mess you let the machine
generate yeah i mean they're that's the
that's the positive but of course it
does come with the darkness like
automation
what what's better correct i'm never
going to try to write a book about that
uh i'm never going to recommend to any
of my students to work for them
so you you're on the side of i'm on the
side i'm on the side of honor happiness
understanding i understand
and i i think these things are really
marvelous if they if
if what they do is you know
all of a sudden we have a better medical
diagnosis or or or you know it will help
guide some scientific experiment or
something like this uh
you know you know curing diseases or
what whatever but
but when it
when it affects people's lives in a
serious way uh uh
so if you're writing if you're writing
code for geeky oh yeah here this is
great
this will make a slaughter bot okay
so i see so
you have to be very careful
like right now it seems like fun and
games it's useful to write a little
javascript program that helps you with
the website
but like you said one year passes two
years passes five years and you forget
you start building on top of it and then
all of a sudden you have autonomous
weapon systems
based
well we're all dead it doesn't matter in
that sense
well in the end
the this whole thing ends anyway so
um but it it
there is a heat death of the universe
predicted but i i'm trying to postpone
that for
for a little bit
well it'd be nice that at the end
as we approach the heat death of the
universe there's
still some kind of consciousness there
to
to to to appreciate it
hopefully human consciousness i'll
settle for 10 to the 10 to the 10 to the
10th year some finite number but
but
things like this might be the reason we
don't pick up any
signals from
extraterrestrial
they don't want anything to do with us
oh because they because they
they invented it too and
so you you do have a little bit of worry
on the
existential threats of
ai and automation
so like like removing the human from the
picture et cetera yeah people have more
more potential to
to do harm now than
by far than they did a 100 years ago
but are you optimistic about so the
humans are good at creating destructive
things but also humans are good at
solving problems yeah i mean there's
half empty and have full you know that
so
how yeah we have full or what i can go
yeah so so let me let me put it this way
because
because it's the only way i can be
optimistic but but
but
think of um
of
things that have changed because of
civilization
you know they don't occur just in nature
so just
uh just imagine that the room we're in
for example
okay some
you know we've got
pencils we've got books we've got tables
we've got microphones
clothing food
all these things were added
somebody invented them one by one and
millions of things
uh that we inherit okay
and
it's inconceivable that that so many
millions of billions of things uh
wouldn't have problems and
we we get it all right
um and and each one
would have no
negative
effects and so on so it it's very
amazing that it much works as does work
it's
it's incredibly amazing
and actually that's the source of my
optimism as well
including for artificial intelligence
so
we we drive over bridges
we we use all kinds of technology we
don't know how it works and there's
millions of brilliant people involved in
building a small part of that and it
doesn't go wrong and it works and i mean
that
it it works
and it doesn't go go wrong
often enough to suffer and we can
identify things that aren't working and
and try to
improve on them
in a sub often suboptimal way oh
absolutely but it's
but but the
the kind of things that
i know how to
improve
require human beings to be rational and
i i'm losing my confidence that human
beings are rational
yeah
yeah now here you go again with the
worst case uh worst case analysis
they may not be rational but they're um
they're they're
clever and uh
beautiful in their own kind of way yeah
i tend to think that most people
um have the desire and the capacity to
be good to each other
and love will ultimately win out like if
they're given the opportunity that's
where they lean
in the art of computer programming you
wrote the real problem is that
programmers have spent far too much time
worrying about efficiency in the wrong
places and at the wrong times
premature optimization is the root of
all evil
in parentheses or at least most of it in
programming
can you uh explain this idea
uh what's the wrong time what is the
wrong place for our optimization so
first of all the word optimization i i
started out writing software uh and
optimization was i was a compiler writer
so optimization meant uh making the
uh
making a better translation it it so
that it would run faster on it on a
machine instead of an optimized program
it's just like you know you you you run
a program and you set the optimization
level uh for
the compiler so that's one
word for optimization
um and at that time i
i happened to be looking in an
unabridged dictionary
uh for some reason or other and i came
to work optimizing
what's the meaning of the word optimized
and it says to view with optimism
and you look in webster's dictionary of
english language in 1960 early 1960s
that's what optimized me meant okay
so people
started doing cost optimization other
kinds of things uh
you know whole subfields of
of
algorithms and economics and whatever
are are based on what they call
optimization now but
but
to me optimization when i was saying
that
was saying uh uh changing a program to
make it more
tuned to the machine
and i found out that uh
when a person writes a program
uh
he
he or she
tends to think that
the parts that were hardest to write are
going to be hardest for the computer to
execute
so
maybe i have 10 pages of code but
i i had to work a week writing this page
i i mentally think that when the
computer gets to that page it's going to
slow down
right uh it's chris oh i don't
understand what i'm doing i better
be more anyway this is of course
silly but it's it's something that we
that we
that we don't know when we write a piece
of code we don't know what
what whether the computer is actually
going to be executing that code very
much
so so people had had a very
poor understanding of
of
what the computer was actually doing
i i made one test where
where we studied a fortran compiler
and it was spending more than 80 of its
time reading the comments card
[Music]
but as a programmer we were really
concerned about how fast it could take a
complicated expression that had lots of
levels of parenthesis and
and and and convert that in
into something but that was just you
know less than one percent of the uh
so if we optimized that
uh
we didn't know what we were doing but
but but if if we knew that it was
spending eighty percent of his time on
the comments
card you know in ten minutes we could we
could make the the compiler run more
than twice as fast and you can only do
that once you've completed the program
and then you empirically study where i
had some kind of profiling that i knew
what was important yeah so
you don't think the supplies generally i
mean there's something that rings true
to this across the board i'm glad that
it applied generally but but it was it
was only my good luck
i said it but you know but but i did but
i said it in limited context and not and
and i'm glad if it
makes people think about stuff because i
i
but
it applies
in another sense too that is
sometimes i will
do optimization in a way that does help
the
the actual running time
but makes the program impossible to
change next week
because i've changed my data structure
of something that
that made it less adaptable so one of
the great uh
principles of computer science is
is
it is laziness or whatever you call it
the
late binding uh you know don't
hold off decisions when you can
um
and
and and you know and we understand now
quantitatively how valuable that is
what do you mean we understand so you
mean people
people have written thesis about how you
can how late binding will
it will improve the i mean you know just
in time manufacturing or whatever
you can make you can defer a decision
instead of doing your advanced planning
and say i'm gonna allocate thirty
percent to this and fifty percent so in
all kinds of domains there's an
optimality to laziness in many cases
decision is not made in advance so
instead you you design
in order to be flexible uh uh to to
change with the uh uh
with the way the wind is blowing yeah
but so the reason that line resonated
with a lot of people
is because
uh there's something about the
programmer's mind
that wants that enjoys optimization so
it's a constant struggle
to
balance
laziness
and lay binding with
the desire to optimize
the elegance of a well-optimized code is
something that's compelling to
programming
yeah
it's a
another concept of beauty
let me ask you a weird question
so roger penrose
has talked about computation computers
and
he proposed that
the way the human mind discovers
mathematical ideas is something more
than a computer
that that a universal turing machine
cannot
do everything that a human mind can do
now this includes
discovering mathematical ideas and it
also includes
he's written a book about it
consciousness
so i don't know if you know roger but
yeah
my uh my daughter's kids played with his
kids in oxford
nice
so do you think there is such a limit to
the computer do you think consciousness
is more than a computation do you think
the human mind the way it thinks is more
than a computation
i i mean like i i can say yes or no but
but but i don't i have no reason
i mean
so you don't find it useful to have an
intuition in one way or the other like
when you think about algorithms do you
isn't it
unanswerable question in my opinion is
is no better than anybody else you think
it's unanswerable so you don't think
eventually science
angels can dance on the head i mean i
don't know
but angels
anyway there are lots of things that are
beyond that that we can speculate about
but
i don't want somebody to say oh yeah
canoe said this and and so he's he's
he's smart and so he so that must be
i mean i say it's something that uh
we'll never know
interesting
okay that's a strong statement i i don't
i personally think it's something we
will know eventually like there's no
reason to me why the the workings of the
human mind
are not within the reach of science
that's absolutely possible and i'm not
denying it yeah
uh but right now you don't have a good
intuition i mean that's also possible
you know that and ai
you know created the universe you know
intelligent design
has all been done by an ai yes
this is i mean all these things are but
but but but you're asking me to
to pronounce on it and and i don't have
any expertise i i i i'm a teacher that
passes on knowledge but i don't
but i don't know
the fact that i
that i vote yes or no on
well you do have expertise as a human
not as a not as a teacher
or a scholar of computer science
i mean that's ultimately the realm of
where the discussion of human thought
yeah well i know we're in consciousness
he might even thought he proved it but
no he doesn't he doesn't prove it he is
following intuition but
but i mean you have to ask john mccarthy
john mccarthy
i think
uh we're totally unimpressed by these
statements
so you don't think so even like the
touring paper on
uh on the touring test
that
you know starts by asking can machines
think oh um you don't think these kind
of um
touring doesn't like that question yeah
i don't consider it important let's put
it that way
because it it's in the category of
things that
it it it would be nice you know but i
think it's beyond knowledge and so i
don't
i'm not i'm more interested in knowing
about
the riemann hypothesis or something
so when you say it's an interesting
statement beyond knowledge
yeah i think what you mean
is it's not sufficiently well
it's not even known well enough to be
able to formalize it
in order to ask a clear question yeah
and so that's why it's beyond knowledge
but that doesn't mean it's not
eventually going to be formalized yeah
yeah maybe consciousness will be
understood some some day but uh the last
time i checked
uh
it it was still 200 years away
i haven't been specializing in this by
any means but but but i went to lectures
about it 20 years ago when i was
uh there was there was a symposium at
the american academy in in cambridge and
it started out by saying essentially
everything that's been written about
consciousness is
is hogwash
i tend to
i tend to disagree with that a little
bit so well it's
so consciousness for the longest time
still
is in the realm of philosophy so it's
just conversations without any basis and
yeah understanding
still
i think
once you start creating artificial
intelligence systems that interact with
humans
and they have personality
they have identity you start flirting
with the question of consciousness not
from a philosophical perspective but
from an engineering perspective
and then starts becoming much more
like i feel like yeah yeah don't
misunderstand me i
i i i i certainly don't disagree with
that at all um
and
even at these lectures that we had
you know 20 years ago there were
neurologists
pointing out that
that human beings had actually decided
to do something before they were
conscious of making that decision yeah
uh
i mean they could tell that
you know that signals were being sent to
their arms before they before their they
knew that they were
anything like this
are true and and uh
my uh you know less valiant has
an architecture for the brain and more
recently uh
uh
christus papadomitrio uh
in the academy
science proceedings a year ago uh with
with two other people but i know chris
does very well
uh and and he's got this uh
uh this model of uh
this architecture
by which you could uh create a
uh things that
that correlate well with the uh with
experiments that are done on
consciousness uh
and and and and he
he actually you know has a
a machine language that in which you can
you can write
code and
and test hypotheses
uh
and so it it might you know we might
have a big breakthrough my personal
feeling is that
consciousness
the the best model
i
i've heard of uh to explain the the
miracle of consciousness uh is
that that
that somehow
inside of our
brains
we're having a
a
continual survival for the fittest
competition
as i'm speaking to you
uh all the possible things i might be
wanting to say
are all in there
and there's like a voting going on yeah
right and
one of them is is winning
and and that's affecting the you know
the next sentence and so on yeah uh and
uh
there was this book
machine intelligence or unintelligent on
intelligence yeah bill
atkinson uh was what was it what was a
total
devotee of that book well i like
whether it's consciousness or something
else i like the storytelling part that
we it feels like uh for us
humans it feels like there's a concrete
it's almost like literary programming i
don't know what the programming going on
on the inside but i'm getting a nice
story here about
what happened and it feels like i'm in
control and i'm getting a nice clear
story so but it's also possible there's
a computation going on
that's really messy there's a bunch of
different competing ideas
and in the end it just kind of generates
a story for you to uh
a consistent story for you to believe
and that makes it all nice yeah and so
i prefer to talk about things that i
have some expertise and then things for
which i which i'm only a
uh you know
on the sideline
so there's a tricky thing i don't know
if you have any expertise in this you
might be a little bit on the sideline
it'd be interesting to ask though
what are your thoughts on cellular
automata and the game of life
have you ever played with those kind of
little uh games i think uh the game of
life uh it is
it is wonderful and uh
uh
and
and shows all kind of stuff about how
things
can evolve without the creator
understanding
anything more than
the power of
learning things in a way but to me the
most
important thing about the game of life
is that is is how it
focused for me
what what it meant to have free will or
not
because the game of life is obviously
totally deterministic yes and i i i find
it hard to believe that anybody who's
ever had children
cannot believe in free will
right on the other hand
this makes it crystal clear
john conway said
he wondered whether it was
immoral to shut the computer off after
he got into a particularly interesting
play of the game of life um wow yeah so
there is
to me the reason i love the game of life
is exactly as you said a clear
illustration that from
simple initial conditions with simple
rules you know exactly
how the system is operating is
deterministic
and yet if you let yourself
if if you allow yourself to
lose that knowledge a little bit
enough to see the bigger organisms
that emerge and then all of a sudden
they seem conscious they seem
not conscious but living if if the
universe is finite
we're all living in the game of life to
slow down i mean
it's sped up a lot
but do you think technically
some of the ideas that you used for
analysis of algorithms can be used to
analyze the game of life
can we make sense of it or is it too
weird yeah i mean i i
i've got i've got a dozen exercises in
volume
for
fascicle six uh
that
actually worked rather well for that
purpose
but
bill gospers
came up with the
with the algorithm that that allows
that allowed golly to
uh to
you know to run thousands and thousands
of times faster to
you know the website called golly
g-o-l-l-y it simulates the cellular
automata like game of life yeah you got
you got to check it out yeah
can i ask about john conway
yes in fact i i i'm just reading now the
the issue of mathematical intelligence
or that came in last last week it's a
whole issue devoted to to
uh
you know
remembrance of of him did you know him
i
i slept overnight in his house several
times i
yeah he recently passed away
yeah he got he died a year ago
may
i think it was i've covered
what are you what are some memories of
him of his work that stand out for you
is
did uh
on a technical level did any of his work
inspire you on a personal level that
did he himself inspire you in some way
you know absolutely to all of those
things but
let's see when did i first meet him i
guess i first met him at oxford in like
1967 when i was wow
okay that's a long time ago yeah yeah
you were minus
20 years old or something i don't know
1967.
but but uh
there was a conference where
uh
and i think i spoke
i was speaking about
something that
known as the canoes bendix algorithm now
but but he
he gave it famous talk about knots
and and at the end i didn't know at the
time but but
anyway that talk had now
the source of thousands and thousands of
papers
since then
uh and
it was he was reported on something that
he had done
in high school uh
you know almost ten years earlier
[Music]
before this conference but he never
published it and and he climaxed his
stock by
building some nozzle
you have these lit these little plastic
things that you that you could stick
together
uh it's it's it's
it's something like lego but easier
and so he made a whole bunch of knots in
front of the audience and so on and then
disassembled it
so it was
a dramatic lecture
before he had learned how to give even
more dramatic lectures later
so
all right and
were you at that lecture and i was there
yeah because i had to i was at the same
conference
um
for some reason i was i i happened to be
in in calgary
uh
at the same day that he was visiting
calgary
and it was a spring of of 72
i'm pretty sure
and
and we had lunch together
and
he wrote down during the lunch on a
napkin
uh all of the
facts about
what he called numbers
um and i
and
and he covered the napkin with with the
theorems
about his
his idea of numbers
and i thought which was incredibly
beautiful
um
and
and later in 1972
my sabbatical year began and i went to
norway
and
and in december of that year
uh in the middle of the night
the thought came to me
you know conway's theory about numbers
would be a great
thing to teach students how to invent
research and what the joys are of
research
and
and i and so i said
and i had also
read a book in dialogue
by by alfred rennie
uh
where he was kind of a socratic thing
where the two characters were talking to
each other about mathematics and so i
and so
at the end
in the morning i i
woke up my wife and said
jill
i think i wa