Studying at York
Theory 3: Computability, Complexity and Logic - COM00027I
- Department: Computer Science
- Credit value: 20 credits
- Credit level: I
- Academic year of delivery: 2024-25
- See module specification for other years: 2023-24
Module summary
Theory 3: Computability, Complexity and Logic
Related modules
Pre-requisite modules
Co-requisite modules
- None
Prohibited combinations
- None
Module will run
| Occurrence | Teaching period |
|---|---|
| A | Semester 1 2024-25 |
Module aims
This module covers computability theory and complexity theory. In particular, students will learn the concepts of semi-decidable and decidable languages, and Turing-computable functions. They will be able to explain the difference between solvable and unsolvable problems and prove unsolvability by reduction. They will understand the time and space complexity of Turing machines, complexity classes such as P, NP, PSpace, NPSpace and NPC, and prove NP-completeness by reduction. The module will also introduce basic concepts and results in propositional logic, predicate logic, and program verification. In particular, students will learn to distinguish between syntax and semantics, and be able to use formal proof systems such as natural deduction. They will understand the limitations of logic in terms of decidability and expressiveness, and how to use a formal calculus such as Hoare logic to specify programs and prove them correct.
Module learning outcomes
-
Use unrestricted grammars and Turing machines to specify semi-decidable languages.
-
Provide examples of unsolvable problems and prove that a problem is unsolvable by reducing a known unsolvable problem to it.
-
Explain the Church-Turing thesis and its significance.
-
Define the classes P and NP, and explain their relation to the class ExpTime.
-
Explain the significance of NP-completeness and provide examples of NP-complete problems.
-
Explain the meaning of formulas in propositional and predicate logic, and translate such formulas into English and vice-versa.
-
Explain the fundamental difference between syntax and semantics.
-
Apply the rules of natural deduction to construct proofs, and determine the truth or falsity of formulas in a given model.
-
Explain the limitations of logic and the relationship between logic and computability.
-
Reason deductively about programs using formalisms such as Hoare logic and weakest preconditions
Indicative assessment
| Task | % of module mark |
|---|---|
| Closed/in-person Exam (Centrally scheduled) | 100 |
Special assessment rules
None
Indicative reassessment
| Task | % of module mark |
|---|---|
| Closed/in-person Exam (Centrally scheduled) | 100 |
Module feedback
Feedback is provided through work in practical sessions, revision classes, and after the final assessment as per normal University guidelines.
Indicative reading
**** Martin, John C., Introduction to Languages and the Theory of Computation (4th ed.), McGraw Hill, 2010
** Rich, Elaine, Automata, Computability and Complexity, Pearson Education, 2008
** Sipser, Michael, Introduction to the Theory of Computation (3rd ed.), South-Western College Publishing, 2012
* Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D., Introduction to Automata Theory, Languages and Computation (3rd ed.), Pearson Education, 2013
* Arora, Sanjeev and Barak, Boaz, Computational Complexity: A Modern Approach, Cambridge University Press, 2009
++ Garey, Michael R. and Johnson, David S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979