Theory of Computability

General Info

  • Instructor: Yuxi Fu, Room 3-327, SEIEE Building
  • Lectures: Tuesdays 8:00-10:40 AM, Room 101, Xia Yuan;
    Sundays 7:00-9:30 PM, SEIEE Building 3-318
  • TA: Qiang Yin (尹强)
  • Office hour: Mondays 6:00-7:00 PM, Room 3-327, SEIEE Building

Lectures

  1. Problems and Effective Solution, 9/17/2013. (PDF)
  2. Recursive Function, 9/21/2013. (PDF)
  3. Church's Lambda Calculus, 9/24/2013. (PDF)
  4. Turing Machine, 9/29/2013. (PDF)
  5. Register Machine, 9/29/2013. (PDF)
  6. Church-Turing Thesis, 10/8/2013. (PDF)
  7. Problem Index, 10/13/2013. (PDF)
  8. Recursive Set, 10/20/2013. (PDF)
  9. Recursively Enumerable Set, 10/22/2013. (PDF)
  10. Creative Set, 11/3/2013. (PDF)
  11. Computational Complexity, 11/5/2013. (PDF)
  12. Elementary Function. (PDF)
  13. Turing Reducibility, 12/10/2013. (PDF)
  14. Arithmetic Hierarchy, 12/19/2013. (PDF)

References

  • Cutland, Nigel. Computability: An introduction to recursive function theory. Cambridge university press, 1980.
  • Soare, Robert I. Recursively enumerable sets and degrees: A study of computable functions and computably generated sets. Springer, 1987.
  • Rogers, H. Theory of recursive functions and effective computability. McGraw-Hill. 1967.

Last updated: March 6, 2014