Theory of Computation
- Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages, and
Computation, Addison Wesley, 2001.
- Giorgio Odifreddi: Classical Recursion Theory, North-Holland, 1992.
- 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. Garey, Johnson is the standard guide to
Background and History
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: April 9th, 2002.