Accessibility statement

Theory 3: Computability, Complexity and Logic - COM00027I

« Back to module search

  • Department: Computer Science
  • Module co-ordinator: Dr. Detlef Plump
  • 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

  1. Use unrestricted grammars and Turing machines to specify semi-decidable languages.

  2. Provide examples of unsolvable problems and prove that a problem is unsolvable by reducing a known unsolvable problem to it.

  3. Explain the Church-Turing thesis and its significance.

  4. Define the classes P and NP, and explain their relation to the class ExpTime.

  5. Explain the significance of NP-completeness and provide examples of NP-complete problems.

  6. Explain the meaning of formulas in propositional and predicate logic, and translate such formulas into English and vice-versa.

  7. Explain the fundamental difference between syntax and semantics.

  8. Apply the rules of natural deduction to construct proofs, and determine the truth or falsity of formulas in a given model.

  9. Explain the limitations of logic and the relationship between logic and computability.

  10. Reason deductively about programs using formalisms such as Hoare logic and weakest preconditions

Assessment

Task Length % of module mark
Online Exam -less than 24hrs (Centrally scheduled)
Theory 3 Exam		 4 hours 100

Special assessment rules

None

Reassessment

Task Length % of module mark
Online Exam -less than 24hrs (Centrally scheduled)
Theory 3 Exam		 4 hours 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


The information on this page is indicative of the module that is currently on offer. The University is constantly exploring ways to enhance and improve its degree programmes and therefore reserves the right to make variations to the content and method of delivery of modules, and to discontinue modules, if such action is reasonably considered to be necessary by the University. Where appropriate, the University will notify and consult with affected students in advance about any changes that are required in line with the University's policy on the Approval of Modifications to Existing Taught Programmes of Study.