# Module 06-05934 (2010)

## Models of Computation

## Level 2/I

Steven Vickers | Semester 2 | 10 credits |

Co-ordinator: Steven Vickers

Reviewer: Volker Sorge

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]
- BSc Computer Science [4436]
- MEng Computer Science/Software Engineering [4754]
- MSc Computer Science [0008]
- MSc Internet Software Systems [5742]