Theory of Computation
CSC 389 and CSC 544

Links

Technical Books

• 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 NP-completeness theory.

Background and History

• Alan Turing by Andrew Hodges who wrote Alan Turing, The Enigma.
• Kurt Gödel
• Mathematics, The Loss of Certainty by Morris Kline, Oxford University Press.
• The Mathematical Experience, Philip Davis and Reuben Hersh, Mariner Books, 1998.
• Tractatus Logico-Philosophicus, Ludwig Wittgenstein.
• Philosophical Investigations, Ludwig Wittgenstein.
• 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, 2000.
• Raymond Smullyan: The Lady or the Tiger?
• Rudy Rucker: Infinity and the Mind, Princeton U. Press, 1995.

Other

• A Turing Machine Applet