CSC 8510: Theory of Computability
Spring 2024
Meeting 6:15-9:00 PM Wednesdays in Mendel G86 (Section 1) and Thursdays in Mendel G88 (Section 2)
Course Home Page: http://www.csc.villanova.edu/~japaridz/8510/
Instructor: Dr. G. Japaridze
· Office hours: Wednesdays and Thursdays 5:10-6:10 PM in Mendel 165A. Additional time may be arranged by appointment.
Teaching Assistant: Mr Giorgi Tsartsidze
Textbook: "Introduction to the Theory of Computation" (3rd edition) By Michael Sipser. Cengage Learning, 2013. ISBN 978-128-540-1065 (ebook), 978-113-318-7790 (hardcover)
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):
Grading: Your grade will be based on quizzes (20%) and one final exam (80%). However, if your quiz average is better than the examination score, the two weights will be switched in your favor: quizzes 80% and final 20%. A student may be awarded some extra points for being highly active in answering questions asked by the instructor and participating in discussions.
Quizzes will be given every week at the beginning of class. A quiz will typically have two questions based on the latest homework. Often, 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. The questions on the final examination will be similar, but otherwise the exam will be comprehensive (all topics covered during the semester).
The following scale will be used when deriving your letter grades from your numeric scores: (A) 94+; (A-) 87+; (B+) 80+; (B) 73+; (B-) 64+; (C+) 55+; (C) 45+.
Office of Disabilities and Learning Support Services: It
is the policy of Villanova to make reasonable academic accommodations for
qualified individuals with disabilities. You must present verification and
register with the Learning Support Office by contacting 610-519-5176 or at learning.support.services@villanova.edu
or for physical access or temporary disabling conditions,
please contact the Office of Disability Services at 610-519-4095 or email Stephen.mcwilliams@villanova.edu
Registration is needed in order to receive accommodations.
Academic Integrity: All students are expected to uphold Villanova’s Academic Integrity Policy and Code. Any incident of academic dishonesty will be reported to the Dean of the College of Liberal Arts and Sciences for disciplinary action. For the College’s statement on Academic Integrity, you should consult the Enchiridion. You may view the university’s Academic Integrity Policy and Code, as well as other useful information related to writing papers, at the Academic Integrity Gateway web site: http://library.villanova.edu/Help/AcademicIntegrity
Absences for Religious Holidays: Villanova University makes every reasonable effort to allow members of the community to observe their religious holidays, consistent with the University’s obligations, responsibilities, and policies. Students who expect to miss a class or assignment due to the observance of a religious holiday should discuss the matter with their professors as soon as possible, normally at least two weeks in advance. Absence from classes or examinations for religious reasons does not relieve students from responsibility for any part of the course work required during the absence. https://www1.villanova.edu/villanova/provost/resources/student/policies/religious holidays.html
Links to related videos:
Proof That Computers Can’t Do Everything (The Halting Problem) [8 min]
The importance of the Universal Turing machine [4 min]
P vs. NP and the Computational Complexity Zoo [10 min]
P vs. NP – The Biggest Unsolved Problem in Computer Science [15 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]