Thursday, January 07, 2010

DO NOT do this when choosing books for your class

When I took my first graduate course in complexity theory the professor had FOUR books on the REQUIRED FOR THE COURSE list. I bought all four. He said that
We may not use these books much but they will be good to have on your shelf if you go into theory.
I am the only one from that class who went into theory. One of them I have used (Hopcroft and Ullman's White Book). The other three I never touched and no longer have. I do not know what I did with them.

He was wrong, but for an interesting reason. Two of the books were on grubby Turing Machine stuff and models. (I don't recall what the third one was.) Things like constructing a universal Turing machine with 5 states. To be fair, theory was changing: Looking at grubby Turing Machine simulations was a dying field. Hence even a complexity theorist would not be served well by these books. We didn't even do this material in that class.

However, while I can be sympathetic that the prof didn't know that complexity theory was changing, asking students to buy FOUR books that are good to have on your shelf is a terrible idea.


  1. GASARCH, the phrase "grubby Turing Machine stuff and models" surely expresses a Great Truth. Which of course means that there is an opposite Great Truth.

    Here is von Neumann expressing that opposite Great Truth in his 1947 essay The Mathematician:

    "As a mathematical discipline travels far from its empirical source, or still more, if it is a second and third generation only indirectly inspired by ideas coming from "reality" it is beset with very grave dangers. ... the only remedy seems to me to be the rejuvenating return to the source: the re-injection of more or less directly empirical ideas."

    If only *one* student in that class "went into theory" (in the academic sense of that phrase) ... then isn't it likely that many of the other students in the class ended up embracing "directly empirical ideas" (in von Neumann's broad phrase)?

    To me---and perhaps to many students---von Neumann's phrase "directly empirical ideas" is immensely more welcoming than "grubby models" ... although the latter wording *is* provocative. :)

    The resulting diversity is IMHO a very good thing for computer science/complexity theory ... because these are issues regarding which it is neither necessary nor desirable for all to think alike.

    Perhaps the take-home message is that it is preferable to have too many books rather than too few, and many narratives about mathematical disciplines rather than few? :)

  2. Perhaps this was before text books became so terribly, insanely, overpriced like they are now.

  3. Even though the field was changing, if you didn't even do that material in class, I can't be sympathetic.

  4. Your time was unlucky to be in. Sipser wrote his book many years later ... :) I'm sure it would have been still on your shelf, had it existed in ur generation.

  5. Your time was unlucky to be in. Sipser wrote his book many years later

    Hopcroft and Ullman's white book was just fine as a textbook for its era. It is certainly nowhere near as readable as Sipser's text but it contains some key classic results that Sipser's text lacks.

  6. Sipser's book is the only real theory book on my shelf so far, I am an undergrad :P

  7. to last anon:
    where do you go to school?