The Deep Question: P or NP
- G. Woeginger's P versus NP page
- Letter from Gödel to von Neumann
- S. Aaronson interview on computational complexity (Mindscape podcast)
The Hardest Problem of All: NP-completeness
- Wikipedia: List of NP-complete problems
Optimization
- P. Crescenzi & V. Kann's Compendium of NP-hard optimization problems
- Traveling Salesperson Problem (TSP) pages at University of Waterloo
Grand Unified Theory of Computation
- Computability and Complexity from the Stanford Encyclopedia of Philosophy
- The Analytical Engine: J. Walker's collection of writings on Babbage's computing machinery
- Alan Turing's 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem
- A. Sakharov's resource center for the Foundations of Mathematics
- D. Keenan's To dissect a mockingbird: a graphical notation for the lambda calculus with animated reduction
- Wikipedia: Wang tile
- L. Fortnow on the efficient Church-Turing thesis (email TA for a pdf, if unaccessible)
General Computation References
-
Wikipedia: List of important publications in computer science
-
C. Moore's and S. Merten's textbook The Nature of Computation