Design and Analysis of
History of Computing
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
- Andrew Hodges' account
of Turing's life also contains explanations of Turing's technical
contributions to computer science. The movie
The Codebreaker talks about some of
that as well. A 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.
Interviews, Puzzles, etc.
How would you move Mount Fuji, William Poundstone, 2003. About
the Microsoft Puzzle interviews.
- Algorithms for
Interviews, Aziz, Prakash, 2010.
Puzzles for Programmers and Pros, Shasha, 2007. About puzzles more
Algoritmic Puzzles, Levitin, 2011.
- FoldIt project
- xkcd Traveling Salesman Problem
- Traveling Salesman,
- Game about Squares
Last updated: March 10th, 2015.