| CODE | CSA3219 | ||||||
| TITLE | Computability and Complexity | ||||||
| UM LEVEL | 03 - Years 2, 3, 4 in Modular Undergraduate Course | ||||||
| MQF LEVEL | Not Applicable | ||||||
| ECTS CREDITS | 6 | ||||||
| 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 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. 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). |
||||||
| RULES/CONDITIONS | Before TAKING THIS UNIT YOU ARE ADVISED TO TAKE ICS2210 Before TAKING THIS UNIT YOU MUST TAKE CPS2005 AND TAKE CSA1017 |
||||||
| ADDITIONAL NOTES | Attendance is not obligatory. | ||||||
| STUDY-UNIT TYPE | Lecture | ||||||
| METHOD OF ASSESSMENT |
|
||||||
| 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 description above applies to study-units available during the academic year 2023/4. It may be subject to change in subsequent years. |
|||||||