The Bottom of Things

Every December, Donald Knuth does something most 87-year-olds do not: he stands before a packed Stanford auditorium and delivers a lecture dense enough to make graduate students take notes. This year's installment, "Adventures with Knight's Tours," might be his most delightfully obsessive yet.

The knight's tour problem — moving a chess knight to visit every square on a board exactly once — sounds like a parlor trick. It's not. Knuth marshaled 832 CPU cores to explore the solution space of an 8×8 board, which contains more than 13 trillion distinct tours. He didn't just count them. He computed optimal solutions, discovered previously unknown symmetries, and presented the results with the aesthetic sensibility of a man who has spent sixty years believing mathematics should be beautiful.

What makes these Christmas lectures legendary isn't the raw computation — it's the insistence that even a "solved" problem has layers worth excavating. The knight's tour has been studied since Euler. Knuth found new things to say about it. That's the difference between knowing a result and understanding it.

When the father of algorithm analysis weighs in on large language models, people listen — even if they don't like what he says. At Georgia Tech's Turing Minds Q&A in October 2025, Knuth called ChatGPT's output "extremely impressive, sometimes astonishingly so" before adding the caveat that defined the evening: it is "emphatically not for me."

This isn't a Luddite dismissal. Knuth has experimented with LLMs, feeding them mathematical problems and evaluating their "wordsmithing." His concern is precision. The man who introduced the concept of algorithmic analysis — who literally wrote the book on measuring computational correctness — doesn't trust a system that's right 95% of the time and confidently wrong the other 5%. For Knuth, a tool that occasionally fabricates proofs isn't a drafting assistant. It's a liability.

The deeper point resonates beyond AI. Knuth has always optimized for depth over breadth, rejecting email, social media, and now AI assistants — not because he fears technology, but because he's done the cost-benefit analysis on distraction and concluded it doesn't factor. In an era where every knowledge worker is being nudged toward AI copilots, his refusal is a data point worth contemplating.

The Donald E. Knuth Prize is the closest thing theoretical computer science has to a lifetime achievement award. In 2025, it went to Micha Sharir for decades of work in computational geometry — the mathematics of how computers reason about shapes, distances, and spatial relationships.

Sharir's contributions underpin everything from GPS routing to robotic motion planning to the collision detection in your favorite video game. The award, given jointly by ACM's SIGACT and IEEE's TCMF, follows last year's recognition of Rajeev Alur for his work on automata theory.

That a prize bearing Knuth's name consistently goes to researchers whose work is both theoretically profound and practically consequential says something about the man himself. He's never been interested in theory for theory's sake. Every algorithm in TAOCP comes with benchmarks. Every proof comes with code.

In the late 1950s, a young undergraduate at Case Institute of Technology (now Case Western Reserve) wrote his first programs on an IBM 650 — a drum-memory computer the size of a refrigerator. That student was Donald Knuth, and the experience convinced him that computing deserved the same rigor applied to mathematics.

This spring, Knuth returned to Cleveland for the grand reopening of Case Western's computer science department. He didn't just cut a ribbon. He suggested the department hang artwork featuring knight's tour patterns — a characteristically Knuthian gift, merging mathematical beauty with institutional pride. The building now displays these algorithmic designs alongside its state-of-the-art labs.

The symmetry is almost too perfect: the man who started programming on vacuum tubes is now decorating the walls of a 21st-century CS department with the output of 832-core computations. The tools changed. The curiosity didn't.

The Art of Computer Programming is the most ambitious project in computer science publishing. Begun in 1962, it was originally planned as seven volumes. Volume 4 alone has grown so large that Knuth publishes it in installments called "fascicles" — a word borrowed from Victorian-era serial publishing. Fascicle 7, "Constraint Satisfaction," arrived in February 2025.

Constraint satisfaction problems (CSPs) are the backbone of everything from Sudoku solvers to airline scheduling to chip design verification. Knuth's treatment transforms what many practitioners know as "just call the SAT solver" into a rich mathematical landscape, complete with his trademark exercises rated by difficulty on a scale from 1 to 50.

Here's the stat that matters: Knuth paused TAOCP for nineteen years starting in 1978 to create TeX — because the typesetting of his own books offended him. He literally invented a new typesetting system, proved it correct, and went back to writing. The "detour" became the global standard for scientific publishing. Every physics paper, every math journal, every ACM proceedings you've ever read was likely set in the tool he built as a side project.

Fascicle 7 is a draft chapter for the eventual Volume 4C. At the current pace, the complete Volume 4 may take another decade. Knuth is 88. He doesn't seem worried.

Long before HackerOne and corporate bug bounty programs, Donald Knuth was paying people to find errors in his work. The reward: $2.56, or one "hexadecimal dollar" (256 cents). The tradition dates back decades, and the checks — drawn on Knuth's personal bank account — became the most famous uncashed checks in computing history.

Nobody cashes them. They get framed. A Knuth reward check is the computer science equivalent of a signed first edition: proof that you found something the most meticulous author in the field missed, and that he thanked you for it personally.

In recent years, check fraud forced a change. Knuth now issues "certificates of deposit" from the Bank of San Serriffe — a fictional island nation invented by The Guardian for an April Fools' joke in 1977, whose name happens to be a typographic pun (sans-serif). It's the most Knuthian solution imaginable: confronted with a security problem, he invented a fictional bank at a fictional island with a name only typesetters would find funny.

In June 2025, Donald and Jill Knuth celebrated their 64th wedding anniversary — a number that is, naturally, a power of two. They live on the Stanford campus. He still doesn't use email. He plays the pipe organ. And somewhere in his study, the next fascicle is taking shape, one carefully considered paragraph at a time.