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.)
- 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: January 15, 2001.