# Module 06-05934 (2012)

## Models of Computation

## Level 2/I

Paul Levy | Semester 2 | 10 credits |

Co-ordinator: Paul Levy

Reviewer: Martin Escardo

The Module Description is a strict subset of this Syllabus Page.

### Aims

The aims of this module are to:

- introduce a variety of formal models of computation
- explain the significance of formal models from a practical and a foundational point of view
- make familiar with the fundamental results in the theory of computation
- explain the way in which formalisations are used to address real-life computational problems

### Learning Outcomes

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

- explain the basics of automata theory, formal language theory, computability theory, complexity theory and lambda calculus
- explain non-computability and non-decidability issues
- describe and use the connection between automata and languages
- explain and use lambda calculus as a theory of functional programming
- explain the connection between theory and applications

### Teaching methods

11 two-hour lectures, 11 one-hour exercise sessions, 2 one-hour review lectures

### Assessment

- Sessional: 1.5 hr examination (80%), continuous assessment (20%).
- Supplementary: 1.5 hr examination (100%).

### Detailed Syllabus

- Finite automata (4 hrs)
- Finite automata and regular languages
- Nondeterminism
- Limitations of finite automata

- Formal languages (2 hrs)
- Grammars
- Pushdown automata

- Limits of computation (4 hrs)
- The Halting Problem
- Reducibility

- Turing machines (4 hrs)
- The basic model
- Extensions and their equivalence with the basic model
- Church's Thesis

- Complexity Theory (4 hrs)
- Complexity of Turing machine programs
- The class P
- The class NP
- NP-complete problems

- Formalising functional programming (4 hrs)
- Rewriting as a computational paradigm
- Lambda calculus
- Typed lambda calculi

### Programmes containing this module

- BEng Computer Science/Software Engineering [4753]
- BEng Computer Science/Software Engineering with an Industrial Year [9500]
- BSc Artificial Intelligence & Computer Science [0144]
- BSc Artificial Intelligence & Computer Science with an Industrial Year [9502]
- BSc Computer Science [4436]
- BSc Computer Science with an Industrial Year [9499]
- BSc Computer Science with Business Management [5914]
- BSc Computer Science with Business Management with an Industrial Year [9503]
- BSc Mathematics and Computer Science [5196]
- BSc Mathematics and Computer Science with an Industrial Year [9495]
- BSc Pure Mathematics and Computer Science [5249]
- BSc Pure Mathematics and Computer Science with an Industrial Year [9497]
- MEng Computer Science/Software Engineering [4754]
- MEng Computer Science/Software Engineering with an Industrial Year [9501]
- MSci Mathematics and Computer Science [5197]
- MSci Mathematics and Computer Science with an Industrial Year [9496]
- MSci Pure Mathematics and Computer Science [5256]
- MSci Pure Mathematics and Computer Science with an Industrial Year [9498]