Theory of Computation
CS544 (302&303)

Links

Technical Books

• 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 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.

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