School of Computer Science

Module 05934 (2011)

Module description - Models of Computation

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

Module Title Models of Computation
School School of Computer Science
Module Code 06-05934
Level 2/I
Member of Staff Steven Vickers
Semester Semester 2 - 10 credits

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


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
  • Sessional: 1.5 hr examination (80%), continuous assessment (20%).
  • Supplementary: 1.5 hr examination (100%).
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 Addison-Wesley
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