CSC 8510: Theory of Computability
Spring 2014 (night section)


v  Homework assignments

v  Lecture notes

Meeting on Thursdays, 6:15-9:00 PM,  Mendel Hall G90  

Course Home Page:

Instructor: Dr. G. Japaridze

Teaching Assistant: Ms. Sherin AmbrammadomBasheer

"Introduction to the Theory of Computation" (3rd edition) By Michael Sipser. Cengage Learning, 2013. ISBN 978-1-133-18779-0

Description and goals: This course is about what computers can and cannot do. It approaches this question in a strict mathematical fashion. The goal of the course is to expand your mind and give you conceptual tools for solving theoretical and practical problems.

Topics and Schedule (tentative):

  1. Regular Languages (1 week)
  2. Context-free Languages (1 week)
  3. The Church-Turing Thesis (1 week)
  4. Decidability (1 week)
  5. Reducibility (1 week)
  6. Time Complexity (4 weeks)
  7. Space Complexity (3 weeks)
  8. Advanced topics (2 weeks)

Examination schedule:

  1. Last week before the Spring break
  2. Last week of the semester

Quizzes: Every week. Missed quizzes cannot be made up no matter what the reason was. One quiz of your choice, however, will be automatically forgiven.

Grading: Quizzes --- 20%, Examinations --- 80%.

Presumably, grades will be derived from cumulative scores as follows:



94 or more


87 or more


80 or more


72 or more


63 or more


54 or more


45 or more


less than 45


External links (video lectures):

Ø  The P vs NP Problem [61 min]  by Michael Sipser

Ø  The Church-Turing Thesis: Story and Recent Progress [66 min]  by Yuri Gurevich

Ø  The Mathematics of Alan Turing [51 min] by Angus MacIntyre

Ø  Quantum Computing and the Limits of the Efficiently Computable [70 min] by Scott Aaronson

Ø  A Mathematical Mystery Tour [49 min]

Ø  Quantum Computer [collection]