0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789
1.
My dad Ervin Knuth (kaNOOTH) was a teacher in Lutheran schools. My mom Louise managed buildings in downtown Milwaukee. I enjoyed music and grammar, also wrote corny jokes. Was poor at sports and art. Spent many hours drawing graphs. Learned to identify many trees by their leaves.
2.
At age 4 I was the youngest "bookworm" in Milwaukee's library. Once was lost in that library, having stayed in the stacks past closing time. Went to parochial school where my teachers taught us to love others. Many chances to sing and to play music, to enjoy nature. Knew no math.
3.
My 7th-grade teacher introduced us to diagramming sentences. My friends and I tried to apply it to non-textbook examples, with limited success; but we learned a lot in the process. The TV program was different: I won a contest to find as many words as possible from given letters.
4.
I probably first heard about UNIVAC on election night 1952, when I was 14 years old. I saw a real computer -- the IBM 650 -- first in 1956, as a college freshman at Case. We were allowed to touch that machine, sitting at the console and feeding cards to it. I was hooked for life.
5.
Freshman classes (physics, chemistry, calculus, civics, writing); sophomore (astronomy, basic math, diff geometry, physics2, history, speaking); junior (algebra, topology, electrical engineering, literature, numer anal); senior (automata, combinatorics, logic, complex variables).
6.
Marched in the band, copy-edited the newspaper, was fraternity vicepresident, fell in love, managed sports teams, wrote compilers and assemblers, entered math competitions, edited magazine and student handbook, watched plays and orchestra rehearsals, wrote a short musical comedy.
7.
R C Bose taught me combinatorics and inspired me to work with Hall. I planned at first to study designs with $\lambda=2$. But one day I happened to construct new kinds of non-Desarguesian projective planes, solving a conjecture, and Marshall told me that that should be my thesis.
8.
Yes, Hall was an early believer in the power of computing to help develop combinatorial theory. Consulting was my connection to the newfangled field of Computer Science. I taught computing at Caltech, even as a math prof. But I stopped consulting when becoming a Stanford CS prof.
9.
A representative of Addison-Wesley, the publisher of my favorite textbooks, met with me in January 1962 and invited me to write a new book about compiler-writing. That was exciting because existing publications were poor, one-sided, often contradictory. I'd always liked to write.
10.
During the summer of 1962, my friend Bill Lynch and I wrote a FORTRAN compiler for UNIVAC SS80 computers. One day I decided to explore why its "hash algorithm" worked well; and got lucky: I saw how to solve that problem, and realized that many similar yet-unsolved problems exist.
11.
As a consultant, I had easy access to excellent Burroughs machines near my home. Almost every university had primitive computing facilities at that time. Stanford was an exception: George Forsythe understood that computer science was a new field with deep intellectual challenges.
12.
My initial focus was on programming languages; I became editor of that section in CACM, then JACM. While writing my book I soon learned that compiler writers were also developing techniques of general interest, and that it was great fun to analyze those algorithms quantitatively.
13.
At the end of the 1960s, computer science was tripartite: Numerical analysis, programming languages, artificial intelligence. But none of those titles quite matched my interests. So I made up the name Analysis of Algorithms, whose first definition was: the part of CS I like best.
14.
Floyd and I had been friends since we met in 1962. We had thrilling correspondence re Bose-Nelson sorting networks. We wanted to be eventually at the same university. Everywhere but Stanford we'd have to help build a leading department; Forsythe had already done that beautifully.
15.
Stanford had great mathematicians, but almost all in analysis with a token algebraist. Cohen was brilliant, yet thought combinatorics trivial. Polya was a wonderful exception; my other math colleagues were Dantzig in OR, plus people like Berlekamp, Gale, Karp, Lehmer at Berkeley.
16.
Cohen was legendary also at Caltech. But I actually never heard about a Berkeley-Stanford math colloquium; at math talks I often asked myself "so what, so what?" I started a series of weekly combinatorial math seminars at my home, and people from Berkeley would often participate.
17.
A week before the Bucharest Congress I spoke at the IFIP Congress in Ljubljana about the beauties of theory. Thus I could straddle both sides of the fence. I'd seen both extremes when writing Volumes 1, 2, and 3 of The Art of Computer Programming. Everywhere we find yin and yang.
18.
I loved books and alphabets since childhood. I loved the look of Addison-Wesley's texts. I spent many years as copy editor, journal editor, and proofreader. Computer science needed new typographic tricks, which I helped to formulate. Many fine printing establishments were nearby.
19.
The letter S suggests a beautiful geometry problem of matching an ellipse to a tangent, solvable with classic primitives. Fitting curves to rasters, breaking paragraphs to lines, and many other appealing math challenges arise naturally, summarized in my 1985 lecture at Epidaurus.
20.
EWD316 also said that everyone should "find their own style". And I believe everyone should find their own beauty. But curiously, I don't recommend finding one's own truth! To me, truth is totally objective. And I'm glad there are mysteries, whose truth or falsity can't be known.
21.
I'm clearly at the discrete end of that continuum. (However, surreal numbers are much richer than the continuum itself.) Like Leibniz, I like to think of everything as made from 0s and 1s. We take limits when that's a useful approximation, and when we understand what limits mean.
22.
When I met him in Nice, I proudly mentioned that I'd discovered the surprising formula l(382)=l(191) in the theory of addition chains. Without blinking he immediately asked if there were infinitely many cases with l(2n)=l(n). (That result was proved by Thurber three years later.)
23.
A few hours before Bill's visit, I'd been thinking about the way random graphs evolve, at their big bang. From the transition probabilities, I realized that the denominator 17017 was the key to the whole pattern. I excitedly drew the picture on the blackboard; Bill was impressed.
24.
Yes, the ninth-century Kashmiri poets who created ingenious "chitrakavya" certainly rank among the pioneers of combinatorics. The study of Sanskrit prosody has also advanced other parts of mathematics. But only a few scholars remembered them, after other ideas became fashionable.
25.
I don't agree that the Indian approach has been entirely pragmatic, instead of curiosity-driven. I immediately felt strong kinship with NArAyana when I learned of his Ganita KaumudI (1356), since I'd played with exactly the same concepts in 1961! He must have felt lonely in 1356.
26.
Mathematics is the science of patterns. Languages are perhaps the most complex artifacts of civilization. Panini had the profound insight that Sanskrit had patterns that could be formalized and put into a logical system. He gave his commentators millenia of rich food for thought.
27.
My knowledge of Sanskrit is entirely third-hand, but I've been told it's this very ambiguity that has made things like chitrakavya possible and inspiring. On the other hand, modern NLP and ML methods seem to have made the complexity manageable, once enough data has been gathered.
28.
No, the largest positive number used in a published proof isn't an oxymoron (nor is it a constant)! My lecture on Coping With Finiteness cited Super-K = 10\uparrow\uparrow\uparrow\uparrow3, which is way bigger than Ron's number; I think it's too large to actually be comprehended.
29.
Indeed, I keep running into apparently new patterns that involve only very elementary ideas. For example, I spoke to Zeilberger's seminar in January about the fascinating Tchoukaillon array, which contains every positive integer exactly once; its properties are mostly unexplored.
30.
No; AI and ML are topics that others can write about far better than I. Of course there are many flavors of learning and many flavors of combinatorics. For example, TAOCP does discuss reinforcement in message-passing models of random satisfiability problems. But that's different.
31.
I'm still with Mumford's former self with respect to not believing that ML can find discrete things like orthogonal latin squares (loved by me and my mentor R C Bose). The big potential problem is that nobody is able to understand how deep neural networks reach their conclusions.
32.
No. I suspect that P=NP because a polytime algorithm might exist without being comprehensible (even more so than Super-K). Existence is far different from embodiment. Robertson and Seymour showed that polytime algorithms for some graph problems exist, yet are probably unknowable.
33.
Hmm. Why did Gelfand leave out "fun"? Also, the Japanese philosophy of Wabi-Sabi explicitly denies that Exactness is necessary, or sufficient. My musical and poetic friends aren't fans of exactness either; perfect rhythm is too dull. Passion and je-ne-sais-quoi are indispensable.
34.
Anybody who looks at the scores of Tchaikovsky, say, realizes that he was a great combinatorialist. There are strong historical ties (works of SArngadeva, Mersenne, and Schillinger explicitly, Bach implicitly). This week I'm enjoying the fantastic combinatorics of Burt Bacharach.
35.
I understand why my friends find fulfillment when they supervise others or affect the marketplace. But the profit motive has always been furthest from my thoughts, after I had a stable job. I envy astronomers, because people understand that astronomers are motivated by curiosity.
36.
Great question! Girolamo Cardano (1501-1576); John Wallis (1616-1703); Leonhard Euler (1707-1783); James Joseph Sylvester (1814-1897); Jack Edmonds (1934-); L\'aszl\'o Lov\'asz (1948-). And let me add Richard Stanley (1944-), a student in the first calculus class I taught (1963).
37.
I have no TV. I've been retired since 1993. I work in "batch mode", not "swap-in-swap-out". I write and rewrite TAOCP one word at a time. I swim almost every day. Take frequent naps. Play piano and organ. Go to Stanford Theatre. Have loving family. Have myriad helpers. Chocolate.
38.
(Also, the purpose of machine learning should be insight, not results!) It is wonderful that computers complement human capabilities, not only for verifying proofs but also symbolic calculations, etc. Of course computer programs can have mistakes; so can their proofs of validity.
39.
The "graffiti" in the margins of Concrete Mathematics, mostly contributed by Princeton and Stanford students when Ron and I first taught from preprints of the book, have clearly been successful: Any errors they contained were discovered by readers before all mistakes in the text.
40.
I've tried unsuccessfully to understand quantum computing. Maybe there are people who understand it but can't fathom the kind of computing that I do. All I know is that there seem be two completely different things, both called "computing". Everybody should follow their own star.