Ana səhifə

Donald E. Knuth a biographical Sketch

Yüklə 106.32 Kb.
ölçüsü106.32 Kb.
Donald E. Knuth

A Biographical Sketch

Beware of bugs in the above code; I have only proved it correct, not tried it.

- Donald E. Knuth written on March 22, 1977

Prepared by:

Josh Elson

University of Colorado at Denver

History of Mathematics

March 13, 2005

Table of Contents

1. Introduction 1

2. Donald Knuth’s Background 1

2.1 Knuth’s Parents 2

2.2 Knuth’s Childhood and Early Education 2

2.3 Case Institute and a Move to Mathematics 3

2.4 Knuth at Caltech 4

2.5 Professor Knuth 5

2.6 Retirement –> Increased Workload? 6

2.7 Awards and Recognition 6

3. Knuth’s Contributions 7

3.1 Groups, Semigroups, and Field Theory 8

3.2 Semantics, Formal Grammars, and Programming Languages 8

3.3 Mathematical Notation 9

3.4 Literate Programming 10

4. Idiosyncrasies and Quirks 11

4.1 The Finder’s Fee – Knuth’s Reward Checks 11

4.2 Definitely not a Technophile 12

4.3 3:16 12

4.4 Mathematical Humor and Easter Eggs 13

5. Errors and Misstatements 13

5.1 Big-O Notation 14

5.2 Knuth’s Series and Number 14

5.3 Literate Programming – the real reason? 15

5.4 NPR and the Hexadecimal Dollar 15

6. Conclusion 15

7. Knuth’s Collected Works 17


The Art of Computer Programming (TAOCP) 18


The TeXbook 18


The METAFONTbook 18


Computers & Typesetting 18


Concrete Mathematics 18


The Stanford GraphBase 18


MMIXware 18


The CWEB System of Structured Documentation 18


Literate Programming 19


Selected Papers on Computer Science 19


Digital Typography 19


Selected Papers on Analysis of Algorithms 19


Selected Papers on Computer Languages 19


Selected Papers on Discrete Mathematics 19


Surreal Numbers 19


Mathematical Writing 19


Mathematics for the Analysis of Algorithms 20


Mariages Stables 20


Axioms and Hulls 20


3:16 Bible Texts Illuminated 20


Things a Computer Scientist Rarely Talks About 20

8. Works Cited 21


The name Donald Knuth is nearly ubiquitous in the modern science, mathematics and technology universe. Affectionately known as the “Father of Computer Science”, Knuth’s contributions to modern mathematical and computing theory are undeniably fresh and lasting. A man known as much for his quirks and oddities as for his profound ideas about computing and the mathematics of computing, there is no doubt that Knuth’s work will go down in history as revolutionary and culture-changing.
One may ask why this writer has chosen Donald Knuth for a biographical sketch, in the face of so many other more traditional mathematicians. Certainly Knuth is a talented computer scientist and a philosopher of the subject, but his mathematical contributions are less known. The modest goal of this sketch is perhaps to begin to suggest the potential to comprehensively synthesize his mathematical theory and computer science work. Knuth himself says that switching between mathematics and computer science “requires a distinct change of mental gears”, however, when one looks at his contributions in both branches, one sees a distinct mathematical influence over his computer science work. Much of the theoretical machinery he develops from a mathematical perspective has substantial effect on this future work in computer science. If this short essay can begin to accomplish one thing, it would be to elucidate the importance of Knuth’s original mathematical contributions on his better known computer science work.

2.Donald Knuth’s Background

One cannot approach a study of a great mathematician without at least briefly examining the forces within life that led him to his place of discovery. Donald Knuth’s history had no less an effect on him then many other great mathematicians throughout history. Given that Knuth’s relationship with his parents appears to have been a large influence on his life, the discussion of Donald Knuth’s background will begin with a summary of the lives of his parents and the perspective they brought the child Knuth. From this point, a discussion of Knuth’s own background and influences will commence

2.1Knuth’s Parents

Donald Knuth’s parents were Ervin Henry Knuth and Louise Marie Bohning. [1] Ervin Knuth attended school in Chicago, where he met Louise Bohning in 1931. After a two year courtship period, they announced their engagement on Louise’s 21st birthday on October 17, 1933. They were finally married on July 26th and moved to Milwaukee, Wisconsin, where they were to make their home. [2]
Ervin wound up teaching at Emmaus Lutheran School. In addition, Ervin played the organ every Sunday in church, an avid lover of the instrument. His professional passion, the English language, would soon become an important element of his famous son’s life.

2.2Knuth’s Childhood and Early Education

Donald Ervin Knuth was born in January 10, 1938 in Milwaukee, Wisconsin. His interests were manifold as a child, but were largely musical. He played and composed music for the saxophone and tuba. One oft-repeated anecdote of Knuth showing his early potential involves the candy manufacturing company known as the George Ziegler Company, which produced candy from the 1950’s until 1974. [3] The Ziegler Company manufactured a candy bar known as “Ziegler’s Giant Bar”. When in 8th grade, Ziegler issued a challenge offering a prize to the person who could make the most unique words out of the phrase “Ziegler’s Giant Bar”. Knuth, showing an early insight and aptitude for discovering patterns in language, won the contest easily. In his own words:
I found approximately 4,500 words without using the apostrophe. With the apostrophe, I could have found many more. The judges had only about 2,500 on their master list. [4]
He was an exceptional student in nearly all areas of study – he graduated from Milwaukee Lutheran High School in 1956 with the highest G.P.A. ever recorded at the school.
An odd trait that marks Knuth’s young life appears to be his lack of self confidence. Even with all of his exceptional qualities, evidenced clearly even in his youth, he seemed to lack the confidence of a man who possessed his talents. His interests, at this point in his life, were not directed towards mathematics at all, though, late in high school, he did begin to show an interest in visualizing multi-dimensional surfaces – often spending many hours making plots of them by hand.

2.3Case Institute and a Move to Mathematics

Lacking any particular direction for his life, Knuth accepted a physics scholarship offered to him at the Case Institute in Cleveland, later to become Case Western Reserve. He later explains:
The system channeled anybody with an aptitude for science into physics. It was post World War II and there was a lot of excitement in the field. [4]
Knuth showed no particular disinterest in physics, but it failed to catch his fancy. He found physics practicals a dreadfully undesirable proposition and was eventually persuaded by Paul Guenther, a mathematics professor and a student of George Birkhoff at Harvard [5], to switch from physics to mathematics.
Additionally, the story goes, one day Knuth missed the bus that was to take him and his bandmates to a performance. Finding himself with some time to spare, he decided to work on a challenge problem posed by one of his math professors. He solved the problem and thus earned an automatic “A” in the class and perhaps provided the impetus necessary for him to move away from physics and towards mathematics.
Another important moment occurs during his first year at Case Institute. He used an IBM 650 (pre-FORTRAN) computer for the first time. He remarked:
The manual we got from IBM would show examples of programs and I knew I could do ... better than that. So I thought I might have some talent. [6]
This would spark an interest in computing for Knuth – the grammar of computing languages had finally been merged with the natural language grammar skills his father taught him and he’d used so frequently growing up. He continued to develop this interest and in 1958 he used a computer program to measure Case’s basketball team’s performance. His senior year of his undergraduate studies, he published two papers, entitled An imaginary number system and On methods of constructing sets of mutually orthogonal Latin squares using a computer. In the first paper, Knuth constructs an imaginary number system in base 2i and in the second paper he gives two sets of five mutually orthogonal Latin squares of order 12. Through his final day at Case, Knuth, still appearing to be at least partly motivated by a great sense of inadequacy, performed much additional detailed work – well above and beyond what was required of him by his professors. [1]
So much, and so noticeable, was this effort that Knuth put into his studies, that the faculty of Case (by a special vote) [7] took an unusual and largely unprecedented step of awarding him his M.S. as well as his B.S. when he graduated in June 1960. [1] He was awarded two prestigious fellowships in 1960 – the Woodrow Wilson Fellowship and a National Foundation Fellowship. These were to be the first of many fellowships and awards Knuth was to enjoy through his professional life.

2.4Knuth at Caltech

In the fall of 1960, he enrolled in the California Institute Technology as a doctoral student in mathematics. His successful defense of this thesis, entitled Finite semifields and projective planes earned him his Ph.D. in June of 1963. This is considered an unusually rapid granting of a Ph.D. at a top research institution, not unusual for Knuth, but what was truly remarkable about this is a brief look at the work he published during the period while he was at Caltech.
Addison-Wesley, in 1962, was interested in the development of a textbook on computers, and given Knuth’s reputation in the early world of computing, they asked him to write it. He agreed, and during the next three and a half years, he handwrote more than 3000 pages simply on compliers. This work was to eventually form the material for Knuth’s magnum opus, The Art of Computer Programming. Also during his years as a doctoral student at Caltech, Knuth worked on a number of different problems – generally combinatorial math problems that utilized Knuth’s newfound computing machinery to solve. He published a computer generated computation of Euler’s constant to 1271 decimal places. [7] In addition, he began to be interested in solving problems of symbolic computation with computers. In 1962, he produced one of the earliest papers on the evaluation of polynomials using computers. Also that year, he produced a history of writing compilers essay – an early look into rigor in compiler analysis.

2.5Professor Knuth

Graduating in 1963, Knuth accepted a job as an Assistant Professor of Mathematics at his alma mater, the California Institute of Technology. He continued to work on computing problems – all the while using his mathematical background an interests to apply rigor to the world of computing. In addition, from 1964-1967, he served as the Editor of Programming Languages for the Association of Computational Machinery. In 1968, he was offered a full professorship at Stanford University, where Knuth was to spend the remainder of his professional life.
His works in the late 1960’s were manifold, showing both the breadth and depth of Knuth’s talent. He published an eclectic array of mathematical and computer science work, with titles such as Computer-drawn flow charts, Transcendental numbers based on the Fibonacci sequence, Billiard balls in an equilateral triangle, Representing numbers using only one 4, and Computation of tangent, Euler, and Bernoulli numbers. [8]
By the early 1970’s Knuth was slightly more focused on his primary interest in the cross-disciplinary study of rigor in computing – the analysis of algorithms and the semantics of programming languages. This led to works such as The analysis of algorithms, Examples of formal semantics, and Top-down syntax analysis. Through the mid 1970’s, Knuth continued to do some mathematical research, especially in the areas of combinatorics and recreational math. His interests in sets, number theory, and finite geometries led to the publishing of several substantial papers including Complements and transitive closures, Permutations with nonnegative partial sums, The asymptotic number of geometries, Random matroids, Identities from partition involutions, and Notes of generalized Dedekind sums. [8]
Knuth’s professional meanderings while at Stanford often led to brilliant discoveries. In 1976, Knuth became so frustrated with the inherent inadequacy of typesetting software for mathematical and scientific purposes that he took nearly 10 years to develop a mathematical and scientific typesetting language known as TeX. In addition, he developed software to develop fonts, appropriately named METAFONT. This was to be the beginning of one of Knuth’s lasting professional ambitions – programming that is designed for people, not computers. The idea of “literate programming” was to permeate Knuth’s thoughts and ideas for the next 30 years. TeX, in many ways, fundamentally changed the manner in which mathematics is communicated and the way in which science is “done.”

2.6Retirement –> Increased Workload?

Finally, after nearly 20 years at Stanford, and after making myriad contributions to mathematics and computer science, Knuth officially retired in 1993. By his own admission, his work on the yet unfinished behemoth work The Art of Computer Programming will take him at least the next twenty years, eventually growing into a seven volume (with some volumes being divided into subvolumes) compendium on computer science. Given his inclination to professional distraction and “tangential research,” one wonders if this process may not take many years longer. In what is perhaps one of the most grossly understated self-critiques, Knuth notes in a 1999 e-zine interview, “I’ve never been a good estimator for how long things are going to take.” [10]

2.7Awards and Recognition

The awards that Knuth has received throughout his professional career are nothing short of staggering. He holds 24 documented honoris causa (honorary) doctorate degrees from universities as varied as Dartmouth, the University of Macedonia, Harvard, the University of Waterloo in Canada, and St. Andrews University in Scotland. Other awards include the Alan M. Turing award from the Association for Computing Machinery (1971), the Franklin Medal (1988), the John von Neumann Medal from the Institute of Electrical and Electronics Engineers (IEEE), and the Adelskold Medal from the Swedish Academy of Sciences (1994). Jimmy Carter himself presented Knuth with the National Medal of Science award in 1979, and the Japanese Inamori Foundation, in 1996, awarded the Kyoto Prize for lifetime achievement in the arts and sciences to Knuth. [10] He has been granted memberships into some of the most prestigious societies, including the British Computing Society, the St. Petersburg Academy of Science, the IEEE, the National Academy of Engineering, and the American Academy of Arts and Sciences. [10] In 1990, Knuth was granted the singular title from Stanford, the Professor of the Art of Computer Programming – a title not granted to anyone save Knuth. [1]
Furthermore, Knuth has the distinct honor of bearing the namesake of the “Donald E. Knuth prize” for outstanding contributions to the foundations of computer science. This award is granted every one and a half years by the Association for Computing Machinery and the IEEE. [11] It places special emphasis on “a sustained record of high-impact, seminal contributions to the foundations of computer science.”

3.Knuth’s Contributions

Knuth’s contributions to mathematics and mathematical understandings of computer science throughout the years have brought about great change in the way in which computing is understood. The mathematical discipline brought to the subject, as well as the emphasis on literacy and literate programming are substantial bodies of knowledge in and of themselves. In addition, Knuth’s mathematical works are certainly substantial – the focus of this section will be to relate his theoretical mathematical work to his practical output in the world of algorithms and programming.

3.1Groups, Semigroups, and Field Theory

One of Knuth’s earliest contributions to mathematics was in the area of finite fields. Knuth was one of the first to recognize the theoretical and practical importance of finite fields and thus group theory in the development of practical computing concepts. In 1964, he published a paper detailing tables of data for finite fields, making practical computation within finite fields a much more attainable reality. Much of this information ended up in Volume 2 of The Art of Computer Programming: Seminumerical Algorithms. [1]

Permutation groups are another important concept in the study of finite fields. Knuth pioneered mechanisms to represent these groups in computers as well as develop the properties of these groups much further than before. His work in combinatorics essentially builds off of his work with permutation groups, which was fleshed out in its theoretical detail in his 1991 paper Efficient representation of perm groups. He notes that this paper “presents an elementary version of C C Sims's algorithm for computing strong generators of a given perm group, together with a proof of correctness and some notes about appropriate low-level data structures.” [1] This is one of his better known contributions – a classic intersection of the theoretical with the practical.

His work from a mathematical perspective for computation with groups is also essential – the Knuth-Bendix Completion algorithm is of fundamental importance for computing with algebraic groups and semigroups. In this algorithm, he proves important properties of when a finite set can be reduced to a finitely terminating, confluent term rewriting system which preserves identities in reduction – in the vernacular, solving problems in algebraic systems by systematically deriving consequences of relations to give a resultant set (if the system can be solved). [16] This work in universal algebra has important theoretical and practical applications.

3.2Semantics, Formal Grammars, and Programming Languages

Since his youth, semantics, especially formal semantics, fascinated Knuth. It was only natural that this would become a professional obsession. A number of his papers focused on the topic of constructing and interpreting formal grammars. His 1968 paper Semantics of context-free languages is often quoted and used even to this day in automata theory. In fact, Knuth’s Selected Papers on Computer Languages (2003) is an entire 600 page collection of essays devoted to formal syntax and grammars from a mathematical and computational perspective. In the preface of this book, Knuth writes:

I found the mathematical approach to grammar immediately appealing---so much so, in fact, that I must admit to taking a copy of Noam Chomsky's Syntactic Structures along with me on my honeymoon in 1961. During odd moments, while crossing the Atlantic in an ocean liner and while camping in Europe, I read that book rather thoroughly and tried to answer some basic theoretical questions. Here was a marvelous thing: a mathematical theory of language in which I could use a computer programmer's intuition! The mathematical, linguistic, and algorithmic parts of my life had previously been totally separate. During the ensuing years those three aspects became steadily more intertwined; and by the end of the 1960s I found myself a Professor of Computer Science at Stanford University, primarily because of work that I had done with respect to languages for computer programming. [12]
This area of study, representing a unification of combinatorial math, linguistics, and formal grammars forms an essential body of knowledge for which he will long be remembered. A practical and important output of this area of research is the Knuth-Morris-Pratt algorithm, which is an efficient (essentially linear complexity) mechanism to search a string for patterns utilizing the “knowledge” contained with in the pattern and the information provided by successive failures. [17]

3.3Mathematical Notation

Knuth’s work in computational and theoretical combinatorics led to him being able to represent a class of problems that was previously outside the realm of practical mathematics. His 1976 paper, Mathematics and Computer Science: Coping with Finiteness. Advances in Our Ability to Compute are Bringing Us Substantially Closer to Ultimate Limitations, is well remembered for introducing Knuth’s convenient and useful “up-arrow” notation. [13] Wanting to clarify and generalize the concept of iterated exponentiation, especially as it related to combinatorial problems, Knuth introduced the up-arrow convention to conveniently allow for the representation of extremely large numbers. Knuth found the usual superscript notation inconvenient, especially for iterated cases, and thus founded his own system. He simply defines the up-arrow operator as follows:

Furthermore, he allows the double arrow operator, which is defined as:

Of course, this was designed to be extended to the generalized case, which is as follows:

As an additional note, a ↑↑ n is often called the “power tower” of order n. [15]

3.4Literate Programming

Another invention of Knuth’s is what is now termed “literate programming.” Again, his history of mixing language, art, and mathematics allowed him to take a very cross-disciplinary approach to the problems of computer science. Literate programming essentially turns what was viewed as the “normal” method of writing computer software on its head. Rather than writing code containing descriptive bits (generally known as comments), Knuth envisioned writing descriptive text, essentially works of literature, that contained embedded machine interpreted code. [18] WEB was the computer system that Knuth created to illustrate this concept, which ended up consisting of two programs, tangle, which compiled the computer language Pascal, and weave which eventually was used to produce the typesetting language TeX. [19]
There is some debate over the success of the concept of literate programming. Many believe, as is often exhibited in Knuth’s work and interests, that it is a mechanism which produces code for “perfectionists.” That is to say that the code is neat and clear, but takes far too much time to develop and maintain. Practical coders, playing the game more for pragmatic purposes, find less of a need for perfection and more of a need for rapid output – and are often opposed to the literate programming methodology for this reason. Still, no one denies the practical importance of writing “self-documenting” code, and modern programming methodologies, such as Rapid Application Development (RAD) and Extreme Programming (XP), make at least limited use of Knuth’s idea of literate coding.

4.Idiosyncrasies and Quirks

There are few men in the world of modern mathematics and computer science that rival Knuth with their well known quirks and unique behaviors. Knuth is a man of many oddities, some humorous, others insightful, and still more just plain strange. In all of his writings, his speeches, and his topics of consideration, a uniquely gifted Donald Knuth always manages to make something memorable occur.

4.1The Finder’s Fee – Knuth’s Reward Checks

There is little doubt among those who know him, and most that are at least casually aware of him, that Knuth is a perfectionist in the extreme. One of his long standing traditions, expounded in the preface of each of his books, has been to offer a bounty of $2.56 to the first discoverer of each error, whether typographical, technical, or historical, found in any of his books. The reason for this – Knuth says that $2.56 is one hexadecimal dollar [20], or alternatively that $2.56 is $100 million, represented in the binary decimal system. This allows Knuth’s books to inch toward perfection over time, as the errors continually found in his works slowly are corrected and updated – inching the books towards absolute perfection. In addition, Knuth offers a bounty of $.32 for each suggestion which he considers valuable towards the purpose of improving the text substantively. He offers no reason for why a suggestion is worth $.32.
Among the world of the initiated, these checks are coveted and prized – as acknowledgements from the “father of computer science.” Knuth has written over $20,000 of checks [21] over the past 30 years, but these checks, even ones for large amounts, are cashed less and less frequently. As one famous geek site Slashdot message board signature goes:

Intelligence: Finding an error in a Knuth text.
Stupidity: Cashing that $2.56 check you got.

4.2Definitely not a Technophile

Another oddity, for a man who essentially created the rigorous discipline of computer science is his apparent unwillingness to actually use the technology. According to his website, he decided that he was done using email on January 1, 1990, saying that “15 years of email was enough for one lifetime”. As such, he does all of his correspondence via “snail mail” and also in “batch mode”, generally every three months. [20] Knuth is also careful to point out that Americans should be using the term “email” instead of “e-mail”, as the term, in his opinion, does not need hyphenation once absorbed into the vernacular.
In addition, virtually all of his programming exercises and computing research are done in assembly language, the language that is essentially closest to machine code. Knuth generally eschews higher-level languages, which are prettier and easier to decipher, for the simplicity and stability of his own machine-generated code and language.


Another oddity in his personality is his manner of believing in a “god.” In several interviews, including a recent one with NPR, Knuth espouses a belief in God, specifically the God of the Christian Bible. [21] This would not normally be odd, considering a majority of the American population does indeed hold a belief in God. However, this, as with many other things in Knuth’s life, takes on a rather unique form. In 1991, Knuth wrote a book entitled 3:16 Bible Texts Illuminated. This text is Knuth’s attempt to examine the Bible, and consequently the character of God, through what he calls the process of “stratified random sampling” – the analysis of the 3rd chapter, 16th verse of every book in the Bible. Considered by many, even in the community of unbelievers, to be a colorful and amusing, yet insightful look at the Bible – it has been a strikingly different work from a scientist with a unique view of the world.

4.4Mathematical Humor and Easter Eggs

Knuth’s mathematical humor permeates his work. Software is normally versioned by major release number in front of a decimal place and minor releases and “bug” fixes successively placed behind the decimal place. Knuth adhered to this convention initially in both of his major commercial releases, TeX and METAFONT. However, once he had established a full feature set for these software packages, he changed his versioning system.
TeX reached version 3, before Knuth, for reasons unbeknownst to the world, decided on a new way to version his software. He chose values of subsequent minor releases of his software which asymptotically approach the famous transcendental number π. As such, the release after 3 is versioned 3.1, followed by 3.14 and 3.141… [22] He claims that this process will continue indefinitely, until the “absolutely final change (to be made after my death) will be to change the version number to π, at which point all remaining bugs will become features.” [22] Currently, TeX is at version 3.141592. METAFONT is versioned much the same way, asymptotically approaching Euler’s constant e.

5.Errors and Misstatements

While this certainly strays from the original intent of this paper, and is perhaps slightly non-standard in a biographical work, this author cannot ignore the substantial amount of wrong information on the Internet and in print with regards to Knuth’s life and work. In the interest of correcting and preserving truth in the historical record, a few of the largest and most common mistakes with regards to Knuth’s career will be briefly expounded upon in this section.

5.1Big-O Notation

Knuth is occasionally incorrectly credited with “introducing big-O notation.” [23] This appears to have stemmed from misstatements and ambiguities from a few sources which credit him with the lesser feat of introducing big-O notation to algorithmic efficiency. Knuth is certainly a user of big-O notation, which characterizes asymptotic complexity – certainly a valid area of study in algorithms. Big-O notation originated many years before Knuth in Germany - Paul Bachmann and Edmund Landau created and popularized its use before the idea of a formal mathematical and computational algorithm ever existed.

5.2Knuth’s Series and Number

The world of naming numbers and other ideas is always an interesting one. It certainly is something of a capricious venture – with individuals taking and giving credit where it is perhaps not due. The generally reliable Stephen Wolfram and Eric Weisstein’s MathWorld website seems to be at fault with this one. They termed the series

used in an American Mathematical Monthly article Knuth authored entitled “Problem 10832”, the “Knuth Series.” However, there seems to be extremely little support for this claim. MathWorld points their article back to the Encyclopedia of Integer Sequences, sequence number A096616, maintained by AT&T Labs, which cites MathWorld’s Eric Weisstein as the source of the article. This circular reference causes many problems for those trying to differentiate legitimate terminology from the lingo and slang permeating the general climate. Internet searches done on major search engines found that MathWorld is the only website that recognizes this terminology, thus making them the inventors of the rather non-standard and unapproved term. No doubt mathematical terminology is occasionally invented this way, but at this nascent stage of development, it causes more confusion than it alleviates.

5.3Literate Programming – the real reason?

Another controversial topic that occasionally surfaces in critiques of Knuth’s work is his “real” reason for inventing the concept of literate programming. It seems that some believe that Knuth invented and used literate programming because of Stanford University’s intellectual property policy. People speculate that Knuth believed that Stanford would own all of his published code, but not his literature, and so it was advantageous to him to produce all of his code in the form of book form – to essentially obfuscate the fact that this is computer code being written. [24]
Research for this essay could find essentially no information confirming this idea. Knuth apparently believes in the concept of literate programming enough to have spent years defending it – and in fact, his major work TeX, written using his literate programming style, is entirely in the public domain. Knuth doesn’t appear to be overly concerned about protecting his intellectual property rights, if he even has them. In addition, this sort of situation doesn’t appear to have ever been litigated at Stanford, so statements made regarding the ownership of computer code should stay outside the world of fact and purely in the realm of conjecture.

5.4NPR and the Hexadecimal Dollar

To nitpick briefly about the recent NPR story, in reporting on David Knuth David Kestenbaum mistakenly refers to the conversion of $2.56 to binary as 10 million dollars [21]. This is correctly represented as 100 million dollars.


There seems to be no more fitting a way to close this biography than with an oft-repeated anecdote story now a part of the Internet lore surrounding the life and illustrative of the stature of Donald Knuth – the respect that his very name conjures up in the community of mathematicians and computer scientists.

Legend has it that Richard M. Stallman, the founder of the Free Software Foundation and the creator of EMACS and GNU C, Linus Torvalds, the creator of Linux, and Donald E. Knuth engage in a discussion on whose impact on the computerized world was the greatest.
Stallman: "God told me I have programmed the best editor in the world!"
Torvalds: "Well, God told *me* that I have programmed the best operating system in the world!"
Knuth: "Wait, wait - I never said that."

And that humorous and totally fabricated story perhaps nicely sums up the life and times of Donald Knuth. A man revered as much for his ideas and stature as for his quirks, oddities, and personal idiosyncrasies. As a scientist, he had with seemingly unlimited abilities, a charmingly geeky wit, and a never-ending desire to achieve perfection. His ability to synthesize mathematical and computational ideas for the betterment of both branches of study will no doubt have an impact felt many years into the future. To Knuth, and only Knuth, can the world rightfully give the title the “Father of Computer Science.”

7.Knuth’s Collected Works

The Art of Computer Programming (TAOCP)

The TeXbook


Computers & Typesetting

Concrete Mathematics

The Stanford GraphBase


The CWEB System of Structured Documentation

Literate Programming

Selected Papers on Computer Science

Digital Typography

Selected Papers on Analysis of Algorithms

Selected Papers on Computer Languages

Selected Papers on Discrete Mathematics

Surreal Numbers

Mathematical Writing

Mathematics for the Analysis of Algorithms

Mariages Stables

Axioms and Hulls

3:16 Bible Texts Illuminated

Things a Computer Scientist Rarely Talks About

8.Works Cited

Please Note: This works cited is listed roughly in order of citation in the sketch, not in alphabetical order.

1. “Donald Ervin Knuth”, From St. Andrews.

  1. “Louise Marie Bohning Knuth”, Donald Knuth.

  1. “Retro Milwaukee Products”.

  1. Shasha, Dennis and Lazere, Cathy. “Out of Their Minds: the lives and discoveries of

15 great computer scientists”. Copernicus Press, New York, NY 1995.

  1. “The Mathematics Genealogy Project – Paul Ernest Guenther”.

  1. “Donald E Knuth, in D J Albers and G L Alexanderson (eds.), Mathematical People:

Profiles and Interviews (Boston, 1985), 183-203.

  1. “Donald Knuth’s Home Page”. Donald Knuth.

  1. “Vita”. Donald Knuth.

  1. Bezroukov, Nikolai. “Portraits of Open Source Pioneers”. Electronically Available.

  1. Wallace, Mark. “The Art of Don E. Knuth”. Magazine. Published


  1. Bein, Wolfgang. “Knuth Prize”.

  1. Knuth, Donald E. “Selected Papers on Computer Languages”. Stanford, California

Center for the Study of Language and Information. 2003.

  1. Knuth, Donald E. “Mathematics and Computer Science: Coping with Finiteness. Advances in Our Ability to Compute are Bringing Us Substantially Closer to Ultimate Limitations." Science 194, 1976.

  1. “Knuth’s Up-Arrow Notation”. From Wikipedia.'s_up-arrow_notation

  1. Weisstein, Eric W. "Arrow Notation." From MathWorld--A Wolfram Web Resource.

  1. Weisstein, Eric W. et al. "Knuth-Bendix Completion Algorithm." From MathWorld—A

Wolfram Web Resource.

  1. “Knuth-Morris-Pratt Algorithm”. From Wikipedia.

  1. “Literate Programming”. From Wikipedia.

  1. “WEB”. From Wikipedia.

  1. “Knuth: Frequently Asked Questions”. Donald Knuth.

  1. Kestenbaum, David. “Donald Knuth, Founding Artist of Computer Science”. NPR:

Morning Edition. Aired March 14, 2005. Available at:

  1. “Knuth”. Wikipedia.

  1. “MUF Mastery – Donald Knuth”.

  1. “Literate Programming”.

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur © 2016
rəhbərliyinə müraciət