Module Title 
Models of Computation 
School 
School of Computer Science 
Module Code 
0605934 
Level 
2/I 
Member of Staff 
Steven Vickers

Semester 
Semester 2  10 credits

Delivery 
11 twohour lectures, 11 onehour exercise sessions, 2 onehour
review lectures

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 noncomputability and nondecidability 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

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

Texts 
Title  Author  Publisher 
An Introduction to Functional Programming Through Lambda Calculus 
Greg Michaelson 
Dover Publications 
Automata and Computability 
D. Kozen 
Springer Verlag 
Computability and Complexity: From a Programming Perspective 
N. Jones 
MIT Press 
Introduction to Automata Theory, Languages, and Computation 
J. E. Hopcroft, J. D. Ullman 
AddisonWesley 
Introduction to the Theory of Computation 
M. Sipser 
PVS Publishing Company 
Models of Computation: Exploring the Power of Computing 
Savage 
Addison Wesley 
Module notes will be provided 


Theory of Computation; Formal Languages, Automata, and Complexity 
Brookshear 
Cummings 
