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 socalled ChurchTuring 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 resourcebounded computation. Having accepted an extended version of the ChurchTuring 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)
Prerequisites 

Corequisites  
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
Prerequisites  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 ChurchTuring Thesis: Empirical evidence for the Thesis; equivalence of Turing machines to other models of computation, both simpler (tworegister 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.
* NPcompleteness: 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 NPcomplete problems.
Relevant QAA Computing Curriculum Sections: Theoretical Computing 
Transferable skills 
Not entered 
Reading list 
* C.H. Papadimitriou, Computational Complexity, AddisonWesley 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, AddisonWesley 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, PrenticeHall 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 NPCompleteness, 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
Nontimetabled 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 

