School of Computer Science

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.


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


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

Detailed Syllabus

  1. Finite automata (4 hrs)
    • Finite automata and regular languages
    • Nondeterminism
    • Limitations of finite automata
  2. Formal languages (2 hrs)
    • Grammars
    • Pushdown automata
  3. Limits of computation (4 hrs)
    • The Halting Problem
    • Reducibility
  4. Turing machines (4 hrs)
    • The basic model
    • Extensions and their equivalence with the basic model
    • Church's Thesis
  5. Complexity Theory (4 hrs)
    • Complexity of Turing machine programs
    • The class P
    • The class NP
    • NP-complete problems
  6. Formalising functional programming (4 hrs)
    • Rewriting as a computational paradigm
    • Lambda calculus
    • Typed lambda calculi

Programmes containing this module