Undergraduate Course: Computability and Intractability (INFR09008)
Course Outline
| School | School of Informatics |
College | College of Science and Engineering |
| Course type | Standard |
Availability | Available to all students |
| Credit level (Normal year taken) | SCQF Level 9 (Year 3 Undergraduate) |
Credits | 10 |
| Home subject area | Informatics |
Other subject area | None |
| Course website |
http://www.inf.ed.ac.uk/teaching/courses/ci |
Taught in Gaelic? | No |
| Course description | The course centres around the so-called Church-Turing Thesis which proposes that each one of a variety of different formal systems adequately captures the intuitive concept of (effective) computability. This thesis implies that by studying any one of these systems, for example Turing machines, we can learn about the inherent theoretical limitations of computers. If a problem cannot be solved by a Turing machine, then there is no computable solution to it at all.
Not all the computational problems which can be solved in principle can be solved in practice: the computational resources required (time or space) may be prohibitive. This observation motivates the study of resource-bounded computation. Having accepted an extended version of the Church-Turing thesis (that the computationally tractable problems are those which can be efficiently solved by a Turing machine) we are led inevitably to conclude the existence of natural problems which can be solved in principle but not within any reasonable resource bound.
The fundamental concepts and techniques encountered in this course resonate around the whole of Computer Science and indeed beyond: effective procedures and decidability, simulation methods, machine encodings and universality, diagonalization arguments, and reductions between problems. |
Entry Requirements (not applicable to Visiting Students)
| Pre-requisites |
|
Co-requisites | |
| Prohibited Combinations | |
Other requirements | Successful completion of Year 2 of an Informatics Single or Combined Degree, or equivalent by permission of the School. This course also assumes that students are comfortable with mathematical notation, definitions, and proofs using basic techniques including induction.
|
| Additional Costs | None |
Information for Visiting Students
| Pre-requisites | None |
| Displayed in Visiting Students Prospectus? | Yes |
Course Delivery Information
| Not being delivered |
Summary of Intended Learning Outcomes
1 - Discuss the fundamental nature of computation as a process (Turing's Thesis).
2 - Discuss the limits to computing both in absolute terms (unsolvable problems) and practical terms (intractable problems).
3 - Distinguish different types of languages (recursively enumerable, recursive etc.).
4 - Demonstrate the solvability of a given problem both in informal as well as formal terms (use of Turing machines).
5 - Demonstrate the unsolvability of a given problem both in informal as well as formal terms (use of reductions).
6 - Discuss the classification of solvable problems into tractable versus intractable ones (P versus NP).
7 - Judge when a problem is likely to be intractable.
8 - Discuss the notion of polynomial time reduction and its relevance to classifying the relative complexity of problems.
9 - Demonstrate the likely intractability of a given problem by relating it to other known problems (use of polynomial time reductions). |
Assessment Information
Written Examination 75
Assessed Assignments 25
Oral Presentations 0
Assessment
via Written Examination.
If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year. |
Special Arrangements
| None |
Additional Information
| Academic description |
Not entered |
| Syllabus |
* Finite state machines: Brief reminder of a model which does not encompass the intuitive notion of effective procedure.
* Turing machines: Definition; some programming techniques and example machines; variants of the Turing machine and their equivalence.
* The Church-Turing Thesis: Empirical evidence for the Thesis; equivalence of Turing machines to other models of computation, both simpler (two-register machines) and more complex (models of computation which are akin to real computers). Overview of the basic ideas; proofs are supplied in appendices to the course notes.
* Universal machines: Encoding Turing machines; a universal Turing machine.
* Decidability and partial decidability: The Halting Problem; reductions between problems.
* Nondeterministic Turing machines: Definition and equivalence to deterministic machines.
* Resource bounded computation: The class P and its interpretation as the class of computationally tractable decision problems; the class NP and its interpretation as the class of search problems with efficiently verifiable solutions.
* NP-completeness: Cook's theorem; examples of problems which are complete for NP.
* Connections with Logic: Brief introduction to first order and second order logic and discussion of how the ideas relate to complexity classes, mainly the NP-complete problems.
Relevant QAA Computing Curriculum Sections: Theoretical Computing |
| Transferable skills |
Not entered |
| Reading list |
* C.H. Papadimitriou, Computational Complexity, Addison-Wesley 1994. Useful for those who intend to progress to the CS4 Computational Complexity module. Includes good discussion of logic and its connections to computability. An excellent introduction to most of the concerns of modern day complexity.
* J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to Automata Theory, Languages and Computation, 3rd edition, Addison-Wesley 2007. Contains material relevant to this module. Also proves lower bounds for various problems (e.g., ones connected with regular expressions).
* M. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall 1972. An excellent book and strong on motivation. Unfortunately, it is now only available as an expensive hardback. There are some copies in the reserve section of the JCMB library.
* M.R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979. A classic book, strong on motivation covering the latter parts of the module. A must for those who want to know more as well as the origins of many of the results and ideas. |
| Study Abroad |
Not entered |
| Study Pattern |
Lectures 20
Tutorials 8
Timetabled Laboratories 0
Non-timetabled assessed assignments 0
Private Study/Other 72
Total 100 |
| Keywords | Not entered |
Contacts
| Course organiser | Mr Vijayanand Nagarajan
Tel: (0131 6)51 3440
Email: vijay.nagarajan@ed.ac.uk |
Course secretary | Miss Claire Edminson
Tel: (0131 6)51 7607
Email: C.Edminson@ed.ac.uk |
|
|
University Homepage