CODE 
CPS3239 

TITLE 
Computability and Complexity 

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

ECTS CREDITS 
5 

DEPARTMENT 
Computer Science 

DESCRIPTION 
This studyunit grounds important concepts relating to the theory of computability. The style of the studyunit will be of an expository nature, but will lay the necessary foundations required by more advanced studyunits 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 Nondeterministic 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 CurryHoward 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.
Aims:
• 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), AddisonWesley, 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 http://homepages.inf.ed.ac.uk/wadler/papers/frege/frege.pdf)


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

STUDYUNIT TYPE 
Lecture 

METHOD OF ASSESSMENT 
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 StudyUnit information are complete and uptodate 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 studyunit description above applies to the academic year 2017/8, if studyunit is available during this academic year, and may be subject to change in subsequent years.

23 October 2017
http://www.um.edu.mt/ict/studyunit