| CODE | CPS3240 | ||||||||
| TITLE | Computability | ||||||||
| 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. It also shows the correspondence between Chomsky鈥檚 language hierarchy and the different models of computation. We then introduce the concept of a Universal Turing machines, emulating other TMs, and culminate with the Halting problem. This allows us to reason about the decidability of certain problems via techniques such as reducibility. 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 lambda calculus is also used as a basis to present the Curry-Howard correspondence between proofs (in a natural deduction proof system) and program classification through type checking. Study-unit Aims: 鈥� Induct the student into the concept of computability and its limits; 鈥� Provide a theoretical understanding of different computational models and how they affect algorithm design; 鈥� Provide a theoretical understanding of how different computational models do not yield additional expressive power in terms of what can be computed. Learning Outcomes: 1. Knowledge & Understanding By the end of the study-unit the student will be able to: 鈥� Outline algorithmic solutions expressed in different computational models. 鈥� 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. 2. Skills By the end of the study-unit the student will be able to: 鈥� Asses the best paradigm to use to develop certain algorithms; 鈥� Use proof techniques such as diagonalisation arguments to compare set cardinalities; 鈥� Asses better whether an algorithm exists to solve certain problems. 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 | Pre-Requisite Study-units: CPS2005, CPS2001, ICT1018, ICS2210, CPS2000 | ||||||||
| 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 2025/6. It may be subject to change in subsequent years. |
|||||||||