Donald Knuth

• 1. Introduction

  ›

  Donald Knuth, an American computer scientist born in 1938, pays $2.56 to anyone who finds a mistake in one of his books. The number is deliberate. As he explains it, 256 pennies make one hexadecimal dollar. A smaller reward of $0.32 goes to people who offer valuable suggestions.

  According to an article in the Technology Review of the Massachusetts Institute of Technology, these reward checks are among computerdom's most prized trophies. In 2008 bank fraud forced him to stop sending real ones. Now each person who finds an error receives a certificate from his fictitious Bank of San Serriffe.

  The author of that joke is a professor emeritus at Stanford University, and his books are exacting enough that catching a flaw in them is a badge of honor. How did a boy from Milwaukee come to write a multi-volume work on programming? Why did he build a typesetting system of his own? And what made a mathematician insist that programs should be read the way people read literature?

  575582

• 2. A Puzzle Solver's Start

  ›

  Donald Knuth was born in Milwaukee, Wisconsin, to Ervin Henry Knuth and Louise Marie Bohning. His father owned a small printing business and taught bookkeeping. Knuth describes his own heritage as Midwestern Lutheran German.

  In eighth grade, at Milwaukee Lutheran High School, a contest challenged students to rearrange the letters of Ziegler's Giant Bar into as many words as possible. The judges had found 2,500. A fake stomachache bought Knuth time away from school, and he spent it going through an unabridged dictionary, testing every entry against those letters. He found over 4,500 words and won. His school received a new television and enough candy bars for every schoolmate.

  In 1956 he enrolled at the Case Institute of Technology in Cleveland, Ohio, on a physics scholarship. He also joined the Beta Nu Chapter of the Theta Chi fraternity. At Case he met the IBM 650, an early commercial computer. After reading its manual, he decided to rewrite the assembly and compiler code on his school's machine, because he believed he could do it better.

  In 1958 he wrote a program to help the school's basketball team win. He assigned values to players to gauge how likely each was to score. Newsweek and CBS Evening News later reported on the novel approach.

  Knuth was also a founding editor of the Case Institute's Engineering and Science Review, which won a national award as best technical magazine in 1959. He then switched from physics to mathematics. In 1960 he received a bachelor's degree and, simultaneously, a master's by special award, because the faculty considered his work exceptionally outstanding.

  At the end of that senior year, he sent a proposal to Burroughs Corporation, and the price on it was $5,500.

  510111258

• 3. Compilers and Consulting

  ›

  Burroughs accepted the proposal to write an ALGOL compiler for its B205 machine. Knuth did the work in the gap between leaving Case and starting at Caltech.

  In 1963, with the mathematician Marshall Hall as his adviser, he earned a PhD in mathematics from the California Institute of Technology. His thesis was titled Finite Semifields and Projective Planes. The same year he joined the Caltech faculty as an assistant professor.

  The success of the B205 compiler made him a consultant in the Product Planning Department at Burroughs. He lived a double life. At Caltech he worked as a mathematician, and at Burroughs as a programmer. There he worked alongside the people he considered the best software writers of the time, who had built the ALGOL compiler for the B220, the successor to the B205.

  Money tempted him and he refused it. Green Tree Corporation offered a $100,000 contract to write compilers, and he declined, choosing instead to stay at Caltech and Burroughs. A National Science Foundation Fellowship and a Woodrow Wilson Foundation Fellowship also came his way. Both required that he do nothing but study, which would have ended his consulting, so he turned them down too.

  He did take one job he regretted. In the summer of 1962 he wrote a FORTRAN compiler for Univac, and he later felt that he had "sold my soul to the devil" by doing so.

  When Knuth returned to Burroughs in June 1961, he did not mention that his degree was a master's rather than the expected bachelor's. He admired the ALGOL compiler's syntax chart, its symbol table, its recursive-descent approach, and its separate scanning, parsing, and emitting stages. He suggested extending the symbol table so that one symbol could stand for a string of symbols. That idea became the DEFINE feature of Burroughs ALGOL, which other languages have since adopted. Some colleagues disliked it and wanted it removed. The last person to call it a terrible idea was Edsger Dijkstra, during a visit to Burroughs.

  Knuth also worked on simulation languages there. With J. McNeeley he produced SOL, short for Simulation Oriented Language, an improvement on the state of the art. In May 1967 he attended a conference in Norway organized by the inventors of the Simula language, and he went on to influence Burroughs to use Simula.

  His consulting for the company ran from 1960 to 1968.

  513141547

• 4. The Book That Kept Growing

  ›

  In 1962, the publisher Addison-Wesley commissioned Knuth to write a book about compilers for programming languages. As he worked, he decided he could not treat the topic properly without first building a fundamental theory of computer programming. That theory became The Art of Computer Programming.

  He first planned a single book. His outline then demanded six volumes, and later seven. The first volume appeared in 1968.

  His motive, he said, grew from the state of the field in the 1970s. He called computer science "a totally new field with no real identity. And the standard of available publications was not that high. A lot of the papers coming out were quite simply wrong.... So one of my motivations was to put straight a story that had been very badly told."

  Just before the first volume came out, Knuth left Caltech for the Institute for Defense Analyses. Its Communications Research Division, then on the Princeton campus, did mathematical research in cryptography to support the National Security Agency.

  At a Society for Industrial and Applied Mathematics conference in 1967, someone asked what he did. At that time, computer science was divided into numerical analysis, artificial intelligence, and programming languages. Knuth decided that next time he would answer "Analysis of algorithms." He is now called the father of that discipline. He helped make the computational complexity of algorithms rigorous, and he popularized asymptotic notation along the way. He also proposed the name algorithmics for computer science as a whole.

  In 1969 he left Princeton for the Stanford University faculty, and in 1977 he became the Fletcher Jones Professor of Computer Science. The study of the stable matching problem also owes him a substantial contribution.

  The years 1972 to 1973 took him to the University of Oslo, among people such as Ole-Johan Dahl. He had meant to write the seventh volume there, on programming languages. But only two volumes were finished, so he spent the year on the third, which came out just after his return to Stanford in 1973.

  In 1992 he retired from regular research and teaching at Stanford, so that he could finish the work. Volume 4A was published by 2011. In April 2020 he said he expected Volume 4 to have at least parts A through F, and Volume 4B arrived in October 2022.

  516192021

• 5. Typesetting and Literate Programs

  ›

  In the 1970s the publishers of The Art of Computer Programming dropped the Monotype process in favor of phototypesetting. Knuth thought the new system fell far short of the quality of the earlier volumes, which had been set with the older method. His frustration was so great that he took time out to work on digital typesetting. The result was TeX, along with METAFONT, a font definition language and rendering system, and the Computer Modern family of typefaces.

  While building TeX, Knuth devised a new way of programming that he called literate programming, because he believed programs should be thought of as works of literature. His own statement of the idea reads: "Instead of imagining that our main task is to instruct a computer what to do, let us concentrate rather on explaining to human beings what we want a computer to do."

  He embodied this in the WEB system. A single WEB source is woven into a TeX file and tangled into a Pascal source file. The first yields a readable description of the program, and the second yields an executable binary. A later version, CWEB, swaps Pascal for C, C++, and Java.

  Knuth wrote TeX and METAFONT in WEB and published both programs as books in 1986, titled TeX: The Program and METAFONT: The Program. Around the same time, Leslie Lamport developed LaTeX, the macro package based on TeX that is now widely adopted. Lamport published its first user manual in 1986.

  4543444654

• 6. Math Hard and Playful

  ›

  Knuth introduced a new course at Stanford in 1970. While writing Volume 1, he had found mathematical tools that he needed and lacked, so he decided to teach them to computer science students. Course notes developed by Oren Patashnik grew into the 1988 text Concrete Mathematics, by Ronald Graham, Knuth, and Patashnik. A second edition followed in 1994.

  Its preface recalls the first class. Knuth, referred to there as DEK, explained the odd title as an attempt to teach math that was hard instead of soft. He announced that, contrary to his colleagues' expectations, he would not teach the Theory of Aggregates, Stone's Embedding Theorem, or even the Stone-Čech compactification. Several students from the civil engineering department got up and quietly left the room.

  His book Surreal Numbers is a mathematical novelette about John Horton Conway's construction of an alternate system of numbers. Rather than simply explaining the subject, it shows the mathematics being developed. Knuth wanted it to prepare students for original, creative research.

  He wrote the foreword to the 1995 book A=B, by Marko Petkovšek, Herbert Wilf, and Doron Zeilberger. He contributes language puzzles to Word Ways: The Journal of Recreational Linguistics. Since the 1960s he has written for the Journal of Recreational Mathematics, and Joseph Madachy's Mathematics on Vacation acknowledged him as a major contributor.

  His sense of humor goes back to 1957. In a school magazine he published his first "scientific" article, The Potrzebie System of Weights and Measures. It defined the fundamental unit of length as the thickness of Mad No. 26 and named the unit of force "whatmeworry". Mad itself published the piece in issue No. 33, in June 1957.

  In the index of Volume 1 of The Art of Computer Programming, the entries "Circular definition" and "Definition, circular" refer to each other, a demonstration of recursion. He once warned a correspondent, "Beware of bugs in the above code; I have only proved it correct, not tried it."

  At the TUG 2010 Conference, he announced a satirical XML-based successor to TeX called iTeX, to be spoken while ringing a bell. It would support arbitrarily scaled irrational units, 3D printing, input from seismographs and heart monitors, animation, and stereophonic sound.

  9258606229

• 7. Faith, Music, Convictions

  ›

  On the 24th of June 1961, while a graduate student at Caltech, Knuth married Nancy Jill Carter. They have two children, John Martin Knuth and Jennifer Sierra Knuth.

  Knuth is an organist and composer. He and his father both served as organists for Lutheran congregations, and he and his wife keep a 16-rank organ in their home. In 2016 he completed Fantasia Apocalyptica, which he calls a translation of the Greek text of the Revelation of Saint John the Divine into music. It premiered in Sweden on the 10th of January 2018.

  His Lutheran faith also produced a book. In 3:16 Bible Texts Illuminated, he examines the Bible by systematic sampling, studying chapter 3, verse 16 of each book. Each verse is paired with calligraphic art by a group of calligraphers led by Hermann Zapf. MIT invited him to lecture on the views on religion and computer science behind the project. Those talks became God and Computer Science, published in his book Things a Computer Scientist Rarely Talks About.

  In 1977, shortly before a three-week trip to China, Frances Yao gave him the Chinese name Gao Dena. He embraced it in the 1980 Chinese translation of Volume 1 so that China's growing numbers of programmers would know him. In 1989 the name was placed atop the header of the Journal of Computer Science and Technology. He says this "makes me feel close to all Chinese people although I cannot speak your language".

  His convictions reach into law as well. Knuth strongly opposes software patents on trivial solutions that should be obvious, though he holds more nuanced views on nontrivial ones such as the interior-point method of linear programming. He has stated his disagreement directly to the United States Patent and Trademark Office and the European Patent Organisation.

  A few times a year he gives informal Stanford lectures that he calls Computer Musings. He was also a visiting professor at the Oxford University Department of Computer Science until 2017, and an Honorary Fellow of Magdalen College.

  3738525340

• 8. A Shelf of Honors

  ›

  In 1971, Knuth received the first ACM Grace Murray Hopper Award. Three years later came the 1974 Turing Award, informally considered the Nobel Prize of computer science.

  The National Academy of Sciences elected him in 1975, and the Mathematical Association of America's Lester R. Ford Award came to him in 1975 and again in 1993. In 1978 he was the Josiah Willard Gibbs Lecturer, and in 1979 he received the National Medal of Science. The British Computer Society made him a Distinguished Fellow in 1980.

  The National Academy of Engineering elected him in 1981 for organizing vast subject areas of computer science so that they are accessible to all segments of the computing community. The American Academy of Achievement gave him its Golden Plate Award in 1985, and the Franklin Medal followed in 1988.

  In 1990 Stanford created a one-of-a-kind title for him, Professor of The Art of Computer Programming. It has since become Professor Emeritus of The Art of Computer Programming. In 1992 he became an associate of the French Academy of Sciences.

  In 1995 he won the John von Neumann Medal and the Harvey Prize from the Technion. The Kyoto Prize came in 1996, the year Masaryk University in Brno awarded him an honorary doctorate in mathematical sciences. In 1998 the Computer History Museum named him a Fellow for his early work on the history of computing algorithms, the TeX typesetting language, and his contributions to mathematics and computer science.

  He became a Foreign Member of the Royal Society in 2003 and a member of the Norwegian Academy of Science and Letters. The Society for Industrial and Applied Mathematics named him to its first class of Fellows in 2009. In 2010 he received the Katayanagi Prize and the BBVA Foundation Frontiers of Knowledge Award in Information and Communication Technologies.

  The year 2011 brought the Turing Lecture and the Stanford University School of Engineering Hero Award. In 2012 he became a fellow of the American Mathematical Society and a member of the American Philosophical Society. The Flajolet Lecture Prize followed in 2014.

  Since May 2001, an asteroid, 21656 Knuth, has carried his name.

  6364747793