Knuth, Donald

computer scientist, Turing Award winner, author of The Art of Computer Programming, creator of TeX

Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life

Lex Fridman Podcast · Sep 9, 2021

• Donald Knuth
• IBM 650 early programming
• literate programming
• premature optimization
• John Conway and surreal numbers
• Morris-Pratt-Knuth algorithm
• stack automata and Steve Cook
• random graph evolution and giant component
• TeX and open source
• free will and Game of Life
• consciousness and computation
• stable marriage

Core ideas

Knuth recounts his earliest programming experiences on the IBM 650 in 1957 — writing decimal machine-language code (no assembler existed yet), debugging by dialing switches at the console late at night, and building three successive programs: a number-factoring program, a binary-to-decimal converter, and a tic-tac-toe program with three "brains" (random play, a canned optimal strategy, and a learning brain using reinforcement that adjusted single-digit "scores" for board positions, exploiting board symmetries to fit within the machine's tiny 20,000-digit memory). He notes this learning brain converged after about 600 games to a safe draw against itself because its reward function only penalized losing rather than rewarding winning — his first hands-on encounter with what would later be called machine learning, though he stresses that at the time he had no interest in the philosophical questions of computation (Turing, computability) that only engaged him academically much later as a required course.

He discusses how a programmer's individual style is legible in code — not through superficial stylistic choices like variable naming, but through conceptual choices (e.g., recognizing when two goals can be accomplished in one machine instruction rather than two) — and connects this to his development of "literate programming," the idea (which he considers the most significant outcome of the TeX project) that programs should be written to be read by humans, interleaving natural-language explanation with code, as exemplified by the book Physically Based Rendering. He resists giving a single definition of programming "beauty," listing multiple valid criteria (working at all, ease of understanding, literate clarity, and humor — citing his own hidden jokes in The Art of Computer Programming, including an RSA-encrypted cipher message in Volume 2 designed to remain unbreakable for decades) and connects this to his coined term "premature optimization is the root of all evil," clarifying that it originated from his experience as a compiler writer discovering (via profiling a Fortran compiler that spent 80% of its time reading comment cards) that programmers' intuitions about which code sections are computationally expensive are usually wrong, and that over-optimizing prematurely can also destroy a program's flexibility for future changes — a case for the value of "late binding" and deferred decisions.

Knuth discusses his intellectual relationship with John Conway, including how a single lunch napkin covered in Conway's unpublished "theory of numbers" led Knuth to write the book Surreal Numbers during an intensely focused, almost trance-like week in a Norwegian hotel room in 1972 (writing in a Socratic dialogue format, discovering the theory as his fictional characters would, and losing the ability to write anything more the moment he finished) — and a later spontaneous collaboration where Conway proved during a party that the set of stable marriages forms a lattice, a result Knuth used the next day in a lecture. He also describes the origins of the Morris-Pratt-Knuth string-matching algorithm — independently co-discovered by three researchers (Jim Morris, Vaughan Pratt, and Knuth) working on different but related problems — and credits a separate, purely theoretical result by Steve Cook about "stack automata" with directly enabling him to solve a difficult string-matching efficiency problem he'd been stuck on, an experience that changed his view of automata theory's practical value.

He identifies the hardest problem he ever worked on as proving results about the "birth of the giant component" in random graph evolution (connected to Erdős–Rényi random graph theory and, unexpectedly, Bose-Einstein statistics in physics): starting from a rumor (later shown false, though nearly true) that random graphs almost always have only one component containing a cycle at any point during their evolution, Knuth computed transition probabilities between successive "complexity" states of the evolving graph, noticed the denominators of his computed probabilities factored suspiciously into small primes (23023 = 7×11×13×23), and used that pattern to find a simplifying reformulation via logarithms — eventually proving the true (non-100%) probability that the rumor holds, a result he says related closely enough to physics that he happened to present it on a blackboard to Bill Gates (visiting Stanford to discuss donating to a computer science building) the very day after the breakthrough.

On open source, Knuth explains he released TeX without proprietary restriction because he had no financial need for additional income beyond a comfortable threshold, contrasting this with what he saw as FORTRAN's healthy openness (versus how proprietary typesetting languages had held back the printing industry by locking customers to specific manufacturers); he distinguishes this from a general principle, arguing non-trivial, high-value software (citing Photoshop's sophisticated multi-step undo algorithm) is worth charging for, while trivial software shouldn't be. He discusses the "pi graph" and other examples of using the digits of π as a source of unbiased test data in his puzzle and graph-labeling work (including a "graceful labeling" puzzle using the 49 contiguous U.S. states, later solved perfectly by a colleague whose solution coincidentally encoded π's digits along a west-to-east path). On AI and automation, Knuth expresses measured concern about ceding control to systems whose reasoning isn't understood (invoking a Caltech colleague's view that "it doesn't matter whether the answer is right, just whether it makes people happy") and specifically states he would never recommend a student build weapons systems, while remaining optimistic overall — reasoning that since civilization already runs on millions of interdependent human-built systems that mostly work despite nobody fully understanding all of them, there's reason for cautious optimism about AI too, so long as human oversight and rationality persist.

On deeper philosophical questions, Knuth declines to take a position on whether human consciousness or mathematical insight exceeds computation (as Roger Penrose has argued), calling it a question "beyond knowledge" — not yet well-defined enough to formalize — rather than asserting it's permanently unanswerable, and cites the Game of Life as clarifying his own thinking about free will: the system is fully deterministic, yet emergent "organisms" within it appear to behave as if alive, which he finds analogous to how humans might experience free will atop deterministic physical processes. He closes with reflections on his 60-year marriage to Jill (framing "stable marriage," ironically also a technical term he's worked on, as requiring ongoing compromise rather than constant bliss), his admiration for Feynman's intellectual honesty (recounting Feynman publicly critiquing a physics textbook written by his own host in Brazil to expose credentialism over real understanding), a scheduling principle inherited from his mother ("see something that needs to be done and do it," prioritizing the least-wanted task first rather than formal planning), and closing advice to pursue work one feels personally "called" to do rather than what's trendy, framing the core life skill as learning to find genuine interest and beauty in almost anything rather than needing to be entertained.

Excerpts