Volume 4 is already written (in our hearts)

Today is the 70th birthday of Donald E. Knuth: Priest of Programming, Titan of Typesetting, Monarch of MMIX, intellectual heir to Turing and von Neumann, greatest living computer scientist by almost-universal assent … alright, you get the idea.

That being the case, Jeff Shallit proposed to various CS bloggers that we should all band together and present the master with a birthday surprise: one post each about how his work has inspired us. The posts are now in! Readers who don’t know about Knuth’s work (are there any?) should start with this post from Luca. Then see this from David Eppstein, this from Doron Zeilberger, this from Jeff, this from Bill Gasarch, and this from Suresh.

Knuth’s impact on my own work and thinking, while vast, has not been directly through research: his main influence on my BibTeX file is that if not for him, I wouldn’t have a BibTeX file. (One reason is that I’m one of the people Doron Zeilberger attacks for ignoring constant factors, and supporting what he calls “the ruling paradigm in computational complexity theory, with its POL vs. EXP dichotomy.”) So I decided to leave Knuth’s scientific oeuvre to others, and to concentrate in this post on his contributions to two other fields: mathematical exposition and computational theology.

Knuth’s creation of the TeX typesetting system — his original motivation being to perfect the layout of his own Art of Computer Programming books — was remarkable in two ways. First, because scientific typesetting is of so little interest to industry, it’s not clear if something like TeX would ever have been invented if not for one man and his borderline-neurotic perfectionism. Second, TeX is one of the only instances I can think of when a complicated software problem was solved so well that it never had to be solved again (nor will it for many decades, one hazards to guess). At least in math, computer science, and physics, the adoption of TeX has been so universal that failure to use it is now a reliable crackpot indicator.

From Wikipedia:

Since version 3, TeX has used an idiosyncratic version numbering system, where updates have been indicated by adding an extra digit at the end of the decimal, so that the version number asymptotically approaches π. This is a reflection of the fact that TeX is now very stable, and only minor updates are anticipated. The current version of TeX is 3.141592; it was last updated in December 2002 … Even though Donald Knuth himself has suggested a few areas in which TeX could have been improved, he indicated that he firmly believes that having an unchanged system that will produce the same output now and in the future is more important than introducing new features. For this reason, he has stated that 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.

But Knuth’s interest in scientific exposition goes far beyond typesetting. His 1974 Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness, which he wrote in one week, was weirdness at the highest possible level: the Beatles’ White Album of math. It’s said to represent the only occasion in history when a new mathematical theory (Conway’s theory of surreal numbers) was introduced in the form of a novel. (Though admittedly, with the exception of one sex scene, this is a “novel” whose plot development mostly takes the form of lemmas.)

Those seeking to improve their own writing should consult Mathematical Writing (available for free on the web), the lecture notes from a course at Stanford taught by Knuth, Tracy Larrabee, and Paul Roberts. Like a lot of Knuth’s work, Mathematical Writing has the refreshing feel of an open-ended conversation: we get to see Knuth interact with students, other teachers, and visiting luminaries like Mary-Claire van Leunen, Paul Halmos, Jeff Ullman, and Leslie Lamport.

Since I’ve blogged before about the battle over academic publishing, I also wanted to mention Knuth’s remarkable and characteristically methodical 2003 letter to the editorial board of the Journal of Algorithms. Knuth asks in a postscript that his letter not be distributed widely — but not surprisingly, it already has been.

In the rest of this post, I’d like to talk about Things A Computer Scientist Rarely Talks About, the only book of Knuth’s for which I collected one of his coveted $2.56 prizes for spotting an error. (Nothing important, just a typo.)

Things is based on a series of lectures on computer science and religion that Knuth gave in 1997 at MIT. (At the risk of oversimplifying: Knuth practices Christianity, but in a strange form less interested in guns and gays than in some business about “universal compassion.”) Perhaps like most readers, when I bought Things I expected yet another essay on “non-overlapping magisteria,” a famous scientist’s apologia justifying his belief in the Virgin Birth and the Resurrection. But Knuth likes to surprise, and what he delivers instead is mostly a meditation on the typography of Bible verses [sic]. More precisely, Things is a “metabook”: a book about the lessons Knuth learned while writing and typesetting an earlier book, one I haven’t yet read, that analyzed verse 3:16 of every book of the Bible.

But this being a lecture series, Knuth also fields questions from the audience about everything from sin and redemption to mathematical Platonism. He has a habit of parrying all the really difficult questions with humor; indeed, he does this so often one comes to suspect humor is his answer. As far as I could tell, there’s only one passage in the entire book where Knuth directly addresses what atheists are probably waiting for him to address. From one of the question periods:

Q: How did you become so interested in God and religion in the first place?

A: It was because of the family I was born into. If I had been born in other circumstances, my religious life would no doubt have been quite different. (p. 155)

And then on to the next question.

To me, what’s remarkable about this response is that Knuth without any hesitation concedes what skeptics from Xenophanes to Richard Dawkins have held up as the central embarrassment of religion. This, of course, is the near-perfect correlation between the content of religious belief and the upbringing of the believer. How, Dawkins is fond of asking, could there possibly be such a thing as a Christian or Hindu or Jewish child? How could a four-year-old already know what he or she thinks about profound questions of cosmogony, history, and ethics — unless, of course, the child were brainwashed by parents or teachers?

My Bayesian friends, like Robin Hanson, carry this argument a step further. For them, the very fact that Knuth knows his beliefs would be different were he born to different parents must, assuming he’s rational, force him to change his beliefs. For how can he believe something with any conviction, if he knows his belief was largely determined by a logically-irrelevant coin toss?

And yet, openly defying the armies of Bayes arrayed against him, here we have Knuth saying, in effect: yes, if I know that if I were some other person my beliefs would be different, but I’m not that other person; I’m Knuth.

So, readers: is Knuth’s response a cop-out, the understandable yet ultimately-indefensible defense of an otherwise-great scientist who never managed to free himself from certain childhood myths? Or is it a profound acknowledgment that none of us ever escape the circumstances of our birth, that we might as well own up to it, that tolerance ought not to require a shared prior, that the pursuit of science and other universal values can coexist with the personal and incommunicable?

Taking a cue from Knuth himself, I’m going to dodge this question. Instead, I decided to end this post by quoting some of my favorite passages from Chapter 6 of Things A Computer Scientist Rarely Talks About.

On computer science and God: “When I talk about computer science as a possible basis for insights about God, of course I’m not thinking about God as a super-smart intellect surrounded by large clusters of ultrafast Linux workstations and great search engines. That’s the user’s point of view.” (p. 168)

“I think it’s fair to say that many of today’s large computer programs rank among the most complex intellectual achievements of all time. They’re absolutely trivial by comparison with any of the works of God, but still they’re somehow closer to those works than anything else we know.” (p. 169)

On infinity: “Infinity is a red herring. I would be perfectly happy to give up immortality if I could only live Super K years before dying ['Super K' being defined similarly to an Ackermann number]. In fact, Super K nanoseconds would be enough.” (p. 172)

On the other hand: “I once thought, if I ever had to preach a sermon in church, I would try to explain Cantor’s theorem to my non-mathematical friends so that they could understand something about the infinite.” (p. 172)

On God and computational complexity: “I think it’s fair to say that God may well be bound by the laws of computational complexity … But I don’t recommend that theologians undertake a deep study of computational complexity (unless, of course, they really enjoy it). ” (p. 174)

On quantum mechanics: “Several years ago, I chanced to open Paul Dirac’s famous book on the subject and I was surprised to find out that Dirac was not only an extremely good writer but also that his book was not totally impossible to understand. The biggest surprise, however — actually a shock — was to learn that the things he talks about in that book were completely different from anything I had ever read in Scientific American or in any other popular account of the subject. Apparently when physicists talk to physicists, they talk about linear transformations of generalized Hilbert spaces over the complex numbers; observable quantities are eigenvalues and eigenfunctions of Hermitian linear operators. But when physicists talk to the general public they don’t dare mention such esoteric things, so they speak instead about particles and spins and such, which are much less than half the story. No wonder I could never really understand the popular articles.” (p. 181)

“The extra detail that gets suppressed when quantum mechanics gets popularized amounts to the fact that, according to quantum mechanics, the universe actually consists of much more data than could ever be observed.” (p. 182)

On free will and the problem of evil: “I can design a program that never crashes if I don’t give the user any options. And if I allow the user to choose from only a small number of options, limited to things that appear on a menu, I can be sure that nothing anomalous will happen, because each option can be foreseen in advance and its effects can be checked. But if I give the user the ability to write programs that will combine with my own program, all hell might break loose. (In this sense the users of Emacs have much more free will than the users of Microsoft Word.) … I suppose we could even regard Figure 5 [a binary tree representing someone's choices] as the Tree of the Knowledge of Good and Evil.” (p. 189-190)

111 Responses to “Volume 4 is already written (in our hearts)”

  1. Marshal SEO Blog Says:

    Happy Birthday Donald E. Knuth!

  2. harrison Says:

    “I think it’s fair to say that God may well be bound by the laws of computational complexity … But I don’t recommend that theologians undertake a deep study of computational complexity (unless, of course, they really enjoy it).”

    Hmm. Just the other day, in fact, I was talking to a friend about how I often think of IP=PSPACE as the class of “tractable” problems assuming the existence of a God/Devil. (Which is metaphysically interesting to me, at least, because it means we can invent EXPTIME-complete games [such as Go] that [probably] not even God could convince us of a solution to).

    I wonder if Knuth, or anyone else, ever thinks of complexity classes in strange metaphysical/theological terms? (Apart from BQP as the class of tractable problems in the physical universe — we know, Scott. :-P)

    And that said, if DEK is reading this, happy 70th birthday, and may you have 70 more. :-)

  3. aravind Says:

    Randomization being my primary research focus, this short mp3 of Knuth’s is often an inspiration. It also includes a nice quip of Rabin’s, connecting theology and pseudorandomness :)

    Happy Birthday, the Don of Computer Science!

  4. John Sidles Says:

    Knuth is a true hero. I especially admire Knuth’s work on literate programming.

    Only about one-in-five-thousand published articles on computer science makes any explicit reference to Knuth’s literate programming practices actually being used.

    Yet the Knuthian ideal of literate programming has been enormously influential … the reason is expressed in a (Wordsworth?) poem:

       In the ancient days of art,
       builders wrought with greatest care
       each minute and hidden part
       for G*d is everwhere.

    The reference is to the stones hidden within the interior walls of a cathedral. Never to be seen by human eyes, these stones were none-the-less carefully dressed.

    In an era in which the median number of references to a scientific article is (necessarily) of order unity, this is a fine poem to meditate upon!

  5. John Sidles Says:

    Note added: it turns out that the above verse was quoted from Longfellow’s poem The Builders.

  6. Robin Hanson Says:

    Yes, Knuth’s response is a cop-out. While we may not be able to escape all of the influences of our origins on our beliefs, we should try to escape what we can, and Knuth clearly could have tried harder.

  7. wolfgang Says:

    Of course it is not a cop-out.
    If one truly believes in God, then one may (depending on the religion) also believe that God placed you in a certain community for a reason.

  8. Chris Austin-Lane Says:

    3:16 is both a lovely book and an interesting book.

    People needn’t worry so much about one another’s beliefs; as long as those beliefs aren’t causing harmful actions, it’s not a problem.

  9. Rasmus Pagh Says:

    I wonder if Knuth himself would consider this a round birthday. I know that he threw a big party 6 years ago for his 1000000th birthday.In any case: Happy birthday, Don!

  10. Job Says:

    I’ve heard that he uses PI digits for dates and times as well.

    My birthday is on the 3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502, don’t forget!

  11. Tim Says:

    I know Knuth is actually some kind of Christian (there are many very different kinds), but I would point out that the question doesn’t actually ask him about his current beliefs about religion, or anything at all about his religious beliefs themselves. All it really asks is why he initially had any interest. Given that a person’s family is usually that person’s first source of non-observational knowledge, Knuth’s answer seems perfectly reasonable to me, and in fact it’s the one I would give to the same question even though I’m an atheist.

    Further, Knuth’s answer doesn’t even mention beliefs! What he says is that his religious life would have been different. This is a distinction that many people (I would lump Dawkins and most modern critics of religion along with religious fundamentalists here) fail to appreciate. Religion, insofar as it is interesting (in my opinion), has very little to do with beliefs at all (or at least not the kind of beliefs that scientists are interested in). It’s the kind of religion that makes “non-overlapping magisteria” a plausible argument, precisely because it doesn’t really care about the historicity of things like the virgin birth or the resurrection. I don’t know if this is what Knuth means when he says “religious life” instead of “religious beliefs,” but it’s consistent with what he says here and with the views of a lot of religious people, some of whom could properly call themselves Christians.

    Now I’ll dodge the question a third and final time by throwing poo in the general direction of Bayesians.

  12. aravind Says:

    Let me also point the readers here to Herb Wilf’s humorous birthday tribute to Knuth, from a few years ago.

  13. Scott Says:

    I wonder if Knuth himself would consider this a round birthday.

    I certainly hope he would, 70 being the smallest weird number (number that’s smaller than the sum of its proper divisors, but not equal to any subset of them).

  14. Sean Carroll Says:

    I’m so glad to read Knuth saying “according to quantum mechanics, the universe actually consists of much more data than could ever be observed.” It’s exactly right, and yet a lot of physicists seem reluctant to put it in those terms.

    (The other thing about quantum mechanics is that physical states can be added together. I think that difference with classical mechanics is also underrated.)

  15. Moshe Says:

    Sean, I cannot speak for other physicists, but for my naive eyes the sentence you quote is simply a definition of the phrase “consists of” in this context. You may feel this is the most natural definition, in the sense of it being the best extension of our daily experience of that expression, but I am not sure such extension is unique.

  16. Moshe Says:

    Also, for the second point, I am fascinated by the questions of where specifically is the difference between classical and quantum mechanics. Lots of the perceived differences really arise because slightly different mathematics is natural in both subjects. So for example, the evolution of a probability distribution in phase space (such as those appearing in statistical mechanics) is also governed by a linear equation (Liouville’s equation), so solutions superpose. Not sure then that superposition is really the new feature of QM.

  17. John Sidles Says:

    Knuth: “according to quantum mechanics, the universe actually consists of much more data than could ever be observed.”

    Strictly speaking, Knuth might have qualified his statement by beginning it with “According to the linear quantum mechanics that is axiomatic in quantum information theory …”. The point being, it is still an open question whether the quantum state-space of the physical world is linear or not.

    When folks simulate quantum systems, they almost always do so by (effectively) projecting linear quantum mechanics onto a nonlinear state-space of lower dimensionality; this technique was invented by Dirac and Frankel way back in 1930–4.

    It turns out to be a pretty considerable challenge to devise experimental tests to prove that real-world quantum mechanics does not have this same projective nature. Needless to say, a working quantum computer (accessing an exponentially large state-space) would constitute precisely the required evidence.

    This situation is perhaps not too different from the state of physics a century ago, when physical state-space was generally considered to be linear and infinite, just like Cartesian mathematical space. It took some subtle experiments, guided by a subtle theory (GR), to confirm that physical space was both nonlinear and dynamical.

    Nowadays, quantum space-space is generally considered to be linear and infinite, just like Hilbert’s eponymous mathematical space. It will take subtle experiments to determine whether the geometry of quantum state-space is in fact curved, and subtle theories to suggest whether this geometry is (or is not) dynamical.

    This is a win-win situation, because if physical quantum state-space is linear and non-dynamical, then quantum computers likely will work (eventually). Good! On the other hand, if quantum state-space should turn out to be nonlinear and non-dynamical, well, that will be good too, because the mathematics is bound to be wonderful!

    My own non-Knuthian opinion is that most things that are interesting are dynamical, and since quantum state-spaces are interesting, they must therefore be dynamical!

    Fortunately, life is fun either way. Huzzah for Knuth! :)

  18. Richard Says:

    How, Dawkins is fond of asking, could there possibly be such a thing as a Christian or Hindu or Jewish child? How could a four-year-old already know what he or she thinks about profound questions of cosmogony, history, and ethics — unless, of course, the child were brainwashed by parents or teachers?

    Scott, If it’s not too rude to ask, would you likely be Jewish if your parents were not? Assuming your answer is no, might you have been similarly brainwashed in your sense of your identity?

  19. Sean Carroll Says:

    Moshe, sorry, but I’m confused about both your comments. On the first one, the point is that in QM you can’t simultaneously measure every observable. In classical mechanics observables are just functions of the state space, but in QM they are operators that map the state space to itself. I’m not sure what this has to do with “consists of,” so I think I’m missing your point.

    On the second point, I don’t think it’s right to compare wavefunctions in QM to distribution functions in classical mechanics; wavefunctions are analogous to single points in phase space (they are the data from which unique future evolutions can be derived). And you definitely can’t add points in phase space.

  20. John Sidles Says:

    Richard says: “Would you likely be Jewish if your parents were not?”

    Ho ho! That is a subtle question. For example, my children definitely are Jewish, although equally definitely I am not (the answer to this riddle happens to be trivial, from a certain point of view).

    A wonderful meditation on this subject (in the various senses of “beautiful”, “true”, “practical”, and “densely encoded”) is Isaac Singer’s short story A Piece of Advice, in the collection published as The Spinoza of Market Street.

  21. Scott Says:

    Richard, I certainly wouldn’t be Jewish if my parents were not. Likewise, if my parents were 14th-century Mongolian goat-herders, I expect that I’d be a Mongolian goat-herder too. But the interesting question then arises, in what sense would it even be me that we were talking about in the first place?

    There’s a Yiddish saying that’s relevant here: As di bubbe volt gehat beytsim volt zi gevain mayn zaidah (“If my grandmother had balls, she’d be my grandfather”). An American version is Popeye the Sailor’s “I yam what I yam, and that’s all that I yam.” Of course, were I neither Jewish nor American, I’d probably know different sayings to the same effect.

  22. Joseph Hertzlinger Says:

    I don’t see why inheriting a belief system should be grounds for disbelief. After all, we inherited the genes for eyes but don’t regard that as grounds for disbelieving what we see.

  23. Luca Says:

    I love the Yiddish saying; on a surprisingly similar note, in Italy we say “if my grandfather had five balls he would be a pinball machine.”

  24. Scott Says:

    Moshe, to expand on what Sean said: for me the key difference is that probabilities don’t destructively interfere with each other. And because of that, given a system in a classical probability distribution, we can always take the stance that “really” it’s one basis state or the other, and only our subjective ignorance prevents us from knowing which one. But with quantum mechanics, such a stance is no longer available to us.

    Of the zillions of ways this difference manifests itself in quantum computing and information, I’ll just mention one example. Given a classical probabilistic algorithm, you can always “pull the randomness out”: that is, treat it as an ordinary deterministic algorithm that takes a random string as input. Lots of theorems about probabilistic algorithms essentially rely on that fact. By contrast, we don’t know of any analogous way to “pull the quantumness out of a quantum algorithm.” This difference is directly related both to quantum computing’s apparently-greater power, and to its being harder to analyze.

  25. Deja vu Says:

    with its POL vs. EXP. dichotomy

    I’m with Doron on this one. Only an academic would call polynomial algorithms feasible. Polynomial algorithms are tractable, while feasibility ends somewhere around O(n^2).

  26. Scott Says:

    Deja vu, your distinction between “tractable” and “feasible” sent me to Webster’s:

    tractable: capable of being easily led, taught, or controlled; easily handled, managed, or wrought

    feasible: capable of being done or carried out; capable of being used or dealt with successfully

    Do others see a difference here? Yeah, alright, I guess I do.

    In the comments section of a previous post, I explained the relationship between polynomial-time solvability and “real-world” feasibility as follows:

    Not in P: Your algorithms are getting slaughtered left and right, like foot soldiers in the Trojan War.

    In P: The war is over — but like Odysseus, you still have a long and perilous journey home.

    n2: Home (but dozens of suitors have been hitting on your wife).

    n polylog(n): You’ve slaughtered the suitors.

  27. The 327th Male Says:

    Joseph Hertzlinger wrote:

    I don’t see why inheriting a belief system should be grounds for disbelief. After all, we inherited the genes for eyes but don’t regard that as grounds for disbelieving what we see.

    I don’t see why it should be grounds for belief either. “Because my parents told me so” is not a valid argument. Besides, you don’t inherit a belief system, you learn it. It’s an idea. Ideas can be changed and altered according to experience, whereas you’re stuck with the genes you have.

  28. anonymous Says:

    On the off chance that Knuth is reading these comments, I would like to know what he thinks of TeXmacs.

  29. milkshake Says:

    a date becomes feasible when impressing-the-babe problem turns out to be tractable

  30. Moshe Says:

    Thanks Sean and Scott, the first point is basically a dispute over assigning ontological status to the wavefunction, but I am really not that interested in onthology to be honest.

    On the second point- it is clear that there is random, probabilistic element in QM, but also that this is not the whole story, so the interesting comparison is to classical random systems. The difference with those does not come down to superposition only, since classical probability distributions superpose as well. I agree that interference is much closer to the point.

  31. Sean Carroll Says:

    Okay, at least now I understand both points. The whole point of my original comment was to express pleasure that Knuth was treating the wavefunction as the true description of reality, which is a point of view that I like. From that it follows that I think the interesting comparison is between wavefunctions and points in phase space, not wavefunctions and classical probability distributions.

    If not agreement, at least carefully defined disagreement is a worthy goal.

  32. John Sidles Says:

    With tongue only slightly in cheek, I will suggest that the main point of quantum physics is to ensure that we live in a universe in which P≠NP.

    The point being, that in a wholly classical universe we could imagine a von Neumann that would cut itself in half (even its atoms) and manufacture two von Neumann machines (each half the size of the original), linked as a two-bit computer.

    Continuing the process (with each von Neumann generation constructed twice as fast as the previous generation, `cuz they’re smaller), in a finite amount of time we have classically constructed a Blum-Shub-Smale machine.

    The point being, if we allow classical physicists as much freedom to pick Hamiltonians as quantum physicists allow themselves, then isn’t computation (potentially) exponentially faster in a classical universe than in a quantum universe? :)

  33. anon Says:

    Isn’t complaining that Knuth acknowledges that his religious life is affected by his upbringing and circumstance, and therefore can’t be ‘logical’ in some sense, a little like suggesting that were one to have lived in different circumstances one might have chosen a different spouse, and therefore ‘logically’ can’t really be in love? Counterfactuals are funny things, and definitely not the same as (thought-) experiments.

  34. John Sidles Says:

    Gee, I accidently clicked “send” before mentioning that the existence versus non-existence of NP-complete cclassical omputational processes is (presumably) related to known hard problems like showing the asymptotic smoothness of solutions to the Navier-Stokes equations. `Cuz if the solutions aren’t asymptotically smooth, well maybe those tiny turbulent vortices are carrying out a computation.

    These are tough problems indeed! :)

  35. Jack in Danville Says:

    Happy Birthday Dr. Knuth! I turned to TAOCP about 10 years ago when I had taken on an over-ambitious coding project, and realized I needed a whole lot of theoretical background if I was going to have any chance of success. Reading all three volumes I learned many nuggets of wisdom (both practical and philosophical), and still have a photocopy of a coveted $2.56 check for reporting a typo.

    I used to wish he would enlist some grad students to help him finish the other planned volumes, but I guess that’s not going to happen, and my interests have moved on. Completing all of his plan would be monumental.

    I may be mistaken, but I believe the good Doctor was also a contributor to discussions on FAUG BBS back in the 80’s. I didn’t know who he was at the time.

  36. Moshe Says:

    Sean, it will have to be a carefully defined disagreement I`m afraid (and I agree those are all good). It is clear that wavefunctions are very different from points in the classical phase space. Part of the difference is the probabilistic nature of them, but I think that is by far the least mysterious part. The gist of QM to me lies precisely in how is fails to be a conventional probabilistic theory, which has to do more with entanglement and less with superposition.

    (As for the “elements of reality“, I`d love to be able to reach carefully defined disagreement. For now it just seems to me that it is just a matter of definitions- you and Knuth like wavefunctions to be real, and I like my food spicy, no point in arguing).

  37. Steve Demuth Says:

    TeX is one of the only instances I can think of when a complicated software problem was solved so well that it never had to be solved again

    Notwithstanding my enormous respect for Dr. Knuth, I would classify TeX per se, from a software engineering perspective, as a truly abominable solution. That many people happily use it, and that it is perfectly stable, says nothing to the contrary. To use a hackneyed supporting example: the QWERTY keyboard is designed as an input device for the human hands, yet so poorly that it cause painful injury to a significant fraction of its frequent users, and is demonstrably less efficient than all sorts of alternatives. Similarly, Microsoft Window is ubiquitous and was for years, despite having a distinctly inferior multi-processing core from software created 10 years before the first line of Windows code.

    Adoption and persistence don’t measure quality of solution.

    So, what’s wrong with TeX (at least as I knew it a decade ago)? It mixes data, format and metadata willy nilly in a fragile stream with extraordinarily poor locality properties. It scarcely permits discernment of the structure of its output, except by completely processing of the entire stream (where is page 127?).

    These are lousy properties for a text formatting program to enforce.

    Now, the various tools that sit on top of TeX can make most of these issues hard to see, or irrelevant, and probably do for most users. Alas, this says nothing good about TeX, only about the ingenuity of people who want to make a hard to understand and use system, usable.

  38. Job Says:

    Steve, you didn’t mention what your preferred typesetting system is.

  39. Steve Demuth Says:

    Job,

    It’s been twelve years since I routinely used typesetting software (my job gives me the luxury of just composing, and letting other people attend to getting the content on a page in an esthetically pleasing fashion when something I write is actually published), so I don’t really have a preferred system for my own use.

  40. Scott Says:

    Steve, I agree with some of your anti-TeX points and would even add a related one: when I get an error message, I can almost never figure out what I did wrong without painstaking trial-and-error (even if it’s some trivial syntactic mistake).

    On the other hand, it’s really not possible to have a file format that lets you tell at a glance where page 127 is, without destroying the whole goal of representation-independence (do you mean page 127 assuming a 10 or 11 point font?).

    More to the point: despite TeX’s flaws, I don’t know of any other package that remotely compares, nor could I suggest how to design one that was much different from TeX itself.

  41. anonymous Says:

    More to the point: despite TeX’s flaws, I don’t know of any other package that remotely compares, nor could I suggest how to design one that was much different from TeX itself.

    TeXmacs is quite comparable. I find it surprising that it is not seriously considered by the cs theory community.

  42. Job Says:

    Doesn’t TeXMacs build on the TeX/LaTeX executables? If so it’s still TeX – with a GUI on top.

  43. Jeremy Henty Says:

    Job#42: no, TeXmacs is not built on top of TeX, it’s a completely separate executable.
    (Although it borrows heavily from TeX’s typesetting ideas, it uses METAFONT fonts, and
    many common LaTeX commands also work similarly in TeXmacs.)

  44. Kurt Says:

    Totally uninformed opinion here, but I would speculate that as Web delivery of content becomes more ubiquitous in the publishing world, MathML-based tools will improve to the point that they eventually replace TeX-based publishing tools. Maybe not for another 5-10 years or so…

  45. cody Says:

    unfortunately, being aware of a problem is not necessarily sufficient to solve the problem (no matter how hard i try, i cannot think clearly around girls i am attracted to). furthermore, he might not consider it a problem, as a suprisingly large number of people have no qualms about logical contradictions within their belief systems (hence hypocracy, though i would assume such a brilliant mathematical mind as Knuth would be bothered by that; though Gödel did starve himself to death).

    our abilities to escape aspects of our childhoods varies widly in both the magnitude and direction of the myth: i broke free of my religious upbringing as soon as i could express it, but my unfounded introversion has changed very little. other people might have much more control over their social behavior, and less control over their spiritual beliefs or lack thereof. and of course this would apply to all other aspects of upbringing as well.

  46. Job Says:

    Kurt, LaTeX is also adapting to the web little by little. It’s easy to setup most web forums to extract and convert LaTeX in posts to images (see http://www.physicsforums.com for instance).

    Also there are a few open source web based LaTeX editors in the works (including one i’m working on but which i won’t plug). Something akin to Goolgle Docs for LaTeX is in the realm of the feasible (think collaboration features) – and given LaTeX’s popularity i think that we will get there at some point.

  47. niel Says:

    Steve Demuth said: So, what’s wrong with TeX (at least as I knew it a decade ago)? It mixes data, format and metadata willy nilly in a fragile stream with extraordinarily poor locality properties. It scarcely permits discernment of the structure of its output, except by completely processing of the entire stream (where is page 127?).

    “Where is page 127″ is not a question about the structure of documents any more than “what mathematical object constitutes the additive identity of Z7″ is a question about the structure of groups. It is precisely because of this that the \pageref command was made: to relieve the author of having to worry about such trivialities.

    As for mixing data and format: well, my experience is largely with LaTeX-style (as opposed to Plain-TeX) style writing, but (to take a simple example) it seems to me that unless you object to people using the \emph command for emphasis — and possibly redefining what \emph does, once, in the pre-amble to contol its’ appearance — then these can be neatly divorced by importing separate a file. It doesn’t prevent you from mixing things, but it doesn’t force you to either.

    One doesn’t write documents using TeX: one writes a meta-document — an equivalence class of documents, and TeX is there to help pick a representative of that class which is well-wrought for the purpose at hand. All the tools to cleanly write a meta-document are there. Then, as with all programming languages/projects, the question is whether these tools are effectively used or taught…

  48. Steve Demuth Says:

    On the other hand, it’s really not possible to have a file format that lets you tell at a glance where page 127 is, without destroying the whole goal of representation-independence (do you mean page 127 assuming a 10 or 11 point font?).

    Scott,

    You are right, and it may have been a poor choice of example on my part.

    My real point was that a “good” design would strive to not mix content with rendering information any more than necessary, and would surely make the operations “extract content,” and “change styling independently of content” obvious ones. The tools people have built on TeX may accomplish this, but TeX, as Knuth designed it, does not.

    And having worked at one point on a project to create a WYSIWYG editor with TeX documents as the underlying file format, I can tell you that TeX is an obstacle to success in making a good visual composition tool because of its poor locality properties.

    In fact the first thoughts I had when I first looked at TeX (and I used raw TeX extensively in the early 90s) was “this was designed by a programmer who has not tried at all to think like a non-programmer in his design process.” Why? Because a TeX document is fundamentally a computer program, and the TeX program a “compiler” for generating virtual machine code for computerized typesetting system. This is certainly one solution to the problem of document formatting, but not one designed to endear itself to people whose profession is putting type and symbols on pages.
    Only a programmer, or someone who can be trained to think more or less like a programmer, would think it an obvious and elegant solution.

    TeX was a huge breakthrough for me because it simultaneously did two things for me. First, it made it possible and even almost simple to electronically typeset books generated from complex databases,using desktop software. All I had to do was write a program to generate the program (TeX document), and the TeX compiler took care of the hoary details.

    Second, it opened my eyes to the reality that by themselves, even the best programmers have a hard time building solutions for the broad run of users, because they just can’t not think like programmers when designing stuff.

  49. Louis Says:

    Knuth, you achieved the impossible: you gave me the tools to prove to others that writing ability and style matter as much to mathematics as the abstract thinking behind it.

    Happy 70th birthday, dude.

  50. anonymous Says:

    And having worked at one point on a project to create a WYSIWYG editor with TeX documents as the underlying file format, I can tell you that TeX is an obstacle to success in making a good visual composition tool because of its poor locality properties.
    Are you familiar with the WYSIWYG TeXmacs? How well do you think it has succeeded in producing output similar to TeX using its own real-time typesetting engine?

  51. John Sidles Says:

    Many people conflate “what you see is what you get (WYSIWYG)” with “what you want is what you get (WYWIWYG)”.”

    My wife, who works in graphic design and publishing assures me that, as a general rule, WYWIWYG typographic tools are utterly disastrous in the hands of non-artists, because (a) no two WYWIWYG articles look alike, and (b) most of them look horrible.

    The genius of TeX and LaTeX is that they are “What you get is what Knuth wants” — and fortunately, Knuth has excellent taste. For which we all (well, almost all) are very grateful to Prof. Knuth!

  52. Sean Says:

    LaTeX is severely flawed. It should be possible to have real-time typesetting as you type. Yes, I know there are technical difficulties, but I don’t care. I’ve tried some of the programs that claim to do this, and their interfaces are uniformly terrible. LaTeX also suffers from cryptic error messages. If I can easily diagnose an error by looking at the source, then LaTeX should be able to do so, too. It should tell me what the error is instead of making me look for it myself and wasting my time. I imagine there are technical difficulties here, too. Again, I don’t care.

  53. anonymous Says:

    LaTeX is severely flawed. It should be possible to have real-time typesetting as you type. Yes, I know there are technical difficulties, but I don’t care. I’ve tried some of the programs that claim to do this, and their interfaces are uniformly terrible.
    Have you tried TeXmacs? What do you think of it?

  54. Scott Says:

    Sean, have you tried Scientific Workplace? That’s a quasi-WYSIWYG program that I often use for composing TeX (in conjunction with WinEdt, for those occasions when Scientific Workplace screws up).

    Incidentally, I just tried TeXmacs last night. The output looks great, the fact that it’s WYSIWYG is amazing, and it’s hard to beat the price. But

    (1) the interface sucks (basically a Unix interface sloppily ported to Windows),
    (2) it doesn’t do a great job of importing my existing TeX files, and
    (3) the fact that it doesn’t support TeX as a native language would make it all but impossible to coauthor papers in a TeX-based world.

    And yes, regarding (1), I know the moral failure is entirely mine for using Windows at all. What can I say? It’s like a heroin addiction…

  55. anonymous Says:

    (1) the interface sucks (basically a Unix interface sloppily ported to Windows),
    (2) it doesn’t do a great job of importing my existing TeX files, and
    (3) the fact that it doesn’t support TeX as a native language would make it extremely hard to coauthor papers in a TeX-based world.

    (1) is relatively easy to fix; try sending your suggestions for improving the UI to the TeXmacs team.

    Supposing the interface has been improved to your liking, are points (2) and (3) a big deal when writing research papers from scratch?

    It seems that (2) and (3) will always be an issue, so does this mean the cs theory community will never adopt better writing tools?

  56. Scott Says:

    anonymous: If the interface were reasonable, then yes, I’d consider using TeXmacs for single-author papers. I can’t speak for anyone else in the CS theory community.

  57. John Sidles Says:

    In the OS X world, a (free) TeXmacs-utility that many folks use is “LaTeXiT”, which provides a simple like visual interface based on palettes from which you select the equation elements you want.

    LaTeXiT is not useful for documents bigger than a multi-line equation or a one-page table, but it is very nice for smaller typesetting jobs. It’s especially handy when you can’t quite recall how to type the Knuthian LaTeX code for “curly brackets under a sequence” … just pull down the “decorations” menu to see a huge selection.

    As a bonus, LaTeXit allow you to drag-and-drop nicely typeset equations into your PowerPoint presentation (ugh!) and/or Word document (double-ugh!), and/or paste the debugged LaTeX code into your (longer) LaTeX article.

    I use it mainly as a visual debugging environment when creating longer equations and tables.

  58. Jon Tyson Says:

    In response to all the comments about TeX compilers, I’ve been using Scientific Workplace as a front-end to compile LaTeX for many years, and I can’t understand why anyone would prefer to handle the raw LaTeX code manually. (Note that Scientific Workplace will still allow you to enter raw code, but it is rarely necessary.) Prof. Effros at UCLA was telling everyone to get that some years back, after doing raw TeX compiling by hand for many years.

    Some people claim that eMacs is better without ever trying Scientific Workplace, and I always ask them if they like $’s, {}’s, and /’s so much why they don’t print out and read their work that way. I don’t even have to think about that when editing!

    I’m using an older version of Scientific Workplace (version 3.0), and the only drawback is that 3.0 doesn’t always allow you to edit other people’s raw LaTeX very well. (You can easily import it raw, though.) I don’t know how well it works with the newer versions. I haven’t tried any of the other front-ends, like LyX, and I’m somewhat interested to know if any are better from people who have tried both the competitor front-ends and Scientific Workplace. (I use windows XP.)

  59. Scott Says:

    Jon: Try the newer versions of SWP; they let you save a file as “Portable LaTeX.” I’ve collaborated with five or six coauthors who TeX entirely by hand, and the only one who complained to me about SWP’s output was Greg Kuperberg (but he would, wouldn’t he? ;-) ).

  60. KWRegan Says:

    Scientific Workplace is a descendant (via “Scientific Word”) of the 1980s WYSIWYG processor T^3. Generosity from the Oxford Mathematical Institute’s Maths Prizes Fund accomplished my effort to bring affordable and flexible math typesetting to Oxford, replacing the dual-wheel Greek/symbol typewriters they had in the room coincidentally numbered T-3. I continued using T^3 for my own papers and courses into the early ’90s until co-authors dragged me into (La)TeX…

    …and my point is: WYSIWYG made me too conscious of fitting words onto lines and lines onto pages. I’m definitely faster with notes and (last-minute:-) problem sets in LaTeX. Fitting handouts onto 1 sheet and conference papers into pages is blanked from my mind until after I’m done writing.

    The long and lasting value of TeX, however, is that so much can be built on it. Indeed, the T^3 people turned away my pixel-rewrite of their fonts and ideas for a 2D extension to ASCII (so we wouldn’t find ourselves 20 years later still writing “T^3″) mainly because they were switching to METAFONT. TeX is Flexible, Foundational, Free, Full-Featured, Fast, and Fun. And transparent. The discussion that could unify elements of the “Things” book and points Scott raises (even about faith) is on the value and place of such “labors of love” and long-view projects in the (computer) science community.

  61. anonymous Says:

    …and my point is: WYSIWYG made me too conscious of fitting words onto lines and lines onto pages. I’m definitely faster with notes and (last-minute:-) problem sets in LaTeX. Fitting handouts onto 1 sheet and conference papers into pages is blanked from my mind until after I’m done writing.
    Advantages of WYSIWYG:
    * it’s easier to enter text (no hard to understand errors)
    * it’s easier to read while you are editing
    * it’s easier to meet page limits with a nice looking layout
    * it’s easier to learn
    * it’s faster since there is no separate compile

  62. KWRegan Says:

    I’m giving you my own personal witness:

    () I grew up in a WYSIWYG household.

    () I went to a school where only WYSIWYG was available.

    () I led a mission to convert an entire university—in fact it was Dawkins’ university—to WYSIWYG. Not just Maths, even the Russian Studies Dept. followed my call.

    () I carried WYSIWYG into my professional life. No paper or proposal I wrote in WYSIWYG was ever rejected (hey…:-). I had dreams of expanding WYSIWYG into the very standard that communications are based on.

    () I don’t do WYSIWYG anymore. Call me an apostate, if you like.

    Maybe childhood influences are overrated. :-) Anyway, I think the *ed points lose their force over a several-months’ time period.

  63. anonymous Says:

    I’m giving you my own personal witness…
    What’s different now is that most computers are fast enough to edit TeX-like quality in real-time — at least for short documents such as research papers and book chapters.

    I guess what I find surprising is that the vast majority of CS/math researchers prefer TeX over WYSIWYG editors. This is hard to explain given the high quality of software such as TeXmacs.

  64. KWRegan Says:

    Actually, my colleagues here in Buffalo combine WYSIWYG and raw-LaTeX editing modes, viewing equations just after/while typing them. One question we would have about new tools is portability. MS Word is often not even portable to MS Word. But then there are the “F” points in my first post.

    Better support for graphics—I suppose the tools you mention are better than add-ons like MikTeX and Beamer?—is a selling point. I used MS Word’s HTML export for this file of reproducible hash anomalies in a chess program because it was the quickest to hand for pasting my screenshots.

    What you say about “fast enough” makes me add something I snipped out of my first comment. The TeX error messages emphasize helping you carry on rather than pinpointing the error, and I wonder how much that was due to jobs being a real cost to re-run, even from interactive terminals, in the 1970s.

  65. anonymous Says:

    One question we would have about new tools is portability. MS Word is often not even portable to MS Word.
    TeXmacs’ main author is a mathematician who uses it to write up research papers. I’m sure he cares about portability across versions as well.
    Better support for graphics—I suppose the tools you mention are better than add-ons like MikTeX and Beamer?—is a selling point.
    Please just try it out! I think you will be very impressed :)

    http://www.texmacs.org/tmweb/home/screenshots.en.html

    Sample TeXmacs documents:

    http://www.texmacs.org/Samples/texmacs.pdf

    http://www.texmacs.org/Samples/Galois/

  66. Karl W. Says:

    While I feel the urge to defend the TeXmacs interface with religious fervor now, I think that this isn’t the best place to start a flame war. There needs to be something like alt.religion.texmacs (or, perhaps, alt.sex.editor-war).

    PS. In case anyone was wondering, vi(m) sucks.

  67. Karl W. Says:

    Oh, I forgot to mention. Has anybody tried AUCTeX?:

    http://www.gnu.org/software/auctex/

  68. Jay Daigle Says:

    I use Auctex. I really like it, it makes TeX editing easy. But then, I use Emacs for everything. And I used the live preview function for about a week–it’s cool and fun to show off, but I find it easier to edit without the distractions. But then, I’m one of the people who enjoys the fact that LaTeX is basically a programming language; doing stuff in WYSIWYG wouldn’t be nearly as cool. And I’m unconvinced that it would give me quite the level of response I want.

    To answer someone else’s question: when I read other people’s work I generally want the compiled document, but when I’m reading my own stuff I often read the source file instead of the compiled version. As long as it’s coded in my style, that’s just as easy to read, and sometimes easier, with the exception of some very long formulas where word-wrap starts being a problem.

  69. John Sidles Says:

    Most of this thread has been devoted to the question “Are GUI interfaces to TeX a good idea or not?”

    Just to state the obvious, can anyone think of a less consequential Knuth-related question?

    Knuth’s home page provides a link to a more profound set of Knuth-raised questions … questions to which Knuth provides neither answers nor clues as to how answers might be found.

    For personal reasons, I have decided to write out my own answers Knuth’s questions … but this will take a few weeks. Perhaps others will post their answers sooner.

  70. anonymous Says:

    Knuth’s 97 stories on Peoples Archives:
    http://www.peoplesarchive.com/browse/movies/6895/

  71. Not Even Right Says:

    At least in math, computer science, and physics, the adoption of TeX has been so universal that failure to use it is now a reliable crackpot indicator.

    While I know that almost all journals require authors submitting articles for publication to prepare their manuscripts in Tex to get them published readily, I find the above idea, originally from Dave Bacon, quite innovative!

  72. Jeremy Henty Says:

    Scott, the TeXmac devs are porting and reworking the GUI as we speak, so if anyone has specific criticisms
    or change requests I’ll pass them on.

    It would also be useful to know in what ways TeXmacs failed to import your LaTeX; it’s certainly the intention
    that “clean LaTeX” (for some rather ill-defined value of that predicate) should import without problems.

  73. KWRegan Says:

    (Ad John S.) While telling a personal tale relevant to the TeX-vs… discussion, I was wanting to wend toward the “consequential” topics of the nature and place of his work, and perspectives in the community. Since this thread has slowed down, I’ll try more directly.

    We’ve all heard about the drive toward specialization and intellectual fragmentation and amassing “publishable units”. A statement I like is in M. Mitchell Waldrop’s book Complexity (the “chaos” kind—Search Inside on the words “provocative lessons” to find pp60–61). To me Donald Knuth has always stood for the resistance to this, for the depth and relevance of a centralized perspective.

    Comments? I don’t think there’s a “Trouble with CS” as said for physics in Lee Smolin’s book, in which that issue figures. My points are more about diversity being healthy, the world’s general need to take the longer view, and active training to see things beyond individual selves.

    (Hat tip for linking DEK’s Iraq-motivated page; on his point #3, after the 1984 US invasion of Grenada I sketched lyrics ending “But if these rules [UN, IMF etc.] are your true ones / Then why your coming with the ships and guns? / Why the bloodbath, and why the bombs? / Does your system simply not work?”)

  74. John Sidles Says:

    Ken Regan’s “personal witness” post was IMHO humorous, kindly, and true — the trifecta of blogging.

    The above link to Knuth’s Infrequently Asked Questions was inspired by Jonathan Israel’s Enlightenment Contested.

    Israel’s book can be read (meaning “the way I like to read it from a science and engineering point-of-view is …”) as an in-depth historical account of how the scientific community asked (and answered) such Knuthian questions during the 17th and 18th centuries.

    Why don’t we ask-and-answer questions that way any more? That is in itself a mighty interesting yet infrequently asked question.

  75. Jon Tyson Says:

    Hi Scott,

    In reguards to your reply, my very old version 3.0 of Scientific Workplace exports portable LaTeX perfectly well. May problem is that it doesn’t import other people’s hand-written LaTeX that well.

    Are the newer versions better at this? (Up to now I haven’t seen much reason to shell out for an upgrade, and I couldn’t get a very definitive answer from the software vendor.)

  76. Scott Says:

    Hmm … tough question. My version does OK (not great) at importing other people’s LaTeX, and I seem to remember it doing worse in the past, but I’ve been using SWP for 11 years and I don’t remember at which version(s) the improvement (if there were any) occurred.

  77. Ashley Says:

    Inspired by all these celebrations, I just bought a copy of Selected Papers on the Analysis of Algorithms. Anyone who’s working on proving P=NP may be excited to learn that Knuth offered a prize of “one live turkey” to the first person to do so, in his paper “A terminological proposal”, which popularised the term NP-hard. So get cracking!

  78. John Ferguson Says:

    If a child grows up in a religious background and then chooses to continue that religion as an adult, it does not mean their choice was dictated by their upbringing. Personally I was sent to Christian church when I was young, but I chose to become Christian when I was 17. I have also met many children who indeed had chosen Christianity by the age of 4 and not merely followed their parents.

    I found Knuth’s insights into religion very interesting. I am tempted to send them my church’s minister, but I fear he wouldn’t get the underlying concepts. He’s good at theology, but computers not so much.

    I wish I had 1/2 the brainpower of Knuth.

  79. John Sidles Says:

    Of all technical professions, mathematicians are the most likely to profess “belief in God” (about 40%), while biologists and physicists are the least likely (about 20%).

    Knuth’s 3:16 covers the mathematicians rationale for “belief in God” quite beautifully. Mathematical analyses (like Godel’s Ontological Proof) have not been widely accepted. Nonetheless, mathematicians are the most religious of technical professionals.

    Among biologists, Ed Wilson’s autobiography Naturalist gives a deeply personal account of Wilson’s loss of (Baptist) faith, which was compensated by a life-long growth in Wilson’s experience of biophilia. This path is typical of biologists.

    Among physicists, Steven Weinberg’s “The more the universe seems comprehensible, the more it also seems pointless” pretty much sums it up (I dunno whether Weinberg is right about the whole universe, but within the narrow context of the Standard Model, Weinberg’s remark is well-founded).

    Einstein famously finessed the issue by embracing Spinozist Deism: “I believe in Spinoza’s God, who reveals Himself in the lawful harmony of the world, not in a God who concerns Himself with the fate and the doings of mankind.”

    My own opinion is simple and pragmatic: religion and philosophy differ greatly from mathematics and science, in the specific sense that it is neither necessary not desirable that everyone agree even on fundamental principles. As evidence of which, the above belief systems (though very different) function very well together.

    Perhaps someday we will all know and agree upon “the truth.” But I for one am not gonna hold my breath. :)

  80. lylebot Says:

    Personally I was sent to Christian church when I was young, but I chose to become Christian when I was 17.

    But was that a fully-informed choice? Did you also go to synagogues and mosques and so on? Did you go to churches of different denominations? In other words, did you give all the options an equal chance, or did the one that you were brought up with get more consideration than anything else?

  81. John Sidles Says:

    But was that a fully-informed choice?

    The interesting question “Whose choice is fully-informed?” is asked and answered in today’s NYT review So, Young Mr. Spinoza, Just What Is Your Thinking About God?

    An emerging characteristic of the 21st century’s embrace of the Enlightenment is that the historians, artists, and mathematicians—and many other disciplines too—are all asking pretty much the same set of questions.

  82. Raoul Ohio Says:

    John says: An emerging characteristic of the 21st century’s embrace of the Enlightenment is that the historians, artists, and mathematicians—and many other disciplines too—are all asking pretty much the same set of questions.

    I wonder where one finds statistics on this topic. Sounds rather far fetched to me. Could it be wishful thinking?

  83. Abdelrazak Younes Says:

    To Jon Tyson:
    You can find some element of comparison between LyX and Scientific Workplace at this page:

    http://wiki.lyx.org/LyX/LyXVsScientificWorkplace

    Please note that some of the complaints of the author are already solved in latest version (LyX-1.5.3).

    Hope this helps.

  84. John Sidles Says:

    Raoul Ohio Says: “I wonder where one finds statistics on [the embrace of the Enlightenment]. Sounds rather far fetched to me. Could it be wishful thinking?”

    That’s a fun idea, Raoul! Here is a MathSciNet search for “(Review Text=(moral) OR Review Text=(ethical) OR Review Text=(social) OR Review Text=(historical))”, organized decade-by-decade:

    1930-9: 19
    1940-9: 172
    1950-9: 440
    1960-9: 684
    1970-9: 1,960
    1980-9: 3,691
    1990-9: 3,603
    2000-present: 3,183

    Pretty obviously, the mathematical community has begun to think hard about these topics.

    Of course, one has to be careful. Lowell Brown used to quote a historian of science who came to lunch at Fermilab and announced: “Heisenberg’s work is not so important: his article on the uncertainty principle is very seldom referenced nowadays.” :)

  85. Scott Says:

    John, what was the growth rate for other math papers over the same period? (I’m guessing also exponential.)

  86. Peter Sheldrick Says:

    I really don’t know why Doron Zeilberger is so unhappy about asymptotics and so demanding for better constants. I mean, doesn’t everyone agree that if you know (roughly) the constants in the runtime to an algorithm in addition to the asymptotics, that you’re better off than without knowing them?

  87. John Sidles Says:

    Scott: John, what was the growth rate for other math papers over the same period? (I’m guessing also exponential.)

    Scott, it is surprisingly hard to think of any academic topic that is not growing exponentially. Not because these topics-in-decline don’t exist, but because (almost by definition) topics-in-decline are hard to think of.

    However, older geezers (like me) definitely can call some to mind. Magnetic bubble memory … analytic S-matrix theory … rollamite mechanisms … fluidic computers … ouch!

    Of course, nothing is ever lost from idea-space … even untrendy ideas still have viability, and can combine with other ideas in surprising ways.

  88. KWRegan Says:

    Zeilberger is quite right that papers that design algorithms in the main fail to apply practical performance metrics. Fifteen years ago NSF wanted to sponsor the creation of tools that would make it easier for theoreticians to code and test their algorithms—what has come of this?

    The response, though, parallels what Scott has written about skepticism of quantum computing: attention to constants has not led to good theory—and I’m speaking as one who started trying. Google “theory of constant factors” in quotes and you get zip. Google it without quotes, and the 2nd hit is a cite of the one real paper I know, Neil Jones’ 1993 STOC paper Constant-time factors do matter, but that’s just showing a constant-factor time-hierarchy in a standard RAM model, something holding more by-definition in other models I’ve devised. After that comes…well, the 8th hit is Wikipedia’s page on the “Cosmological Constant”—does that help? :-) At least it reminds one of the point Scott popularizes that no algorithm in this universe can involve more than 10^122 bits or anything—since this is a Knuth thread, make that the hex number 1 followed by a hundred-and-one hex-0’s.

  89. bill payne Says:

    My ACM publications

    http://portal.acm.org/results.cfm?query=ProfileID%3A81332520373&querydisp=ProfileID%3A81332520373&coll=GUIDE&dl=GUIDE&CFID=11614876&CFTOKEN=62796220

    and

    http://portal.acm.org/results.cfm?query=ProfileID%3A81100557695&querydisp=ProfileID%3A81100557695&coll=GUIDE&dl=GUIDE&CFID=12086890&CFTOKEN=54620783

    may help get these messes settled.

    How the Iraq/Iran War Got Started

    http://www.prosefights.org/thecanadian/thecanadian.htm#gotstarted

    I see that I am about 6 months older than Knuth – and 45 days younger than saddam.

    I met and drank beer with knuth at Ottis Rechard’s home in Pullman, WA in about 1966.

    http://www.prosefights.org/rechard/walden.htm

    Let’s all hope for peaceful settlement of these unfortunate matters … and not WWIII.

  90. SP Says:

    So, readers: is Knuth’s response a cop-out, the understandable yet ultimately-indefensible defense of an otherwise-great scientist who never managed to free himself from certain childhood myths?

    Yes it’s an admission from an astounding intellect that his childhood nurture affects his decision making and belief structure.

    The interesting thing about this, to me anyways, is that you’d be hard pressed to find an atheist that is willing to concede the same, yet in my short life experience I’ve noticed that atheist parents are equally as guilty, if not more so, of brainwashing their children into disbelief.

    His accurate self perception is probably the greatest catalyst of his profound contributions to the community.

    Happy 70th.

  91. Ferris Squizzix Says:

    Is it so improbable that there is a bearded man who lives on a cloud and who sees, knows, and controls everything in a vast universe that he himself created? That is not such a bold belief, is it?

  92. Job Says:

    It is fairly improbable, since there are countless possible beliefs that are as “little” bold as that one. I’d say:
    p = 1/(your creativity)

  93. niel Says:

    The interesting thing about this, to me anyways, is that you’d be hard pressed to find an atheist that is willing to concede the same, yet in my short life experience I’ve noticed that atheist parents are equally as guilty, if not more so, of brainwashing their children into disbelief.

    I couldn’t tell you if atheist parents are usually so guilty, but if you feel that it’s so hard to find atheists who were not originally atheists, as children, perhaps you’re not actually trying too hard.

  94. Tim Says:

    “For how can he believe something with any conviction, if he knows his belief was largely determined by a logically-irrelevant coin toss?”

    Wait – your childhood and your parents are “irrelevant coin toss”? Wow. This was Christianity we were talking about?

    I think most Christians think that these things are (more or less) chosen and affected by the God. And I hope you don’t forget that (to my knowledge) most Christians consider also belief more a gift of the God than your own choice/work.

    The matter is related to the concept of predestination (see Wikipedia). There are Christians who think e.g. that your fate has already been chosen (or at least known) by the God in the beginning of time.

  95. SP Says:

    @Niel
    I couldn’t tell you if atheist parents are usually so guilty, but if you feel that it’s so hard to find atheists who were not originally atheists, as children, perhaps you’re not actually trying too hard.

    Niel the points isn’t that one simply believes what their parents believe. It’s that nurture affects decision making. I don’t have any problem comprehending why someone who was molested by a priest turns atheist. I get it. I just think it’s admirable when people are willing to admit that their belief structure is a product of past experiences. It takes a humble person to understand themselves so well as a human being.

  96. Bobby Fischman Says:

    Anyhow, if Donald Knuth is so smart, why does he believe that an old man in the sky controls the world?

  97. Tyler DiPietro Says:

    “Anyhow, if Donald Knuth is so smart, why does he believe that an old man in the sky controls the world?”

    I don’t know if that’s an accurate representation of Knuth’s beliefs, but it is nonetheless a non-sequitor. Smart people are not immune to believing stupid things.

  98. Bobby Fischman Says:

    Sequitor: If they believe stupid things, then they are not smart people.

  99. Peter Sheldrick Says:

    Bobby, were there any smart people who lived > 500 years ago?

  100. John Sidles Says:

    Peter Sheldrick asks: Bobby, were there any smart people who lived > 500 years ago?

    Averroes!

    Cuz, like, duh, who was it d’ya think who started those secret societies, of radical-minded folks, that hid the treasures, that Nicolas Cage is always chasing after? I ask you!

  101. Bobby Fischman Says:

    Averroes? Ever since 9/11 Muslims are so au courant. It seems to me that Donald Knuth is smart in some things but dumb in others, like everyone else. People were not smart in physical science > 500 years ago. They were smart in mathematics, though.

  102. Job Says:

    The whole religious process is so much without rationale (driven mostly by inheritance, custom, etc) that i wouldn’t exactly call believers “dumb” for believing. It’s like being called dumb for wearing pants rather than nothing at all, isn’t it? When i get up in the morning i don’t rationalize pants-wearing – i just wear them – and i may be wrong about it.

    And if it were shown that there’s probably no reason to wear pants at all i would still wear them, because it’s a part of my life by now and i have more important things to do than update my life to the pantless version just because i’m probably not required to wear pants anymore.

    If Knuth likes his trousers, then isn’t that a good reason to wear them? Does everything in a person’s life have to be driven by logic? Emotions and stuff are relevant they say. If logic said that one must cut one’s hand off…

    If Knuth is so smart then why does he still have two hands? Does he know that he’s probably not required to not cut his left hand off?

    (he does have two hands right?)

  103. Job Says:

    Have you ever just found yourself somewhere talking about pants-wearing for no good reason?

  104. James Says:

    No.

  105. cody Says:

    Bobby Fischman, how about Eratosthenes of Cyrene? or Aristarchos of Samos? given the very limited tools they had (both physical and mathematical), they did an awfully good job, early in our development.

  106. cody Says:

    oh, Bobby Fischman: …and of course Democritus and Archimedes and probably many i dont remember, never learned about, were lost to history, or never even recorded.

  107. John Sidles Says:

    Bobby Fischman: don’t forget Hero of Alexandria:

    It is almost certain that Hero taught at the Musaeum of Alexandria, which included the famous Library of Alexandria, because most of his writings appear as lecture notes for courses in mathematics, mechanics, physics and pneumatics. Although the field was not formalized until the 20th century, it is thought that the work of Hero, his programmable automated devices in particular, represents some of the first formal research into cybernetics.

    So it is, that Hero was the first to achieve the fond dream of every professor … lecture notes that endure in history! :)

  108. Jonathan Vos Post Says:

    “Hero was the first to achieve the fond dream of every professor … lecture notes that endure in history!”

    Yeah, but he really got screwed on the intellectual property on steam engines and cybernetic devices. No stock options, no IPO, no dot-com millions. Otherwise he’d have been owning a major league sports team, and/or VC in a free enterprise space program company.

    And Archimedes? Lost his head completely…

  109. John Sidles Says:

    Just to keep this topic going (until Scott launches a new one), it is a truism of history that “big science” projects don’t begin until the theoretical and algorithmic foundations are in-place to ensure that they project is going to work.

    Examples: nuclear physics/computational dynamics and the atomic bomb, aero/astronautics and space program, shotgun sequencing and the (fast version) genome project, and of course … Knuthian algorithms and the internet!

    So a key question for both young researchers and futurologists is (as ever) what is going to be humanity’s next big-science project?

    And especially for readers of this blog, what will be this project’s sexy algorithmic and theoretical foundations?

    Please don’t say “DRM” … :)

  110. RubeRad Says:

    Things A Computer Scientist Rarely Talks About

    Knuth’s own website links to Dobbs for downloads of the original lectures, but Dobbs seems OBE. A little googling is no help. Anybody know of where the .mp3 can be downloaded? Or have them and willing to post?

  111. RubeRad Says:

    Sorry, that’s http://technetcast.ddj.com/tnc_program.html?program_id=50