Donald Knuth: Algorithms, Complexity, and The Art of Computer Programming | Lex Fridman Podcast #62

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

Channel: Lex Fridman

Views: 371,827

Keywords:

Id: 2BdBfsXbST8

Length: 105min 56sec (6356 seconds)

Published: Mon Dec 30 2019

Reddit Comments

[u/qznc_bot2]

There is a discussion on Hacker News, but feel free to comment here as well.