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

Lex Fridman visits Donald Knuth at his home for a wide-ranging conversation spanning his first encounter with an IBM 650 in 1957 through the decades-long writing of The Art of Computer Programming. Knuth explains 'geek' thinking as the ability to jump between levels of abstraction, walks through the volumes of his magnum opus, and describes his daily writing and programming routine. The talk ranges into literature, the art versus science of programming, his intuition that P equals NP, and the limits of artificial intelligence. He also discusses his study of the Bible, his prostate cancer diagnosis, his belief in God, and finishing a long-desired musical composition, ending with what he would ask God.

• Knuth says when asked what about computing surprised him he rattled off a couple dozen things but could not name a single thing he would have correctly predicted.
  00:06:19
• Knuth states he believes P may actually equal NP, contrary to most computer scientists.
  00:57:59
• He argues that even if P equals NP it would not yield usable algorithms, because vastly more algorithms exist than humans can ever discover or comprehend.
  00:58:33
• On AI he warns about people believing they've succeeded, citing a huge gap between real understanding and the illusion of understanding.
  01:11:47
• Knuth describes coming to terms with mortality after his father's death and again after his 2006 prostate cancer diagnosis, accepting he might die with no expectation he deserved better.
  01:28:32
• He reveals a lifelong unfulfilled goal to compose a piece of music, which premiered on his 80th birthday.
  01:29:39
• He recalls being furious when Volume 2 was reprinted because the number '2' in the page numbers looked ugly to him, forcing him to retune the whole typeface.
  01:36:06

• The IBM 650 had only 2,000 words of memory and adding two numbers took about three milliseconds because of the spinning drum.
  00:04:44
• Knuth estimates 'geeks' make up about 2% of the population, a figure he says held fairly constant over his career.
  00:08:00
• He admires Alan Turing as the first fully legitimate geek, who wrote numbers backwards (left to right) to think like a computer.
  00:13:13
• Knuth's literate programming philosophy: good technical writing says everything twice, formally and informally, to lodge concepts in the reader's brain.
  00:20:08
• The Binary Decision Diagram (BDD), invented by Randy Bryant in 1986, was a total surprise that added a whole new section to his book.
  00:50:35
• Knuth lives by a 'point eight is enough' philosophy: an organism happy about 80% of the time is better designed than one happy all the time.
  01:25:58
• He notes that all numbers humans can comprehend are still vastly smaller than almost all finite numbers, citing Knuth arrow notation and 'supernatural numbers'.
  01:40:47
• Asked what he would ask God, Knuth jokes: 'What kind of browser do you have up here?'
  01:44:29

Books, products and media the guest or host genuinely endorsed here — with the buy link.

Affiliate link — we may earn a commission at no extra cost to you.