Babbage difference engine



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

page top