# Module 06-05934 (2016)

## Models of Computation

## Level 2/I

Paul Levy | Semester 2 | 10 credits |

Co-ordinator: Paul Levy

Reviewer: Achim Jung

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

### Outline

The module will introduce various automata theoretic models of computation and discuss their practical and theoretical significance. Finite automata, grammars and stack automata and Turing machines will be introduced. The fundamental ideas of (non-)computability and complexity will be presented. There will also be a section on the Lambda Calculus and its connection with Functional Programming.

### 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

### Restrictions

None

### Pre-requisites

- 06-28344 - Elements of Functional Computing
- 06-20415 - Introduction to Mathematics for Computer Science

### Teaching methods

11 two-hour lectures, 11 one-hour exercise sessions, 1 one-hour revision lecture

Contact Hours: 34

### Assessment

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

Supplementary (where allowed): 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

- 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 Study Abroad [5571]
- BSc Mathematics and Computer Science [5196]
- BSc Mathematics and Computer Science with an Industrial Year [9495]
- BSc Year in Computer Science [5955]
- 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]