Skip to Content


Last modified: 25 May 2018 11:16

Course Overview

This course provides a basic-level introduction to computability via the notion of a Turing Machine. Some familiarity with imperative programming (e.g., in JAVA) and with the basics of set theory (e.g., the notion of a bijection) is assumed. The Functional language Haskell (familiar from earlier courses, including CS2013) is used to explore the concepts of infinity, recognisability and decidability, which are crucial to computability.

Course Details

Study Type Undergraduate Level 3
Session Second Sub Session Credit Points 15 credits (7.5 ECTS credits)
Campus None. Sustained Study No
  • Dr Adam Wyner
  • Professor Kees Van Deemter

Qualification Prerequisites

  • Either Programme Level 3 or Programme Level 4

What courses & programmes must have been taken before this course?

  • CS2013 Mathematics for Computing Science (Passed)
  • Any Undergraduate Programme (Studied)

What other courses must be taken with this course?


What courses cannot be taken with this course?


Are there a limited number of places available?


Course Description

  • Imperative languages and their associated automata: Regular languages and Finite state automata (FSA), Context-free languages and Pushdown Automata (PDA), Non-context-free languages and linear-bounded automata (LBA), Turing Machines (TM), nondeterministic Turing Machines.
  • Functional languages: Haskell idioms, Haskell polymorphic types, recursion, Haskell higher-order functions, lazy evaluation, infinite sets.
  • Chomsky hierarchy and computability: Turing decidability, Turing recognisability, injections, surjections and bijections, Cantor's diagonal argument, the halting problem, the Church-Turing Thesis.

Further Information & Notes

Assistive technologies may be required for any student who is unable to use a standard keyboard/mouse/computer monitor. Any students wishing to discuss this further should contact the School Disability Co-ordinator.

Degree Programmes for which this Course is Prescribed

  • BSc Computing Science
  • MA Computing
  • MSci Computing Science w Ind'l Placement
  • MSci Computing with Industrial Placement

Contact Teaching Time

72 hours

This is the total time spent in lectures, tutorials and other class teaching.

Teaching Breakdown


1st Attempt: 1 two-hour written examination (75%); continuous assessment (25%).

Resit: 1 two-hour written examination (75%); continuous assessment mark carried forwards (25%).

Only the marks obtained on first sitting can be used for Honours classification.

Formative Assessment

During lectures, the Personal Response System and/or other ways of student interaction will be used for formative assessment.


Formative feedback for in-course assessments will be provided in written form. Additionally, formative feedback on performance will be provided informally during practical sessions.

Compatibility Mode

We have detected that you are have compatibility mode enabled or are using an old version of Internet Explorer. You either need to switch off compatibility mode for this site or upgrade your browser.