# Module 06-35393 (2022)

## Theories of Computation

## Level 1/C

David Parker Paul Levy Mian Muhammad Hamayun Sonia Marin | Semester 2 | 20 credits |

### Outline

Computers have been used to solve an astonishing range of different problems, but this does not mean that they can be used to solve all possible problems: some cannot be solved efficiently, and some cannot be solved at all. In this module, we will introduce a set of principles and techniques for formalising computation and computability to understand what problems can be solved, how efficiently they can be solved, and what problems cannot be solved. We will develop mathematical models of computations using ideas such as sutomata theory (including Turing machines), of formal languages using ideas such as regular expressions and grammars, and will conclude by considering the notions of non-computability and complexity.

### Learning Outcomes

On successful completion of this module, the student should be able to:

- Explain and apply mathematical models of computations
- Explain and apply concepts from automata theory, formal language theory, computability theory and complexity theory
- Describe and use the connection between finite automata and regular language
- Explain non-computability and undecidability issues

### Co-requisites

- 06-35324 - Mathematical and Logical Foundations of Computer Science

### Assessment

- Main Assessments: Continuous assessment (20%) and an examination (80%)
- Supplementary Assessments: Examination (100%)

### Programmes containing this module

- BSc Artificial Intelligence & Computer Science [0144]
- BSc Artificial Intelligence & Computer Science with an Industrial Year [9502]
- BSc Artificial Intelligence & Computer Science with Study Abroad [452B]
- BSc Computer Science [4436]
- BSc Computer Science with an Industrial Year [9499]
- BSc Computer Science with Digital Technology Partnership (PwC) [610C]
- BSc Computer Science with Digital Technology Partnership (Vodafone) [893C]
- BSc Computer Science with Study Abroad [5571]
- BSc Mathematics and Computer Science [5196]
- BSc Mathematics and Computer Science with an Industrial Year [9495]
- MEng Computer Science/Software Engineering [4754]
- MEng Computer Science/Software Engineering with an Industrial Year [9501]
- MSci Computer Science [4443]
- MSci Computer Science with an Industrial Year [9509]
- MSci Computer Science with Study Abroad [5576]
- MSci Mathematics and Computer Science [5197]
- MSci Mathematics and Computer Science with an Industrial Year [9496]