| CODE | CPS3239 | ||||||
| TITLE | Computability and Complexity | ||||||
| UM LEVEL | 03 - Years 2, 3, 4 in Modular Undergraduate Course | ||||||
| MQF LEVEL | 6 | ||||||
| ECTS CREDITS | 5 | ||||||
| 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. 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), 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 http://homepages.inf.ed.ac.uk/wadler/papers/frege/frege.pdf) |
||||||
| 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. |
||||||
| STUDY-UNIT TYPE | Lecture | ||||||
| METHOD OF ASSESSMENT |
|
||||||
| LECTURER/S | Adrian Francalanza (Co-ord.) |
||||||
|
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 description above applies to study-units available during the academic year 2024/5. It may be subject to change in subsequent years. |
|||||||