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

[@lexfridman]

I really enjoyed this conversation with Donald. Here's the outline: 0:00 - Introduction 3:45 - IBM 650 7:51 - Geeks 12:29 - Alan Turing 14:26 - My life is a convex combination of english and mathematics 24:00 - Japanese arrow puzzle example 25:42 - Neural networks and machine learning 27:59 - The Art of Computer Programming 36:49 - Combinatorics 39:16 - Writing process 42:10 - Are some days harder than others? 48:36 - What's the "Art" in the Art of Computer Programming 50:21 - Binary (boolean) decision diagram 55:06 - Big-O notation 58:02 - P=NP 1:10:05 - Artificial intelligence 1:13:26 - Ant colonies and human cognition 1:17:11 - God and the Bible 1:24:28 - Reflection on life 1:28:25 - Facing mortality 1:33:40 - TeX and beautiful typography 1:39:23 - How much of the world do we understand? 1:44:17 - Question for God

[@Jon-br8co]

Lex we need an interview with Andrew Yang. We been waiting months... You had several experts on AI and Economics and those guests thus far are perceiving UBI in a negative light. Most in part because they are not dialed in on the proposed implementation from Andrew Yang's UBI. Kai Fu Lee's argument on the labor displacement was to focus on retraining. Andrew Yang states that the retraining success rate is about 5%-15% for the manufacturing worker that were displaced from automation. You must agree that's freaking horrible. Ray Dalio's concern is that UBI will take away from other social programs and mostly focused on child's early development to provide opportunity at an early age. We all know that schools can only influence 30% of a child development and 60%-70% has most to do with what the child's home environment is like... Please get Andrew Yang on for the Rebuttal of Kai Fu Lee's and Ray Dalio's perspective. You yourself know very well that AI will rip through our economy and completely redefine labor. What this mean to our society at this moment is looking very dark. Please get Andrew Yang on your show... BTW massive fan of the show, only because I and many like me see the massive change coming down the pike and we all know it could be incredibly good for us and on the flip side, it could be incredibly bad for us... Please consider me very concerned and please excuse my forwardness...

[@SudipBishwakarma]

What the....YOU FINALLY DID IT!!! WOW😃

[@AmericanbouyUSA]

1:17:11 God rolls the dice. However, the adversarial (Devil) tries to roll the dice back, in order to confuse the situation (ANALOGY - G.A.N.s or Generative Adversarial Networks). Therefore, there is a, contradictory, random, probabilistic, solution, determined by who knows how to roll the dice, while knowing the end result (Fate). Free will, only, occurs when intelligent living organisms work together for a common cause, I think. Which direction is the world headed, collectively?

[@AmericanbouyUSA]

1:39:23 Reality is a result of experiencing tragedy(ies) or Caring for others. Destruction of people and/or society(ies) is/are a result of fearlessness and/or lack of conscience (either on purpose or perhaps a lapse of memory (past experiences) - like dementia), I think. Flaws are our memories, either learned or overlooked, we have been exposed to, relative to the past. However, looking to the future, in a "positive light" is what normal reality should look like, to me.

[@AmericanbouyUSA]

1:44:17 Question for God - "What kind of browser do you have up here?" "I hope we had good internet." Answer from God - We live in a holographic ("super" (BEYOND HUMAN COMPREHENSION) internet of God's crafting) universe that connects us to our creator(s), via the dimensions we can not perceive with our eyes, but with, only, our minds and souls, I think. Quantitatively speaking, we are minuscule, compared to the size of our creator(s). That is what differentiates us, on planet Earth, to what lies beyond the infinity or finite real estate we call the universe(s), in my opinion. We seem to be two different entities (Two independent (yet dependent) systems that struggle to coexist). Therefore, one's own death is validated, (relative to some (NOT ALL HUMANS) intelligent living organisms), in order to meet our maker and/ or ask for forgiveness for our sins. ETERNAL LIFE IS RELATIVE TO ONE'S BELIEF SYSTEM AND / OR ENVIRONMENT. EITHER PEOPLE WANT TO LIVE FOREVER, IN THIS TIME WE CALL LIFE, OR ONE ACCEPTS DEATH, AT SOME POINT, TO HAVE ETERNAL FREEDOM FROM PAIN AND / OR QUESTIONS UNANSWERED, IN THIS FINITE / SELF CENTERED VIEW THAT MOST PEOPLE SEEM TO HAVE ABOUT THE WORLD WE LIVE IN, GENERALLY SPEAKING, I THINK.

[@thuggfrogg]

These videos with living legends are an incredible gift and contribution to humanity. Thanks for these, Lex.

[@dalelarson3884]

I've long admired Donald Knuth and much enjoyed your interview. Its pacing and development were superb. I chanced years ago to meet him at his Palo Alto church. In the passing of the peace he circled around to shake hands and at social hour engaged in conversation. Your fine interview has today given me a second chance to extend that pleasure. My double thanks.

[@NomenNescio99]

Interview haven't begun and I already clicked like. KNUTH!! He's my homeboy! Lex, anything is okay as long as you are talking with the Knuth.

[@foodsel]

"I enjoy the fact I have limits" - but seemingly driven by the sense of being able to solve complex problems; one of many things to possibly take away from this talk. The openness of dealing with mortality and the contagious yet realistic curiosity really is inspiring to me. Thanks to both guest and host!

[@mohamedlotfi982]

I feel spoiled with all these guests. Would love to see Grant Sanderson of 3blue1brown on here. Like so Lex could see this

[@lexfridman]

I did! I think it'll be out next Monday or Tuesday. And I'll probably talk to him again.

[@mohamedlotfi982]

@@lexfridman Wow! Always 1 step ahead, your work is awesome man!

[@unoriginalusernameno999]

Lex Fridman WOW! Whose next? Jeff Bezos? Tory Bruno?

[@rolandlemmers6462]

@@unoriginalusernameno999 Next thing you know he'll be coming down from the mountain. Life might get complicated though, stone tables are not fashionable anymore just 10 rules and it's full, 128 Gb sd-cards though... Next bible 98.000.000 pages?

[@squirlmy]

@@ACogloc he presumably named himself after the Diagnostic and Statistical Manual of Mental Disorders, Fifth Edition (That's DSM 5, not sure what the extra 'D' stands for) So yeah, I think this is quite literally someone in need of a medication adjustment. We've grown so used to things like "AI-generated content", that we forget there are actually people suffering from thinking disorders who sincerely post indecipherable statements. Another reason to be careful and compassionate with responses.

[@bigshaqsmathematicalinstit3318]

You ask good questions, this is how a podcast should be!

[@7cle]

You are a good interviewer. Your questions are good and you let the interviewed answer without stepping in and put yourself forward. That's gold.

[@rpbmpn]

So valuable to be able to hear this. As a youngster in the late 1990s I dreamed of hearing from all the experts in any domain I was interested in, but it was never realistic (at least not without a string of certain extraordinarily difficult or unlikely events). There's no way you have time to read even a hundredth of your comments, so I know with quite high probability that I'm speaking into the void, but thank you for making this vast wealth of knowledge so easily accessible.

[@kevalan1042]

Lex, my only complaint is I can't keep up with watching all these amazing interviews. Deepest kudos to you sir.

[@1974greymalkin]

I love listening to very intelligent people formulate a thought. This is a brilliant man. What a treat to hear him talk in a relaxed setting.

[@shellrox2878]

One of the greatest computer scientist and mathematician of all time!

[@ofHerWord]

Him and Ritchie are my hero's

[@vikingthedude]

@@ofHerWordritchie who?

[@ofHerWord]

@@vikingthedude I’m a nigger

[@JivanPal]

@@vikingthedude Almost certainly referring to Dennis Ritchie.

[@faithinverity8523]

I didn't quite know what to make of these conversations until 15:40. Lex has a goofy side. I am supremely glad that Lex has roped together this group and conversed with them. We all read Knuth and listened to him talk but never had a chance to see him in conversation. And I have to thank all of Lex's subjects for turn submitting to being interviewed. It has been unsurprisingly good to hear what they had to say.

[@TheNishant1980]

Lex please conduct an interview with yourself as well. It's really a tough job to ask all these intelligent questions to all these experts from different fields. You are yourself a legend 😊

[@rahulpyd1]

That last Q/A is so hilarious. I couldn't stop laughing for a while. On a serious note thanks Lex for this. You have literally connected a generation with Knuth. I haven't seen an interview like this with him. Knuth as ever inspires me.

[@giedirietveld7425]

Thank you Lex Fridman for the heavy questions you 'put on the table' of Donald Knuth. Mabye that's the reason why I see him now as a human being in the first place. You took the risk to loose him during the interview, but he stayed on line with you and special that makes him greater then I thought before this podcast. So for the second time: THANK YOU!

[@thevfxwizard7758]

I was taught AP Calculus AB by his son. Needless to say, he was a great teacher.

[@wqz9822]

Get Linus Torvalds next!

[@johnhammer8668]

Yes. Torvalds please

[@SuperMarioTomma95]

Yes and then John Cena pls

[@keedt]

and Theo Deraadt should make for an interesting interviewee in the open source realm as well.

[@SuperMarioTomma95]

@@keedt yes and then also Brock Lesnar

[@SuperMarioTomma95]

@@williamhumphries2900 No :( He keeps doing his "you can't see me" thing and then disappears while Lex ask questions.

[@joelicata]

Incredible interview. In the early 70’s Vols 1 and 3 were my foundation. Seeing hearing Don puts a big comfortable smile on my face. Thanks Lex.

[@mzsolt]

So great to hear that he's still programming. Can't get enough of that, when you're solving fun puzzles and not making big systems that solve everything. :)

[@ralvarezb78]

20 Years Ago I discovered "The Art of computer programming" this brings me "the light"

[@vkray]

Raúl Alvarez Which country?

[@stefanluginger3682]

Raúl Alvarez I would too if I would have 100 more years in life

[@TarlanT]

I discovered it in year 2000 as well.

[@ivayloyankov8120]

How incredible is our time? To listen to these bright minds for free, this is amazing.

[@ynmorho]

this was such a treat. i will cherish this interview for years to come. thank you!

[@rekeshali]

Damn Lex, you ask the best questions cause your guests are always so enthusiastic to answer them. Makes these podcasts a joy to listen to

[@MrHeyyyyy1234]

This interview was very thought provoking in regards to finiteness of certain aspects of life. Donald is so focused because of his own pure intentions. Thanks Lex for sharing these conversations with the public. Take care man.

[@strange_collection]

Amazing to see and hear Don Knuth. The quality of the people you interview is just unmatched. They had the most profound impact on computer technology.

[@matt-g-recovers]

I am blown away by this for some reason. while we share so many traits, the one I admire most about Donald Knuth (and Lex) is the discipline to grunt out the last corner cases, refinement. I used to have that and think it can be exercised as a muscle, but urgency in time has made me sloppy. Very profound takeaway for me.

[@tiadiad]

Nice surprise. Glad to hear one more episode in 2019. Thank you for the amazing work! Learning a ton from these conversations. Awe inspiring stuff.

[@akashghosh4766]

This is unbelievable. You got knuth. You got great connections..

[@ngideo]

So amazed to see the new guests you manage to get on here! Thank you Lex!

[@PhillipRhodes]

Don is still an amazingly sharp guy, even at 81! Of course, he's starting out so far ahead of us mere mortals, that he'd probably seem like a genius if he was working at 4% of his capacity. Remarkable man, great interview!

[@esra_erimez]

The importance of this video cannot be over stated. Thank you.

[@RyanHoguePassiveIncome]

Thanks for another great interview Lex!

[@shadowclan5859]

Doesn't matter where you put the add, the content is fantastic!!! If required, increase the number of adds... Do whatever is required for you to continue having these conversations.

[@AlexandruJalea]

Lex, well done on all the interviews over the year. Really enjoyed most of them.

[@CarlosAlexandre-dc3lw]

I would love to get the proper words to translate how much I'm grateful to you and your amazing work. Long live and prosper, Mr. Fridman. Every each video from you is a blast.

[@daisygonzalez2020]

Daaaaang Lex Fridman is bringing it! Thanks for the holiday uploads. You're the best!

[@KeldonA]

The answer to the last question is pure gold!

[@IamSY19]

To one more decade of this podcast 🍺

[@taotechnique]

This is my new favorite channel. I love every single one of your videos. How do you manage to get all these great people on your show?! edit: in response to your ad placements, I see no problem with them in your designated spots. Like you said, they're placed in a way to not break the flow of the conversation. I hope your other fans agree as well :)

[@alex_hiller]

Saw the thumbnail and literally swore out loud. Thank you, Lex!

[@jane3ta]

Alex Hiller “Holy F S” for me.

[@hanselpedia]

WOW! no time left to watch TV with all those great podcast :-) Thanks!

[@haseebq]

Thanks for another great Podcast! Would love it if you could interview John Carmack! Just because of the body of work he's already done and also because he's recently started looking into AGI.

[@sylvainatoz2045]

Lex, thanks for bringing us those podcasts. Very interesting, bring me knowledge and makes me think. Must required you lot of effort for little retribution. You are a very good person. Please kept up the good work in 2020. Wish you the best, wish us the best.

[@j_s_soares]

Amazing conversation. From James Gosling, Bjarne Stroustrupe and Brian Kerninghan, this was the most honest and most insightful. Brilliant youtube channel!

[@TheProf42]

Hi Lex, what a fantastic interview with one of the heros of computer science! I am professor of computer science and physics and get a lot of motivation and historically interesting information from these kind of interviews. Of course, I‘ m also a tournament chess player, so also the interviews with Carlsen, Nakamura and Kasparov are really just fantastic and I could hardly believe that you really got them as interview partners, besides all the other very interesting figures of science and technology. It seems that you yourself also have an interesting path of life with time at Google and then MIT instructor. I wonder why that apparently didn‘t work out. It seems you are only missing out on Einstein, Newton, Heisenberg, Bor and Schrödinger but got many of the most interesting living scientists and entrepreneurs as interview partners. Amazing. I love watching the interviews with people that have to say something (in contrast to e.g. run-of-the-mill politicians). Keep it on!

[@zuzusuperfly8363]

I love how indifferent Lex seems. It gives me old news anchor vibes, which is what we need more of.

[@gromov-]

It is my hope if I ever get past 80 to be half as sharp as Don Knuth. What a luminary!

[@maxheadrom3088]

Your suit gives Computers the class they deserve. Your hi-fi matches your suit! Where's the single malt? Excellent interview!

[@TwelfthRoot2]

I didn't even study computer science (aerospace engineering) but I love these interviews.

[@tanishshrivastava2442]

The greatest part about this is that he does not interrupts, unless he feels necessary. So many interviewees try to use that strategy as an unbalancing strategy.

[@keamkazi]

One of my favourite podcasts.. thank you Lex for an awesome effort and diversity of guests.

[@dadecountyboos]

I just bought MMIX 1-4 and supplementary volume. So excited to become ready for RISC-V Thanks as always for sharing these wonderful people

[@paulkiat]

I miss these old podcast formats.

[@mad1083]

Been awaiting this conversation for months!

[@rajatchopra1411]

Listening to actual scientists and experts is way better than celebrity interviews

[@gjulka]

Beautifully conducted interview of a brilliant mind.

[@billyandriam]

I have found my home on the internet thanks to your AI Podcast Lex. Thank you for doing all this!

[@yonosenada1773]

This is definitely an amazing podcast on a great subject. The interview was delightful.

[@magnusahlden7087]

Donald Knuth is the inspiration for me to get into the field of programming / software development.

[@abum91]

how did i not find this podcast earlier...thank you lex

[@AndyChamberlainMusic]

The equivalents of some of the guests of this podcast would be Archimedes and Pythagoras and Euler... crazy to imagine seeing a podcast with Pythagoras on KZbin, and then realize that's the math equivalent of what I'm seeing for computer science.

[@opodrera]

Wow! December 2022 and only now KZbin suggests your interview with Donald Knuth! I'm sure you realize what a privilege this is! To me he is to computer science what a great physicist like Newton is to physics. Awesome!

[@rosswaring2835]

Lex, this was such a treat! Don is a true inspiration and the way you clearly were both at ease with the smooth flow of insightful questions made this one of the best podcasts of the year. Great work, and great guests!

[@kylefranklin151]

Hey Lex, I’m happy for you that you’re getting very famous guests. Just remember your roots bringing people like this into greater attention for people like me to learn from them. Famous people already have large platforms to speak. Don’t be seduced by the lights.

[@rishabhshirke1175]

At last...thank you, would love to listen to Andrej Karpathy

[@broccoloodle]

Thank Lex for connecting the brilliant mind in Computer Science to the whole internet. It’s s please to meet you Sir Knuth

[@psibarpsi]

Great interview! Hope that this podcast series never ends. I do think though, that Lex should've given more time to Dr. Knuth for the last question. He clearly had more to talk about.

[@aahm6975]

Can we expect Geoffrey Hinton in near feature in the podcast

[@penciltwirler5829]

probably not, GH has back issues and can't travel far... Lex would have to travel to Toronto... tho now they could just do zoom

[@mohamedaminemahmoudi531]

I am writing this comment before watching the video because I am sure that the content will be incredibly amazing

[@RosaLei]

"What kind of browser do you have up here" 😆 lol. What a priceless question! 🥰 Donald Knuth! Mahalo Lex Fridman, another endearing podcast!

[@Kobe29261]

A man so far traveled he approaches home from the backdoor traveling away from it!!! This was sublime!

[@markkennedy9767]

Love how Knuth goes into the psychology behind how he and others like him think. I love who he mentions the right and left brain and tries to see the big picture.

[@wonseoklee80]

Abstraction. Is such a profound concept for not only computer sceince but also all human knowledge

[@tristandarracq8811]

Many thanks for your work and dedication, your podcast is fantastic! I would love to watch you debating with Ajay Agrawal or Yuval Noah Harari in 2020.

[@deeliciousplum]

I loved listening to Donald Knuth's passionate expressions for programming and of the maths underying these. Though this following need not be said, I will say it: Donald appears to have faith that a god as described in the myths of Christian writings exists. I wholeheartedly support and fight for the freedom for Donald and any religious/spiritual peep to believe in fables and in myths, so long as these beliefs do not impede nor supercede any of the human rights that our species has struggled and died for. 🌻

[@michaelzamora8056]

I'm about a minute in and I understood 60% of what lex said. This is gonna be a good one

[@lohphat]

Very good editing. The cross-fades instead of jump-cuts during the excising of short pauses is pretty smooth.

[@kwantheman2643]

Answer to the last question is priceless!

[@REALESTATEVIPPODCAST]

Damn lex, you never rest. I can't keep up! 🙂

[@blind_neighbourhoodNerd]

I just discovered this podcast. Awesome work man!!

[@fredbcarneiro]

Can I like this 1000 times??? Thanks for this led 😊

[@michielkarskens2284]

I hate computer programming with a passion, but learned my basic understanding of algorithms from Knuth’s article in communications of acm.

[@gulllars4620]

Donald Knuth is a legend. He is one of the top contributors to computer science, and sounds like he is still going strong. May he live long enough and be mentally present to finish his magnum opus and have that as a legacy as well. I loved the part around 9:15 with considering multiple levels of abstraction. I think that ability and skill combined with curiosity is what makes the best programmers or computer scientists.

[@rpsloss]

Your guests are supreme. Thanks for the work!

[@lazarus8011]

What an amazing man. Positioned at such an amazing point in history.

[@davidechiappetta]

Only a genius like Donald Knuth could invent the LR Parser.

[@micoberss5579]

Блин, сам Дональд Кнут. Круто!

[@ducklund8578]

Ееее, русские люди)))))

[@Jon-br8co]

Lex we need an interview with Andrew Yang. We been waiting months... You had several experts on AI and Economics and those guests thus far are perceiving UBI in a negative light. Mostly in part because they are not dialed in on the proposed implementation from Andrew Yang's UBI. Kai Fu Lee's argument on the labor displacement was to focus on retraining. Andrew Yang states that the retraining success rate is about 5%-15% for the manufacturing worker that were displaced from automation. You must agree that's freaking horrible. Ray's concern is that UBI will take away from other social programs and mostly focused on child's early development to provide opportunity at an early age. We all know that schools can only influence 30% of a child development and 60%-70% has most to do with what the child's home environment is like and this has to do with economic disparity... Please get Andrew Yang on for the Rebuttal of Kai Fu Lee's and Ray Dalio's perspective. You yourself know very well that AI will rip through our economy and completely redefine labor. What this mean to our society is at this moment is looking very dark. Please get Andrew Yang on your show... Please excuse my forwardness, as myself and many like me are very concerned about our future.

[@rwantare1]

"I get a surprise every time I have a bug in my program obviously" -- surely he's joking, what madness is this?? The rest of us get a surprise when we don't have a bug in our programs. I've been humbled today. Even Curry doesn't get a surprise when he misses a 3 pointer.

[@titokris5162]

hahahaahhahaha!!! O boy, can't stop laughing man!!!!

[@Stwinky]

39:40 Don: "The chair I'm sitting in is where I do ..." Lex: "Where the magic happens? hahah" Don: "Well, reading a writing" Geeks are a special breed ;)

[@seer5994]

A Legend! Thank you Mr. Knuth for all algorithms I learned !

[@ofHerWord]

At age 30 after failures i decided to choose to study computer science on my own while on welfare. My hero is this man and Ritchie and though ill never get a job due to my age ill live a happy jewosh life.

[@consumer1843]

"Donald Knuth, he is the God of programming!" -- Mark, University of Illinois, Fall semester, 1984... just like yesterday.

[@joshphilips9919]

You're a national treasure mr fridman

[@KeldonA]

9:25 - Being able to jump between and recognize levels of abstraction is key.

[@thisprofileismt]

What an absolute legend. Thank you for your work, Don!

[@filinieves8983]

I listen to lex to help fall asleep

[@Larkinchance]

A nerd is someone who distinguishes themselves in an aspect of technology, often at the expense of their charisma.. A geek is someone who distinguishes themselves in an aspect of technology, not necessarily at the expense of their charisma... From a new sub!

[@zanerobison2956]

This is a gold mine, thanks for posting.