Theory of Computation
CSC 389 and CSC 544
- Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages, and
Computation, Addison Wesley, 2001.
- Giorgio Odifreddi: Classical Recursion Theory, North-Holland, 1992.
- S. Barry Cooper: Computability Theory, Chapman & Hall, 2004.
- Garey, Johnson: Computers and Intractability, Freeman, 1979.
Hopcroft, Motwani, Ullman is an updated version of the classical Hopcroft,
Ullman text on automata theory. Presentation is much improved. Odifreddi's
book covers computability theory (decidability) emphasizing the philosophical
and scientific context. Cooper is a shorter introduction, that, however, often
goes into surprising depth. Garey, Johnson is the standard guide to
Background and History
- Alan Turing by Andrew
Hodges who wrote Alan Turing, The Enigma.
- Mathematics, The Loss of Certainty by Morris Kline, Oxford University
- The Mathematical Experience, Philip Davis and Reuben Hersh, Mariner Books,
- Tractatus Logico-Philosophicus,
- Philosophical Investigations, Ludwig
- Martin Davis, The Universal Computer (paperback as Engines of Logic).
(Traces the history of ideas that went into Turing's Universal Computer,
starting with Leibniz's work.)
- Charles and Ray Eames, A Computer Perspective, Harvard University Press,
1990. (Pictures of computer pioneers and early computing devices.)
Fiction and popular accounts
- Neal Stephenson: Cryptonomicon,
Harperperennial, 2000. (Talks about Turing's work during the 2nd world war.)
- John L. Casti: The Cambridge Quintet, Perseus, 1999. (Discussion on the
possibility of Artificial Intelligence.)
- William Gibson, Bruce Sterling: The Difference Engine, 1992. (What would
have happened if Babbage had been successful in building the Analytical
Engine? Great idea, poor execution.)
- Apostolos Doxiadis, Uncle Petros & Goldbach's Conjecture, Bloomsbury,
- Raymond Smullyan: The Lady or the Tiger?
- Rudy Rucker: Infinity and the Mind, Princeton U. Press, 1995.
Last updated: December 9th, 2003.