Design and Analysis of
Algorithms
CSC 321
Algorithms
Visualizations
Sorting
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
Certainty".
- 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
and Newman.
- 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
and Unsolvability".
- 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.
Python
Marcus Schaefer
Last updated: October 19th, 2011.