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

In his second appearance on the podcast, Donald Knuth tells Lex Fridman the story of his first program written in 1957 decimal machine language on an IBM 650, including a tic-tac-toe program that learned to play. The conversation ranges across what makes a program beautiful, literate programming, premature optimization, and the limits of automation and AI. Knuth shares memories of John Conway and the surreal-numbers week, the Knuth-Morris-Pratt algorithm, and the hardest problem he ever solved: the birth of the giant component in random graphs. He closes with personal reflections on his 60-year marriage, Feynman, productivity, and his belief in something beyond human understanding.

• Knuth says the IBM 650 manual was so badly written he figured he must have a talent for computing because he could write a better one.
  00:03:04
• His goal with his first program wasn't to find a large prime but just to see the lights flash and understand the magical machine.
  00:10:44
• Knuth reacts skeptically to OpenAI Codex/Copilot, worrying we are losing more and more control over what machines do.
  00:33:36
• He declares he is on the side of honor, happiness, and understanding, and would never recommend a student work on autonomous weapons.
  00:37:15
• On consciousness and whether the mind exceeds computation, Knuth insists it is unanswerable and that he is no better placed than anyone to say.
  00:49:45
• He describes writing Surreal Numbers in a single intense week in an Oslo hotel, feeling like he was channeling, then losing the muse entirely.
  01:06:00
• The denominator 23023 factoring into 7x11x13x23 was the clue that cracked the giant-component problem for him.
  01:46:38
• Knuth states his belief that God exists and that he tries to resonate with something beyond human understanding.
  02:14:42

• Knuth's third program was a self-learning tic-tac-toe with three 'brains'; it converged to a safe draw after about 600 games.
  00:11:14
• Charles Babbage had planned to program tic-tac-toe for his unfinished machine over a hundred years earlier.
  00:16:00
• A Fortran compiler Knuth studied spent more than 80% of its time reading the comments card, illustrating premature optimization.
  00:45:01
• John Conway wondered whether it was immoral to shut the computer off after an interesting play of the Game of Life.
  00:58:05
• During a party, Conway invented a lattice theory of stable marriages that Knuth used in his lecture the next day.
  01:08:37
• Knuth says he never really enjoyed kissing until he found how his wife Jill did it; they have been married 60 years.
  01:11:44
• Feynman challenged Knuth's arrow notation by asking about complex numbers of arrows.
  01:22:42
• Knuth wrote a paper titled 'Automata Theory Can Be Useful' after a stack-automaton theorem helped him crack string matching.
  01:32:06
• Bill Gates visited Stanford and was impressed by Knuth's giant-component explanation while being pitched to fund a CS building.
  01:48:10
• Knuth says the most important thing he learned was how to be interested in almost anything and never bored.
  02:11:35