Computer Science 75010: Theoretical Computer Science
Graduate Center, City University of New York
Fall 2002

Announcements:

• Information about the first exam, scheduled for 10 June.
  

Handouts:

• Syllabus
• Outline
• Homework 1 (due 13 September)
  Comments on Homework 1
  
• For lecture on Friday, 13 September:
  • Finite State Machine Explorer (by Matt Chapman)
• Homework 2 (due 20 September)
  Comments on Homework 2
  
• Homework 3 (due 27 September)
• For lecture on Friday, 27 September:
  • Turing Machine overview (by Andreas Ehrencrona) and an incrementer and adder
  • Another Turing Machine (by Derek Thompson)
  • And another Turing Machine (by Andrew Hodges)
  • Biography of Turing (by by J J O'Connor and E F Robertson, St. Andrews U.)
• Information for Exam 1, including versions of the exam given (4 October)
  
• Homework 4 (due 11 October)
• Comments on Homework 4
  
• Homework 5 (due 18 October)
• Homework 6 (due 25 October)
• Homework 7 (due 1 November)
• For lecture on Friday, 1 November:
  
  • Post Correspondence Problem (by Ling Zhao, U Alberta) 
  • Biography of Post (by J J O'Connor and E F Robertson, St. Andrews U.)
• For lecture on Friday, 8 November:
  • Rice's Theorem (by Rob van Glebbeek, Stanford U.)
  • Unsolvable Problems and Rice's Theorem (by Bob Daley, U. Pittsburgh)
    
  • Formal definitions of Rice's Theorem, the Parameter (s-m-n) Theorem, & Recursion Theorem (by V. Yu. Shavrukov, IT U. Copenhagen)
• Homework 8 (due 15 November)
• For lecture on Friday, 15 November:
  
  •  An interesting analogy for the recursion theorem (by Bob Daley, U. Pittsburgh)
  • Overview: Making computability theory interesting (by Ching-Kuang Shene, Michigan Technological U.)
• Homework 9 (due 22 November)
• Information for Exam 2, including sample exam (22 November)
  
• Homework 10 (due 6 December)
• Information for Final Exam (13 December) and final exam page.

Useful Links:

• Book's webpage