**CSC 8510: Theory of
Computability**** **

**Fall
2016 (Tuesday evening section)**

NOTE: This page should be viewed with
Internet Explorer. Other browsers may fail to display things properly.

**Meeting** on Thursdays, 6:15-9:00 PM, J.Barry Hall 202B

**Course Home Page:** http://www.csc.villanova.edu/~japaridz/8510/

**Instructor:** Dr. G. Japaridze

**Office:**MSC 165A**Email:**giorgi.japaridze@villanova.edu**Office hours:**Tuesdays 4:30-5:30 PM and Wednesdays 1:45-2:45 PM

**Teaching Assistant:** Ms. NahiniVenkantaKrishnaKumari
Palem

**Office:**Mendel 158**Email:**__npalem@villanova.edu__**Office hours:**Not held

**Textbook:**

*"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):

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

**Grading:** Your grade will be based on the quizzes. They will
be given every week at the beginning of the class. A quiz will typically have two
questions: one from the latest homework assignment, and one from some earlier
homework assignment. Occasionally, however, questions may be asked that are not
exactly on the list of homework problems yet are similar or closely related to
the latter; if you have done homework with understanding (as opposed to
memorization), answering such
questions should not be a problem.

External links (video lectures):

Ø
P vs. NP and the
Computational Complexity Zoo [10 min]

Ø
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]