University of Malta

Study-Unit Description
UOM Main Page
Apply - Admissions 2016
Campus Map button


TITLE Computability and Complexity

LEVEL 03 - Years 2, 3, 4 in Modular Undergraduate Course


DEPARTMENT Computer Science

DESCRIPTION This study-unit grounds important concepts relating to the theory of computability. The style of the study-unit will be of an expository nature, but will lay the necessary foundations required by more advanced study-units such as Principles of Programming languages, where a more rigorous treatment is taken.

In the first section we explore Computability and the limits of computation. Most of the concepts are expressed using Turing Machines (TMs). We present TMs as language accepting machines, define computation as an algorithm over these TMs, consider variants of TMs (k tape, TM composition) and show that they can be expressed in terms of a single tape TM. We also introduce the concept of a Universal Turing machines, emulating other TMs, and culminate with the Halting problem.

The second part of the unit explores alternative models of computation and informally shows that they posses the same expressive power as TMs. We introduce the Lambda Calculus, invite the student to familiarise with this computational model through programming examples, and then equate their expressive power to that of TMs by encoding one computational model in terms of the other.

The last part of the unit deals with tractability and complexity and the relationship between computation and formal proofs. TMs are used as a computation formalism to describe the Polynomial time (P) and Non-deterministic Polynomial time (NP) class of problems, introduce the concept of NP completeness and to give an appreciation of the classic open problem of whether P=NP. Furthermore, the course covers the notion of reducibility and how this induces an ordering on the set of problems. The lambda calculus is used to introduce the Curry-Howard correspondence between proofs (in a natural deduction proof system) and program classification through type checking. unit deals with bringing everything together: It shows the correspondence between Chomsky’s language hierarchy and the different models of computation. It also highlights the relationship between formal logic proofs and computation, presenting a coherent story which ties in all the formal elements covered over the duration of their degree.


• Induct the student into the concept of computability and its limits;
• Provide the student with a theoretical understanding of different computational models and how these do not yield additional expressive power in terms of what can be computed;
• Expose the student to the complexity limits of certain classes of computational problems.#

Learning Outcomes:

• Formulate algorithmic solutions in terms of different computational models;
• Reason formally about these algorithmic descriptions in terms of the formal semantics of computational model used;
• Use proof techniques such as diagonalisation arguments to compare set cardinalities;
• Classify algorithmic problems according to a taxonomy complexity classes.

Main Text/s and any supplementary readings:

• Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, ISBN 053494728X, 1997
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (second edition), Addison-Wesley, ISBN 0201441241, 2001
• Chris Hankin, An Introduction to Lambda Calculi for Computer Scientists, College Publications 2004, ISBN 0954300653
• Philip Wadler, Proofs are Programs: 19th Century Logic and 21st Century Computing, 2000, (available at

ADDITIONAL NOTES Students taking this study-unit are assumed to have knowledge of the material covered in the following study-units:
- CPS2005;
- CSA1017 or ICS1018;
- ICS2210.


Assessment Component/s Resit Availability Weighting
Examination (3 Hours) Yes 100%

LECTURER/S Christian Colombo
Adrian Francalanza

The University makes every effort to ensure that the published Courses Plans, Programmes of Study and Study-Unit information are complete and up-to-date at the time of publication. The University reserves the right to make changes in case errors are detected after publication.
The availability of optional units may be subject to timetabling constraints.
Units not attracting a sufficient number of registrations may be withdrawn without notice.
It should be noted that all the information in the study-unit description above applies to the academic year 2017/8, if study-unit is available during this academic year, and may be subject to change in subsequent years.
Study-unit Registration Forms 2017/8


For Undergraduate (Day) and Postgraduate students.


Academic Advisors 2017/8


Academic Advisors for ICT 1st year students (Intake 2017/8), NOW available

Faculty of ICT Timetables


ICT Timetables are available from Here.

Health and Safety Regulations for Labs Form

The Faculty of ICT Health and Safety Regulations for Laboratories form can be found here



Log In back to UoM Homepage