Accessibility statement

# Theory 3: Computability, Complexity and Logic - COM00027I

« Back to module search

• 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

• None

• 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

## Indicative assessment

Closed/in-person Exam (Centrally scheduled) 50
Closed/in-person Exam (Centrally scheduled) 50

None

### Indicative reassessment

Closed/in-person Exam (Centrally scheduled) 50
Closed/in-person Exam (Centrally scheduled) 50

## Module feedback

Feedback is provided through work in practical sessions, revision classes, and after the final assessment as per normal University guidelines.

**** 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 constantly explores 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. In some instances it may be appropriate for the University to notify and consult with affected students about module changes in accordance with the University's policy on the Approval of Modifications to Existing Taught Programmes of Study.