Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life | Lex Fridman Podcast

[@lexfridman]

Here are the timestamps. Please check out our sponsors to support this podcast. 0:00 - Introduction & sponsor mentions: - Coinbase: coinbase.com/lex to get $5 in free Bitcoin - InsideTracker: insidetracker.com/lex and use code Lex25 to get 25% off - NetSuite: netsuite.com/lex to get free product tour - ExpressVPN: expressvpn.com/lexpod and use code LexPod to get 3 months free - BetterHelp: betterhelp.com/lex to get 10% off 0:48 - First programs 24:11 - Literate programming 27:20 - Beauty in programming 33:15 - OpenAI 42:26 - Optimization 48:31 - Consciousness 57:14 - Conway's game of life 1:10:01 - Stable marriage 1:13:21 - Richard Feynman 1:24:15 - Knuth-Morris-Pratt Algorithm 1:33:47 - Hardest problem 1:51:26 - Open source 1:56:39 - Favorite symbols 2:06:12 - Productivity 2:13:53 - Meaning of life

[@MM-gd1be]

Thank you for the quality information I look forward to you as much as jre

[@janglestick]

very cool ... in most of those timestamp categories, there is in fact a quotable answer. great interview. Up with the algorithmythists ! how funny is it that Knuth uses globals? Dynamic programming is having a bit of a renaissance.

[@aaron8344]

Thank you for keeping an old man valuable. You challenged him like a child because you recognised that it is all we are to him. Based on this interview, I'd like to see you challenge more people at the end of their line. Good for your podcast - sure. Good for these people who changed the world - you made their day - remind them of their value and perhaps reinspire them. Really good job.

[@OpticalAntenna]

Unfortunately comments that have given me the biggest laugh are ones where the coder admits they have no idea what they are doing. One person right in the middle of an attempt to implement an extended kalman filter began naming variables i_have_no_idea and fudge_factor. We instated peer review process immediately.

[@corineskipper1919]

@@MM-gd1be how Rogan is not a truther and NOT someone to b trusted for ANY information

[@Simon-jw1ww]

The first name you learn in computer science is "Alan Turing". The second one is Donald Knuth. It's sad that we can't hear/see Turing in your Podcast. But you are realy lucky to have the opportunity to speak to the one and only Donald Knuth! A man whose ideas are in every single modern computer on this planet! The definition of a legend!

[@lugas2267]

i mean we are lucky…

[@RobertTempleton64]

If you really learn computer science, the names "Charles Babbage" and "Ada Lovelace" might crop up. The real pioneers of computer science in a time when its actuality was virtually improbable.

[@NinjaofApathy]

Fun question: what historical person active within the last 150 years would you have visit the Lex podcast? (You can only pick one). Mine might be Tesla.

[@IntuitiveLeap]

@@NinjaofApathy Maybe the inventor of the Sumerian abacus? Whoever that is.

[@axiom1650]

@@NinjaofApathy Einstein

[@remixisthis]

Your doing an immeasurable service getting these rare long form interviews from programming legends. I really appreciate it and incredibly grateful we can all hear more from these hard to reach figures who usually don’t get to have in-depth conversations nowadays

[@sunte91]

I agree 100%

[@TonyDiCroce]

@Lex Fridman ▫️◽ you should find a podcast with a dumber audience than this one. Here, you run the risk that some hacker might choose to make an example out of you.

[@krabkrabkrab]

"You're"

[@dreadsdomain]

Gimme your fav programming guest on the lex podcast… pls :)

[@utubez0red]

We are so lucky to be in the privileged position to listen to scientists of this magnitude talking in such a humbling way about subjects like consciousness. Thank you Lex for the value you add in this world.

[@dalimrabet3087]

Donald: "I am doing this at night when nobody else was around" Lex: "of course" This resonates on so many levels !

[@alexandreconlon8990]

The confidence with which Lex said that really got to me.

[@DaveWhoa]

I find 3am to be a beautiful hour to do some coding

[@flexairz]

And girls were introduced much later in Dons life...

[@GeronimOCZECH]

@@DaveWhoa Yes, becouse it's only you and your keyboard. In the daytime there is too many distractions imo.

[@jamesevans2507]

@@DaveWhoa I would probably do it too if I was privileged enough to not have to work 9-5

[@fosres]

Hello Lex. I honestly appreciate the time and effort you put into convincing Donald Knuth to speak on your show. Keep up the awesome conversations!

[@zomroxy2458]

I really love how Donald Knuth just genuinaly loves coding, it's vividness gives me motivation.

[@ozymet]

"I wrote program because it was fun to write programs" - For how many of us have been a real and pure joy to write something that just worked? Long before we became corporate programmers.

[@robinkaraa3369]

We need John Camack, please Lex make it happen :)

[@lashropa]

Oh great idea! It was such a treat to see him on Rogan, Lex's style would really scratch that technical itch, though. Lex, do it!

[@remixisthis]

Let’s go!!

[@apoage]

Wow thaw would be so awesome ..

[@TonyDiCroce]

And ask him about functional programming.... and Abrash.

[@cbennoes]

@@lashropa absolutely, that would be amazing

[@adels1388]

I love he is actually calculating 3^5 in the interview.

[@JameyKirby]

I got Dr. Knuth's volume III when I was a teenager. I learned SO MUCH from Dr. Knuth books. I remember implementing soundexing in BASIC circa 1985 based on his book. Thank you for doing this second interview.

[@karu6111]

surprised that there's not more views, this man is a legend, well, at least based on how many recommends his books on the concepts regarding computer science.

[@3227998]

A living legend - Donald Knuth. They should have computer scientists appreciation course at schools and include Mr. Knuth to that course.

[@jonathanpopham5483]

someone asked Jimi Hendrix what it felt like to be the greatest programmer alive, he said "I don't know, ask Donald Knuth"

[@nteasushz]

Acid is the root of all evil

[@keepme5225]

Access to Don Knuth’s time is by far one of Lex’s most valuable leverages

[@arawproductions3156]

so glad you keep getting CS goats on the pod

[@justinjoseph5582]

First Edit: I normally never comment on KZbin videos, but just a guy from africa with the entire collection of the art of computer programming, already love this podcast and I am in a few minutes

[@ken888wong]

I spent too many hours fixing latex bugs on my papers. Thank you Lex for doing these interviews of these pillars of computer science. It is interesting to hear the human side rather than the theorems and/or products of their work. Please do an interview the Dr Stephen Cook; he's getting up there in age.

[@damislav]

the fact that we are alive in the same time as him, is amazing

[@ronj9448]

Amazed to see a current interview with Knuth. I was introduced to his work in college where I needed better quality algorthms to get a better grade (early 1980s). I went to the library and every book seemed to reference Knuth so I decided to look for the source. Wow. Changed my life in a few ways both education and personal.

[@EricHrahsel]

I have a stutter. And this feels so motivating and Donald is so brave to attend this talk

[@anitsh]

Thank you @Lex Fridman for this! It's an honor to hear Donald. Like many of us in this profession, I am thankful to his contributions.

[@Angelo_Nicolson]

I love his view of money. I wish more people thought like that. We are surrounded by so much greed and thirst for power.

[@gritmcnasty5592]

I’ve tried to listen to these podcasts to fall asleep, bad idea! I always find myself listening to the very end, I get so into to the topics even when I don’t know a thing about the topic at hand, the only podcast that does this to me! 😂

[@consumer1843]

Dr. Knuth is a great teacher. Dr. Fridman is an accomplished conversationist.

[@peterfireflylund]

Knuth, the homeboy of all of us! I never really liked attribute grammar but thank you, thank you for teaching me about shift-xor random number generators!

[@MrEloyina]

I am from a city in PERÚ, we dont have this type of amazing talks. Thank you for sharing.

[@nteasushz]

But you have peyote!?

[@fredb2022]

Wow! Thank you to our host and guest. This is not my field and I was afraid I had aimed too high. Only midway through did I “connect.” Glad I stuck it out.

[@palefire4454]

GOD BLESS YOU, LEX, THANK YOU FOR BRINGING US KNUTH, WHAT A LEGEND!!!

[@vorburger]

Thanks!

[@stanuel]

Wow, fantastic conversation! I love how he's able to recall the exact first programs he wrote and how it played out. What a legend

[@ir3mix3d]

So cool to hear a pioneer show us his perception of the timeline!

[@FacesintheStone]

Wonderful guest! It’s so great to learn about how it was in the old IBM days compared to controls and automation today. Keep bringing these epic guests Lex my man!

[@AminKhalek]

“When I met John Conway, you were minus twenty years old.” 😂

[@video-request-response]

That was amazing!!!!

[@ninadesianti9587]

Thank you for the great interview, Lex! Thank you for introducing me to another great guest! Your podcast made me want to learn more about the work of Stephen Wolfram, Joscha Bach, and now Donald Knuth! Listening to them and other great thinkers scares me, it’s FOMO, fear of missing out. But it’s all good, at least it’s not boring, more stuff to learn!

[@tdbulvan2177]

“I had more bugs in it than number of lines of code” - so freaking awesome of a statement

[@2894031]

This is totally f-ing amazing, chatting with such a legend! This is the best channel on YT

[@fiifianyimadu6118]

The most respectful, appropriating part of the web is the learned side of it. I like this side with no sour grapes and thumb-downs, etc. I hope I am welcome

[@nabeelhasan6593]

"The word open source didn't exist at the time" :O This simple statement shows how much these people are important

[@mubiratan]

The master, Professor Donald Knuth!

[@ushiferreyra]

I absolutely agree about finding a thing boring many times means you haven't been exposed to them with clarity and mostly haven't realized that there is in fact beauty in it. It's refreshing to know more people share this sentiment.

[@Sliverth]

Excellent interview and a guest who’s a giant in the field. I’m forwarding this to my grandson, a high school senior and headed to STEM.

[@measure5141]

Wouldn't know what to do without you Lex.

[@hyperreal]

The visuals for this really help, thank you.

[@STARBOY-ko4kb]

I lived everytime when i watch these podcasts.

[@focusEngineered]

Lex YOU ARE AWESOME. I watched the first Episode +10 times, Thanks for hosting Don one more time. He is one of a kind scientist

[@rvdheij]

Thank you for doing these interviews. It's a true pleasure to hear Don Knuth and others you interviewed.

[@FilipiVianna]

Really really wonderful conversation... It took me hours to watch because I was googling for references, like On Intelligence and Surreal Numbers... Donald Knuth has such a charismatic personality that I had the pleasure to chat during some International Free Software Forum in Porto Alegre, Brazil... Congratulations, Lex Fridman, well-conducted interview.

[@gr8xpect8ion]

Amazing interview, Lex does such a great job with these legendary figures. These interviews are part of the historical record for this inflection point in human history. Historians of the future thank you Lex!

[@programmer1379]

So awesome !! Enjoyed the chapter about the hardest problem; watching professor Knuth describe the research process and how he managed to finally crack the problem is amazing. Many lessons to learn from this podcast. Thank you for sharing, Lex !

[@seer5994]

Thank you for the interview !! Please do more interviews with Mr. Knuth!

[@SincerelyBradley]

Someone I absolutely look up to. A mentor of mine when I got my first software job gave me his book "Stuff Computer Scientists Rarely Talk About" and I've been inspired by him ever since.

[@raphaeld9270]

Thanks, "Things a Computer Scientist Rarely Talks About" looks like a great read.

[@raphaeld9270]

The wikipedia link: en.wikipedia.org/wiki/Things_a_Computer_Scientist_Rarely_Talks_About

[@vgoj]

Donald was visibly emotionally touched by the memories of Conway`s. Beautiful minds.

[@TheGunmanChannel]

Very interesting stuff.

[@skwest]

Holy Cow!!! Donald E. Knuth: The Man, The Legend! I can't wait to listen... I'll scatter his books around me (thank you, Addison Wesley) like fragrant rose petals, as I do. You rock, Lex.

[@reihanehiranmanesh9643]

You have done the interview I have long waited for OMG. Lemme watch this ;)

[@SeekHunt1334]

Thank you. Make the next one with Dr. Knuth longer?

[@warfreddy6968]

Hearing Donald talk about using old airgapped machines and soon upgrading to ssd is the most wholesome example i can imagine. Lol.

[@sm_xiii]

It is such a fanboy moment for me. I want to achieve that level of enthusiasm and confidence in my life, where the feeling that existing word processors are not capable enough will lead me to even think of creating something of my own.

[@rusi6219]

Stop optimizing your code and you're halfway there haha

[@coincrazy3563]

Lex is a budding hero of new media

[@Yolo_Swagins]

Lex love your podcast. Thank you.

[@marcgarridocasas9672]

6:38 I love the fact that Lex had to stop talking due to a smile, he really likes working hard instead of getting consistent sleep.

[@calebbarnes5452]

Lex is my role model

[@6pat]

Enjoyed very much this episode, best health to Mr Knuth.

[@metalstraw6700]

We need a Don podcast every year

[@PankajDoharey]

I am so happy to see him in good health.

[@bruhbigchungus]

Don is such a legend, glad he's still with us

[@MrAcenit]

37:45 Phenomenal insight - literally the need for AI Ethics/Safetyl - When the code you write is impacting people's lives in a significant way, humans better understand what the computer's doing!

[@thebeckettgroup]

Thanks @Lex ~ Amazing... the one and only Father of Algorithms... Donald Knuth

[@mohan1519]

"I'm on the side of understanding" - could not have said better. I only hope people listen to experts in the field.

[@mohan1519]

He's also such a wonderful human... like the way he spoke...

[@Nataspin900]

Can you interview linus torvalds?

[@matthewlawrence2395]

The Lexbot is producing more content then the human Lex could.

[@Pawai-e8d]

### Summary **Introduction (**0:00** - **0:48**):** The podcast host introduces Donald Knuth, a legendary computer scientist awarded the Turing Award, known for his contributions to algorithm analysis and as the author of "The Art of Computer Programming." Knuth is also recognized for creating TeX, leading to LaTeX. The host shares a personal anecdote about writing a letter to Knuth and establishing a meaningful interaction with him. The episode is part of the Lex Fridman Podcast. **First Programs (**0:48** - **24:11**):** Donald Knuth discusses his early programming experiences. Starting in 1957, he wrote his first large-scale program in decimal machine language for the IBM 650. He describes the learning process, including debugging, which involved manually inputting and testing instructions late at night. His initial programs included number factoring, converting numbers, and a tic-tac-toe game. He shares the intricacies of programming on the IBM 650, including optimizing memory and machine learning aspects in his tic-tac-toe program. Knuth highlights the trial and error involved in early programming and the joy of making machines perform complex tasks. **Literate Programming (**24:11** - **27:20**):** Knuth discusses the concept of literate programming, which he pioneered during his work on TeX. Literate programming combines English documentation with programming code, making the code more understandable for humans. This approach emphasizes the importance of writing code intended for human readers, not just machines. Knuth advocates for this method as it enhances readability and maintainability of code, allowing future programmers (including oneself) to understand the code better. He cites the book "Physically Based Rendering" as a notable example of literate programming. **Beauty in Programming (**27:20** - **29:06**):** When asked about what makes a program beautiful, Knuth explains that beauty can be subjective and multifaceted. It can range from the program simply functioning correctly to being easily understandable, elegantly solving a problem, or having wit and humor in its comments. He notes that different criteria can define beauty, depending on the context and what the programmer values at the moment. ### OpenAI (33:15) SM-GPT-Donald Knuth Programming, Algorithms, Hard Problems & the Game of Life Lex Fridman Podcast #219The discussion about OpenAI highlights its advancements in AI technology, particularly through its language model, which is capable of generating coherent text and assisting in coding via tools like OpenAI Codex and GitHub Copilot. The conversation delves into the implications of such technology, touching on the potential loss of human control over automated systems and the philosophical aspects of truth versus happiness in machine decision-making. The speaker expresses caution, suggesting that while AI can be beneficial, particularly in areas like medical diagnosis, there's a need to be wary of negative impacts, such as the development of autonomous weapon systems. Ultimately, there's a nuanced view of AI as both a potential help and a hazard, emphasizing responsible use and cautious optimism about human ingenuity overcoming challenges. ### Optimization (42:26) The discussion revolves around the importance and pitfalls of optimization in programming. The phrase "premature optimization is the root of all evil" is explored, emphasizing that focusing too much on optimizing code too early can lead to inefficiencies and difficulties in future code modification. The speaker describes the historical context of optimization, originally focused on improving compiler performance, and underscores the importance of empirical study and profiling to understand where optimization efforts should be placed. This cautious approach to optimization reflects a broader principle in computer science of deferring decisions (late binding) to keep code flexible and maintainable. ### Consciousness (48:31) The conversation about consciousness and computation explores whether the human mind and consciousness can be fully explained and replicated by computational means. Referencing Roger Penrose's ideas, it's discussed whether human cognition and creativity transcend computational capabilities. The speaker expresses skepticism about the potential to fully understand or replicate consciousness through artificial intelligence, suggesting that questions about consciousness might remain beyond the reach of current scientific knowledge. Despite advancements in AI and neurological studies, the speaker maintains a stance that some aspects of consciousness may never be fully comprehended. ### Conway's Game of Life (57:14) The discussion turns to Conway's Game of Life, a cellular automaton that demonstrates complex behavior emerging from simple rules. The game is lauded for illustrating the concepts of determinism and free will. The speaker reflects on how Conway's game can create the illusion of life and consciousness from deterministic processes, suggesting a parallel to our universe if it is finite. There's further conversation on the technical and analytical methods that can be applied to understand the Game of Life, highlighting exercises and contributions from researchers like Bill Gosper that enable deeper analysis of the game's evolving patterns. ### 1:10:01 - Stable Marriage The speaker recounts an instance with John Conway in Montreal, where they met between the speaker's sixth and seventh lecture in a series on stable marriages. At a party, Conway quickly developed a new and intricate theory that expanded on the concept, notably proving that the set of all stable marriages forms a lattice. This was a significant addition to the existing theory and the speaker was able to incorporate this new insight into his lecture the following day, showcasing Conway's quick and brilliant problem-solving skills. ### 1:13:21 - Richard Feynman The conversation shifts to discussing Richard Feynman, noted for his influential contributions to physics and his unique, impactful method of teaching. The speaker mentions attending each other's lectures at Caltech and highlights one detailed anecdote about Feynman's time in Brazil, criticizing the educational methods which focused more on passing exams rather than truly understanding physics. This anecdote underscores Feynman's commitment to genuine learning and the continuing problem of credentialism in education. The speaker also reminisces about Feynman's curiosity in large numbers and complex mathematics, specifically inquiring about potential in the Knuth arrow notation for handling complex numbers. ### 1:24:15 - Knuth-Morris-Pratt Algorithm Here, the discussion is about the development and significance of the Knuth-Morris-Pratt (KMP) algorithm. The speaker explains it should technically be called Morris-Pratt-Knuth due to alphabetical order but chose to use KMP. This algorithm addresses efficiently finding if a word or pattern exists within a large text, avoiding the need to start from scratch for each new letter after a failed match. Jim Morris initially introduced a more efficient searching method and the KMP algorithm became fundamental, avoiding redundant checks and significantly speeding up search processes in texts, widely used in various search engines and text processing tasks.

[@courseprovider9871]

i still havent finished but still this is brilliant episode!

[@oguntigli882]

Great interview Lex, thanks so much.

[@nephiindustries]

The beauty in programming part is appreciated 👍🏼

[@94franz]

What a legendary scientist so many PhDs were blessed with his name! talking about LaTeX, have you ever interviewed Leslie Lamport who is yet another CS genious

[@mrknowmyself]

I enjoyed this dialog so much. Was very thoughtful thank u!

[@dadecountyboos]

round two thank you, as always for this work you do. Reading MMIX for the Millennium & supplementary text last few months. Knuth is truly incredible

[@erpthompsonqueen9130]

Thank you. Honoring Parent. Brilliant.

[@CaseyAtchison]

Had a job interview last week and got asked "who's the smartest person you know" and I reflexively spat out Don Knuth ... they were a younger crowd.

[@py_a_thon]

Paul Dirac? Although to be fair, I never met him. I only see his shadow. Ramanujan is another fun answer I think. You need to know the reason you answer that answer far more than you need to answer what others wish to hear. That is the secret hack of those inane interview questions. Or so my opinion goes.

[@CaseyAtchison]

@@py_a_thon If they hadn't been fed that question it could have revealed a lot about me, but they seemed to be expecting a different answer and were completely unimpressed. I'm pretty sure they didn't know who Karl Popper was either.

[@py_a_thon]

@@CaseyAtchison The answer to a question such as that should probably involve a brief description of the person, and why that is your answer.

[@OpticalAntenna]

He almost mentions Zen and the art of motorcycle maintenance. He must think philosophically for that to be on the tip of his tongue. Wonder when he last read it, one of my favorite books as it brings back memories of traveling on the back of my father's motorcycle and camping out.

[@go5582]

hi . i really enjoyed this video. host ,in 1:30:24 ,your guest has answered and reached his mathmatical threshold. very sincere. thanks for your time.

[@solderbuff]

35:50 - First, programmers like Knuth were really mathematicians who solved a problem mathematically and then wrote a program. Then agile development came along and programmers started to ship something that seems to work until another bug report shows up. And now increasingly programmers don’t even know how the result is achieved (with deep learning and stuff).

[@jasonlind3065]

Agreed

[@AlvinYakitori060]

They do import, fit, predict and call themselves “Data Scientists” and don’t even know performance metrics, terrible…

[@nikhilk7493]

he is one of the kind

[@swinehorde9118]

Hell yeah, Donald. A wellspring of knowledge!

[@moneymarosx]

How many black suits does Lex have? Awesome content! Love your stuff Lex. Keep it up, thank you.

[@thefrankiepalmeri]

Anyone else noticing the inconsistency in the quality of some of these videos? Especially the last two uploads seem quiet.

[@AstonnMartin2003]

Lex, I love you man and enjoy your podcast emensly. With one caviot of an observation from watching the podcast. No disrespect intended, however, the manner of your asking questions can and does confuses your quest. Not to mention your audience. When asking a question to a guests, and they start to answer, you'll interrupt with another question/questios. There were times that I felt sorry for the taxing rapid fire questions and the poor old man struggling.

[@michaelschasteen2407]

dude awesome thank you both.... i'm realy at aweeeeeee

[@rebeccaavendano9442]

Insightful conversation about consciousness!

[@davidwalz3317]

“Life is a binary search..” me stops and think deeply about this for days. Haha

[@Channel-gv2gw]

please give me the timestamp

[@jacobbisher6291]

This would make a great T shirt. 2:10:44

[@supermario1982171]

This really stood out to me also

[@georgejaniec]

I literally come back to the algorithm itself ;)

[@michaelschasteen2407]

incredible...Thank you gentlemen.........

[@venkateswarans1012]

20:03 Donald : I was pretty much a machine. Lex : yeah I got you

[@robocop30301]

This is awesome! Thanks Lex

[@janew2108]

How do you get these power house guests?! We’re so lucky! Thank you Mr. Knuth. 😀

[@luserdroog]

Please, please, keep working on TAOCP. Hoping to see the later volumes on parsing and compilers.

[@pariscatblue]

wow!!!! Lex, it was deeply touching, in many ways.. THANKS!

[@andrevale2079]

Would love to see you interviewing Terence Parr!

[@connoly6329]

Respect to the legend!

[@geez6666]

Jesus, thanks Lex! immediately liked this one before even listening to the interview(FYI: Just like Knuth books...hard stuff...lol)