Design and Analysis of Algorithms
Set Theory and Logic
History of Computing
- For a history of computers from the early calculating machines of Pascal
to the design of the von Neumann computer, see Herman Goldstine's excellent The
Computer from Pascal to von Neumann.
- There are many books about Charles
Babbage and his difference
and analytical engines that foreshadow the von Neumann computer. Doron
Swade's account of the London's Science Museums effort to actually build
parts of the difference engine makes suspenseful reading, and offers many
insights into Babbage's thinking.
Limits of Computation
- Kurt Gödel published his
famous incompleteness theorem in 1931. Several years later, Alan
Turing developed his theoretical model of computation (the
Turing machine) and recast the incompleteness theorem, showing that the
halting problem is undecidable. For a history of the impact of Gödel's
theorem on mathematics, see Kline's "Mathematics. The Loss of
- Popular accounts of Gödel's theorem can be found in several of Raymond
Smullyan's books ("Lady or Tiger", and "Forever
Undecided"), and Douglas Hofstaedter's "Goedel, Escher,
Bach". Also check out Rucker's "Infinity
and the Mind" which is fun reading, and makes connections to
philosophy and cognitive science. It contains a full proof of Gödel's theorem. Another
readable account of Gödel's theorem is by Nagel
- Andrew Hodges' account
of Turing's life also contains explanations of Turing's technical
contributions to computer science. Ag good introduction to computability
theory is Martin Davis's book on "Computability
- In Neil Stephenson's science fiction novel "Cryptonomicon" Alan
Turing makes an appearance as a character, and an amazing number of
technical details, about Turing's work on descrypting the German Enigma
machine during the second world war are explained.
- Cormen, Leiserson, Rivest, Stone is the standard textbook for an
- The standard reference, however, is Donald Knuth's "The
Art of Computer Programming".
Last updated: January 15th, 2002.