Babbage difference engine

Reading

Books

[G] O. Goldreich, Complexity: A Conceptual Perspective, Cambridge University Press.
[GJ] M. Garey and D. Johnson. Computers and intractability: A guide to NP-Completeness. W. H. Freeman & Co., 1979.
[HMU] J. Hopcroft, R. Motwani, J. Ullman, Intriduction to Automata, Languages, and Computation, Addison Welesley.

Lecture Notes

Turing Machines & Decidability

Turing Machine, from Wikipedia
S. C. Kleene, Origins of recursive function theory, Annals of the History of Computing, 3 (1981), 52-67.
D. Hilbert, Mathematical Problems (English translation), Bull. Amer. Math. Society, 8 (1901-1902), 473-479.
M. Davis, Why Godel didn't have Church's thesis, Information and Control 54 (1982), 3-24.
M. Davis, Hilbert's tenth problem is unsolvable, Amer. Math. Monthly, 1973, 233-269.
J. Hartmanis, Observations about the development of theoretical computer science, Annals of the History of Computing, 3 (1981), 42-51.
J.E. Hopcroft, Turing machines, Scientific American, 250:5 (1984), 86-98.
A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Scoiety, 2 (1936), 230-265.
A. M. Turing, 1948, "Intelligent Machinery." Reprinted in "Cybernetics: Key Papers." Ed. C.R. Evans and A.D.J. Robertson. Baltimore: University Park Press, 1968. p. 31.

Complexity Theory

J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Transactions of AMS, 117 (1965), 285-306.
M. Sipser, The history and status of the P versus NP question, Proc. 24th Annual ACM Symposium. Theory of Computing, 1992, 603-619.
L. Stockmeyer, Classifying the computational complexity of problems, J. Symbolic Logic, 52 (1987), 1-43.