CSC 8510: Theory of Computability
Fall 2014


v Homework assignments

v Lecture notes

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

Course Home Page:

Instructor: Dr. G. Japaridze

Teaching Assistant: Ms. Description: Description: Description: ThathamChetty

"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 Fall break
  2. Last week of the semester

Grading: Your grade will be based on the quizzes. They will be given every Thursday.  Missed quizzes cannot be made up. One quiz with the lowest grade, however, will be automatically dropped.

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]