Point eight is enough: Donald Knuth on algorithms, TeX, and a life in one chair

Lex Fridman recorded the conversation in Knuth's office, a crowded room that was awkward for cameras and, for Knuth, the place where most of the work gets done. Getting there took ingenuity. Knuth does not check email. Fridman introduces him as a 1974 Turing Award winner, author of the multivolume *The Art of Computer Programming*, popularizer of asymptotic Big-O notation, and creator of the TeX typesetting system that scientists still use to make papers look beautiful.

The story Knuth wants to tell starts in 1957 at Case Tech. He was a freshman with a job in the statistics group, punching cards and sorting data on another machine, when the IBM 650 arrived. It did not fill a room, but it was big and noisy. He first saw it through a window, lights flashing. He had a key to the building, so he could get in, look at it, and take a manual home.

The 650 was large in physical size and tiny in power. It had two thousand words of memory; a word was ten decimal digits plus a sign. Adding two numbers took on the order of three milliseconds. That number was not magic. The drum took five milliseconds to go around. An instruction sitting at one position had to wait for the data, then wait again for the next instruction if that instruction was not sitting at the expected notch. Until senior year there was no random-access memory at all. Then they got fifty words of it, which felt priceless. They would move work up in sixty-word chunks, run a subroutine, and start again.

Could he have predicted computing sixty years on? An interviewer once asked what had surprised him; he rattled off a couple of dozen things. She flipped the question: what had *not* surprised him? He thought for five minutes and could not name one. The 650, he notes, was the first machine produced in quantity, more than a thousand of them. IBM rented them to universities on a generous deal, which is how a generation of students met computers.

Knuth calls people who gravitate toward computational thinking geeks, including himself. Something in how he grew up, he thinks, structured his brain so that it resonates with computers. He has long estimated the share at about 2 percent of the population, a figure that held fairly steady over most of his career, though it might be shifting now that children grow up with different machines. In the 1950s IBM noticed the type and advertised for it: if you play chess, come to Madison Avenue for an interview.

What does a geek find easy that other people find hard? First, the ability to jump levels of abstraction: to see a problem in the large and in the small, and to pass between those views without thinking about it. You know that solving a big problem means adding one to a certain register. You do not go down to the electron, but you know what those milliseconds on the 650 drum felt like, and you know how that maps onto factoring a number or finding a root. Debugging walks the same staircase: a keypunch error, a wrong instruction, the wrong thing in a register. Each level is different, and you can enter all of them.

That is why his books mix low-level detail with high-level argument. Some readers say he should write better books; others say that if your mind already works this way, mixing the levels is how you train it. The second talent is comfort with non-uniformity: case one, case two, case three, rather than one or two rules that govern everything. An algorithm with ten steps, each doing something else, does not bother him. A lot of pure mathematics wants a universal rule. People like him, he admits, sometimes build systems more complicated than necessary, because not finding the simple rule does not feel like a crisis.

Nineteenth-century mathematicians — Jacobi, Bolzano, Abel — may have had symptoms of geek, he says. The first 100 percent legit geek was Alan Turing. As an undergraduate Knuth knew only computability theory and Turing machines, which sounded like purely formal work. Years later he learned that Turing had designed machines, written a wonderful manual for the Manchester machine, invented subroutines, and been a real hacker with dirty hands. Turing even wrote numbers backwards, left to right, π as 9 5 0 1 4 point 3, because that was how the computers he used processed them. He had trained himself to think like the machine.

Fridman notes the apparent contradiction: Knuth practices some of the most elegant formalism in computer science, and he also created literate programming, which moves description closer to natural language. Knuth does not see a fight. He does not think one size fits all, and he does not think all truth lives in one kind of expertise. His life, he says, is a convex combination of English and mathematics. He is not merely okay with that. He wants his children that way: left brain and right brain at the same time.

He did not read literature for pleasure until his thirties. The books that lasted are the ones with a worked-out way of life inside them. Tolstoy's *Anna Karenina* mattered less for plot than for the philosophical discussions among characters. Dostoevsky he disliked: sloppy, always forgetting what he had started, never polishing. Knuth admires people who dot the i's and cross the t's, and he loves the music of language even in translation. Raymond Chandler's sentences flow; Dashiell Hammett's do not. Ian Fleming can make a golf game or a hand of bridge the most exciting one possible and tell it beautifully. He met Philip Roth when they received honorary degrees from Harvard on the same day. Roth, Knuth recalls, knew computer books would never sell.

Literate programming, he says, is a way to understand a complicated thing by looking at it from at least two perspectives, formal and informal. A good technical writer, without being obvious about it, says everything twice, maybe three times, so the reader can put the concept into their own brain. The writer's job is a mental image of the reader: say what the reader expects next, and try to make interesting what was interesting to you. A program is not only instructions to a computer. It is insight for the person who will maintain it, and for the programmer who is debugging it, about *why* this is being done. The exposition tricks a teacher uses make you a better programmer, if the program is not a one-shot throwaway.

He is the wrong person to ask how hard the mix is, because he is a geek, and for a geek it is easy. He will not claim anyone can be taught any particular skill. Writing is half his life; he puts it together with programming. Even a one-shot program he writes in a literate way, because he gets it right faster. The example he reaches for is a self-referential Japanese arrow puzzle: boxes pointing north, east, south, west, each to be filled with the count of distinct numbers it points to. A correspondent had sent a pile of formal disjunctions. Knuth rendered them as informal dialogue — I contain a three, and the boxes I point to contain one, two, and six — until the string of abstract variables locked in.

Fridman pivots to neural networks: using data to construct algorithms rather than writing them in language. Knuth thinks that style of work suits a certain kind of non-uniform mind, which is probably why the community took off. It is also hard to trust, because even the people who train the systems have no idea what has been learned. That, Fridman notes, may make algorithms accessible to a different kind of brain, the way literate programming might. Knuth is unconvinced that anyone can be taught to be a great programmer, or a great skier. He has been well motivated at things he never got past a certain level. He cannot visualize three-dimensional objects in his head; he has to make a model and look at it from every angle. Physicists, he says, are good at four dimensions.

In 1962 he set the table of contents for what became *The Art of Computer Programming*. It was supposed to be a single book with twelve chapters. Fifty-seven years later he is in the middle of volume 4 of seven, specifically 4B. Asked for an elevator summary, he says it depends how many floors the building has. Volume 1, *Fundamental Algorithms*, is the stuff you cannot do without: what a program is, what an algorithm is, a low-level machine so you can picture what is going on, input, output, subroutines, induction, mathematical preliminaries. What makes the book different is that he does not only present an algorithm. He analyzes it quantitatively. Not only does it work; it works this fast. That is why he needs the math.

Volume 2, *Seminumerical Algorithms*, is programs that deal with numbers: arithmetic, matrices, random numbers, power series, the way a computer thinks about floating-point and high-precision arithmetic. Volume 3, *Sorting and Searching*, is the one he likes to introduce with a grin. You sort letters as well as numbers, and searching is what we do all the time now when we Google. None of the volumes is about a particular application; the applications are why people want to know about sorting or random numbers.

Volume 4 is combinatorial algorithms, the domain of zillions. Here one good idea can make something go more than a million times faster. The problems are probably never going to be solved efficiently, but that does not mean you give up. These are the algorithms Knuth has always enjoyed most, because that is where programming skill has the most payoff: the gap between the obvious first method and the subtle one that runs circles around it. A lot of the methods first showed up in artificial intelligence or cryptography; in his case they were associated more with puzzles. Graphs are great because they model so much of the real world, and numbers on a graph make a network.

The 1962 outline was not even a book about computer programming in general. A publisher asked him to explain how to write a compiler. Only a few dozen people in the world had done that, and he happened to be one of them. He had also written for the campus newspaper. He figured he was the only person he knew who had written a compiler without inventing a new technique, so he could be the journalist who described everybody else's cool ideas, not just his own.

The table of contents grew. You needed a chapter on data structures. You needed searching, because a compiler writer has to look up variables in a symbol table and decide when two names are the same. He threw in arithmetic, and a chapter on combinatorics because that was what he most enjoyed programming, even though in 1962 there were not many combinatorial algorithms to write about. Chapter 12 was going to be compilers, applying chapters one through eleven. During the 1970s the whole field of combinatorics went through a huge explosion — not only of case counts, but of ideas. By 1975, he bets, more than half of the computer-science journals were about combinatorial methods.

Graph theory was dominant, along with the NP-hard problems everyone still recites: Hamiltonian path, traveling salesman. Operations research had a small class of problems with efficient solutions, usually tied to matroid theory. Once you went from looking at things two at a time to three at a time, everything got harder. Satisfiability with two literals per clause can be tested in linear time. Allow three variables in a clause, and nobody knows how. The papers of that era were hunting better ways into cryptography and graph problems where you have lots of data and no idea how to find the best subset.

Today there may be half a dozen conferences whose topic is combinatorics. He does not have to rewrite the book every month the way one did in the 1970s, but there is still a huge amount of work, and people keep getting better ideas on problems that still lack truly efficient solutions. The volume he is finishing now contains brand-new methods that, as far as he knows, no other book covers. He is trying to explore the tip of the iceberg, try lots of things, and keep rewriting as he finds better ones.

The chair Fridman is looking at is where the magic happens. It was designed by a Swedish maker, and it is the only chair Knuth can sit in for hours without knowing he is in a chair. Next to it is a stand-up desk. The kernel of an idea goes down first with pencil and eraser. Then he gets up, types, revises, rewrites. He writes maybe five literate programs a week. Before he describes something in the book, he always programs it to see how it works.

At the end of January he learned of a breakthrough by four Japanese researchers who had extended one of his methods. He spent five days implementing what they did, then generalized the parts they had not, then ran their approach on a couple of dozen problems he had already solved with the old methods. That took another couple of weeks. Friends solved some of the new mathematical questions; those became exercises. A month later he had absorbed one idea. The book was supposed to come in at 300 pages and was up to 350; that episode added ten. He does not want to learn about another one just yet.

Some days he asks why he has to have such high standards, why he could not be sloppy and just report the answer. He grit his teeth, does the work, and the joy arrives when the results are good, and even more when somebody has actually read and understood the page and told him how to make it better. He still has the tablet of large, tightly lined paper he bought about forty years ago visiting his sister in Canada. He has manuscripts going back to the 1960s. He went to typing school in high school, so he types faster than he thinks; style and rhythm appear at typing speed, and the screen version comes out different from the page. He types in TeX. He does not think in macros, though he will write one when he needs it. He will rewrite a sentence to save a line, like haiku, because it looks better on the page. He knows that is maybe 3 percent of the time and he should not waste it. He cannot resist.

He works in the garden one day a week. That, he says, is a description of his life: getting rid of weeds, removing bugs from programs. The fun is putting together ideas of two people who did not know about each other. He may be the first person who saw both, and then he gets to make the synthesis, which is a chance to be creative. The drudge is chasing everything to its root, which leads him into Sanskrit, thank-you letters to authors or to people who knew the dead ones, getting the math right, and rewriting programs after readers try to find holes. Dead ends happen. He spent a long time on a major baseball example, complete with a planned foldout, then asked what a reader raised on cricket or soccer would think, and what algorithm he was actually teaching. He ripped the whole thing out. He took out bowling too.

Why is *art* in the title? He gave his Turing lecture on that word. Art, at root, means something that is not in nature — the same root as *artificial* in artificial intelligence, something created by human beings. Later the word picked up fine art, beauty, elegance, joy. Tolstoy versus Dostoevsky, again. Art is what human beings are specifically good at. When people say artificial intelligence they are trying to mimic humans, but there is an element of fine art in the word, and that is what he has been trying to say: you can write a program and make a work of art.

Asked for an idea that changed how he saw a space of problems, he jokes that he gets a surprise every time he has a bug. The transformational example is binary decision diagrams, BDDs. He had been programming since the 1950s and thought Boolean functions were cut and dried. Logic underlies everything we can describe. Then Randy Bryant, in 1986, found a way to represent a Boolean function that revolutionized the field. By the early 1990s it had billion-dollar applications and was the standard way to design computers, until SAT solvers arrived around 2000.

That discovery forced a whole new section of the book he would never have planned. The middle third of volume 4B, more than 300 pages, is about that territory, mostly material discovered in this century. He started from scratch, met the people in the field, and wrote fifteen different programs while preparing it; seven are described in the book, the other eight for his own understanding. Theoreticians then catalogued everything you could *not* do with BDDs, and the structure got a bad name for failing to solve every problem. He expects theoreticians, in the next ten years, to show why machine learning does not solve everything either. He is not only worried about the worst case. He gets huge delight from solving a problem he could not solve before, even if it suggests a further problem. He knows he is way better than he was.

He popularized asymptotic notation because he needed a way to write down something he did not know exactly, only partially. Imagine being allowed, in high school, to put "0 or 1 or 2" in the middle of a formula and then learn how to multiply such expressions. Big-O is the same move: here is something not bigger than some constant times n squared. You learn to add Big-O of n squared to Big-O of n cubed, to put Big-O inside a logarithm. That turned out to be hugely valuable. In practice, the worst case of a combinatorial algorithm is almost always horrible. SAT solvers are nonetheless solving instances; one of the last exercises in that part of the book is to find a problem with 100 variables that is still difficult, even though 2^100 possibilities sounds untouchable.

Knuth has said in recent years that he believes P may equal NP, but that a proof would not directly give you an algorithm for the hard problems. The popular idea is that if an algorithm exists, somebody will find it. He thinks many more algorithms exist than anybody can understand or ever discover. The total number is more than mind-boggling. We already have situations where we know an algorithm exists and have not the foggiest idea what it is.

Hex is the clean example. Players take turns putting pebbles on a hexagonal board. White tries for a path left to right, black for a path bottom to top. There is no capture and no draw: when the board is full, one of those paths exists. The game is finite, so it is a first-player win or a second-player win. A pairing strategy shows it cannot be a second-player win, so first player wins. Nobody knows the winning algorithm, or even where the first stone should go.

A deeper example is the Robertson–Seymour theorem in graph theory. Any class of graphs closed under taking minors — shrink an edge to a point, or delete an edge — has a polynomial-time algorithm to test membership. The proof says there is a finite list of minimal forbidden minors. For planar graphs the two bad graphs are K5 and the utilities graph. Test a candidate against each forbidden minor; each test is polynomial, a finite number of them is still polynomial. The catch is that you only know the list is finite. You might know one or two of the bad graphs and not know whether there are 21 or 25. So you have a polynomial-time algorithm whose actual form you do not know.

That is why a P = NP proof might not help. You would have to rule out a vast space of bizarre algorithms: encode the graph as primes, multiply, take bitwise AND, stumble into a coincidence. Hair-counting is the analogy. A country has fewer people than hairs on a head, so two people must have the same number of hairs. No mystery, just the pigeonhole principle. Combinatorics is full of such collisions. People say P cannot equal NP because so many smart people, and a million-dollar prize, have failed to find the algorithm. He can turn the sentence around: so many smart people have failed to prove P ≠ NP. The same logic cannot support both conclusions, which means it supports neither. He does not spend time on questions he could never know, including whether there is intelligent life in the universe, though he is glad some questions have no answer. Proof that God exists or not would spoil the mystery. The world would be too dull.

From the 1960s on, Knuth says, the AI community has been computer science's greatest source of inspiration, maybe more than any other group. People trying to mimic intelligence, or to match its greatest achievements, pushed the envelope and generated a stream of good problems, partial answers, and increasingly successful ones. A lot of the field's great discoveries started there. He himself is not as captivated as most people in that community by the possibility of creating echoes of intelligence. That is preference, not a verdict that they are wrong.

What worries him is when people start believing they have actually succeeded. There is a huge gap between really understanding something and being able to pretend to understand, to give the illusion of understanding. Can you create without understanding? He does that all the time; he likes random numbers. The gap is still there. He will not say true intelligence is impossible. He does not see anything coming close to the kind of stuff he would consider intelligence.

The Art of Computer Programming is mostly single-processor algorithms because the table of contents was set in 1962. He is glad he did not wait until 1965; one book cannot cover everything. He has said that understanding how ant colonies perform incredibly organized tasks might be a key to human cognition. The advantage of ants is that we can see which ant talks to which ant. Brains are harder: we do not know to what extent neurons are passing signals. He tends to think of an ant colony as a single cognitive being, the way he thinks of himself as one person even though his brain cells and microbiome are interacting entities. If we are going to crack cognition, faking out how ants do it — pheromones, touching, sight — might be more measurable than electrical currents in a skull.

Conway's Game of Life can simulate any computable process, but that is not its most powerful feature. The magic is that the units are distributed and extremely simple. We understand exactly what the primitives are, even simpler than an ant colony. That still does not mean he understands life. It gives insight into what a deterministic universe means, and what free choice means for us. Does God play dice? Yes. He sees no reason God should be forbidden from using the most efficient methods, and we know randomness is essential to many algorithms. Some things cannot be done well without it. Physics, in his view, should not constrain that.

In 1999 Knuth gave a series of MIT lectures on religion and science, later published as a book. Facing a subject beyond human understanding, he argues, you should not give up, and you should not only study the parts someone assigns. Use randomness. Pick a subset within your grasp and study it in detail. He chose something like 60 verses out of about 3,000, one in 500. Then he went to libraries whose indexes were good enough to use. Once a week for a year he sat in the Boston Public Library; he also went to Harvard. He could look up whether a given verse was mentioned on page 205 of a scholarly book, and so learn not only the Bible but the secondary literature around it.

The method gave him firm pegs on which to hang pieces of information. He would not say "and therefore this is true." The main thrust, as he read it, was not the commandments people usually cite. It was how to live in harmony with God's wishes, assuming God exists. He is glad there is no proof. He would run through the proof once, remember it, and stop speculating about spiritual things and mysteries, and his life would be incomplete. Even for people who say God does not exist, the question is still important to them. One verse he studied can be read as saying it is much better to be an atheist than not to care at all.

Fridman asks how Knuth, if he were God, would present himself to the people of Earth. Knuth points to a novel he thinks is called *Blasphemy*, in which God reveals himself through a computer at Los Alamos. It is the only book he has ever read whose punch line is the very last word and explains the whole idea. He will not spoil it. If God decided that previous means of communication were not the best for the 21st century, it is conceivable God would choose the way that book describes. The larger lesson of the thought experiment is humility. Solving one problem does not make the others drop out. There are things beyond our ability. Fridman says he sees hubris all around. Knuth agrees.

Fridman asks him to run program analysis on his own life: correctness, running time, asymptotic resource use. Nobody had asked that before. Knuth says he started with libraries and subroutines, learning to be an obedient automaton. He had a great advantage: nobody to blame for his failures. If he was not understanding something, he knew he should stop playing ping pong; it was his fault for not studying hard enough, not discrimination. He does not know how to erase bias in the world, but he knows that extra burden is one he did not have to suffer.

From his parents he learned altruism, service to other people as more important. Then he realized he had to be happy enough himself in order to be of service. The philosophy he finally phrased is "point eight is enough," riffing on a TV show called *Eight Is Enough*. If he had a way of rating happiness, a well-designed organism would be happy about 80 percent of the time. At 100 percent it would be as if everybody were on drugs. Everything would collapse. Nothing would work, because everybody would be too happy.

Has he achieved 0.8? There are times he is down. He knows he has been programmed to be depressed a certain amount of the time. If that gets out of kilter he catches himself asking who he should be mad at today, then realizes it is chemistry telling him to be mad at somebody. He sets it aside, goes to sleep, and it gets better. Not being 100 percent happy does not mean he should find someone on the street and scream at them. He can accept being happy enough to be part of a sustainable situation. That is the numerical analysis: a human life converges toward 0.8.

In 2006 he was diagnosed with prostate cancer. The first real encounter with mortality, though, was his father's death. He spent a month becoming comfortable with the fact that he would die someday. During that month he felt all right, but he could not sing, and he could not do original research. After three or four weeks he had a technical thought that made sense and was slightly creative, and he could feel something starting to move again. Before that he felt empty. He later learned this was a standard grief process. By the time of the interview, all of his goals were fulfilled except finishing *The Art of Computer Programming*. He had wanted all his life to write a piece of music of a certain kind, at least as a proof of concept. He finished it. The world premiere was on his 80th birthday; there was another in Canada, talk of Europe. It is part of the world's music now, good or bad. He did what he hoped. When the cancer diagnosis came he thought: I have had good luck all my life, nothing to complain about, maybe this is the end. He made no plans. After surgery, learning to walk again, pain, he got home and realized he had not thought about what to do next. Then: oh, I am still alive, I can write some more books. He had already gotten more than his share.

In the 1970s Knuth created the TeX typesetting system, the METAFONT language for describing shapes, and the Computer Modern family of typefaces. They have defined how math, physics, computer science, and far more of research looks on the page. Beauty is hard to quantify. George David Birkhoff wrote *Aesthetic Measure* in the 1930s, printing pictures of vases with a number underneath for how beautiful each was, and he wrote about music too. Knuth once thought of programming Birkhoff's algorithms so a composition would score at the top. It was not rigorous enough for a computer. It was, he thinks, the most serious attempt to put a numerical value on beauty. His own loose definition for letters was simpler: he wanted them to appeal to him, personally.

That test failed on what he expected to be the happiest day of his life, when volume 2 came out in a new printing. Same covers, same pages, and it did not look great. The number 2 was particularly ugly. He could not stand it. Any painter would have drawn a page-number 2 properly. He had made measurements, looked at the letters in different ways, had great technology, and he was not done. He had to rewrite the whole thing after 1961. Did it finally make him happy? Yes. So many books have been written that would never have existed without the system. Sitting in his office, looking at the pages above him, if he does not like them he can change them. Nobody else has that ability. They have to stick with what he gave them.

On spacing and white space, you can always go further. He did not stop at 0.8. He started at about 0.98. That looks like a violation of his happiness rule. He says no. There is a Japanese aesthetic, wabi-sabi, in which the most beautiful works have flaws, because the viewer adds their own appreciation. Typography, for him, is the opposite: he wanted it to look as good as he could in the vast majority of cases. When it does not, that is 2 percent more work for the author. He did not want his job to be 100 percent, taking all the work away from the author. That is what he meant by 0.8 is enough — for the things you should not try to finish for other people.

How much of the nature of reality do humans understand? Infinitesimal: point, then some number of zeros. We muddle through, keep advancing, and do not spend the day announcing we are not at the end. Mathematicians in the office next to him never thought about anything smaller than countable infinity; he almost never got up that far, because he works with finite things. Even limiting to the finite, the universe might be a finite number of quarks, and all the numbers humans can comprehend are still way smaller than almost all finite numbers. In a paper called "Supernatural Numbers" he used Conway's chained-arrow notation: no arrows is multiplication, one is exponentiation, then tetration and beyond. Ten with four arrows and a three is already beyond imagination, and still pathetic next to a typical finite number, because you could set the number of arrows itself to that huge value. The boundary between finite and infinite is incomprehensible. Infinity is a useful tool for thinking about the extremely large. We can never know the universe is anywhere near it. We know how little we know, and even in this small universe we have found more than any one person can hold. "We did pretty good." If he got to heaven and could ask God one question: what kind of browser do you have up here? He does not think it is a meaningful question. He hopes the internet is good.