Computability and Complexity 2002

FS2: Computability and Complexity

Course Tutors

Course Description

The goal of this course is to explain and illustrate one of the most important and fundamental facets of the world of computing --- its inherent limitations. We shall see that there are problems for which no algorithmic solution will ever exist, and realizing the existence of such inherently unsolvable problems has been one of the main achievements of 20th century mathematics. Roughly speaking, the subject matter of the theory of computability is the precise definition of the informal concept of algorithm, and the characterization of those problems that can (or, perhaps more intriguingly, cannot) conceivably be solved by means of algorithms. In the process of developing such a theory, to which the bulk of the course will be devoted, we shall touch upon topics such as: The last part of the course will be devoted to a brief introduction to the theory of computational complexity. In a nutshell, one may say that, whereas computability theory is concerned with the class of problems that can or cannot be solved algorithmically, complexity theory aims at characterizing the problems for which efficient algorithmic solutions can conceivably be found. The key concept that we shall touch upon in this part of the course is that of NP-complete problem.

As an alternative, excellent description of this course I strongly recommend the preface of Computers Ltd.: What They Really Can't Do (Oxford University Press, to appear) by David Harel.


The main textbook for the course is Introduction to the Theory of Computation by Michael Sipser. The author maintains a list of errata for the current edition of this book. Some of the lectures will be based on material from John C. Martin's book Introduction to Languages and the Theory of Computation, McGraw-Hill. (Copies of the relevant pages will be available for photocopying when necessary.)

Other excellent references are:

and many more.

As supplementary reading on the science of computing as a whole, I also strongly recommend the book Algorithmics: The Spirit of Computing by David Harel. Of special relevance to this course are chapters 6-9 ibidem.

Course Material

Links Related to Alan Turing and his Machines

Links to Alan Turing

Links to Turing Machine Simulators

There are other websites with information on (downloadable) Turing machine simulators.
These are maintained by:

Look also here for a nice Turing Machine simulator written in Java (and documented in German). (Many thanks to Thomas Rask Thomsen for providing this one!)

Other Links of Course Related Interest

Some people whose work has had a great impact on the field of Computability Theory: Other links that you might want to explore are:

Other Models of Computation

Recently there has been a great interest in alternative models of computation. Prominent amongst these are quantum computing and DNA computing. Some information on these exciting models of computation may be obtained from the following links:
This page will be actively modified over the autumn term 1999, and is currently undergoing heavy restructuring. You are invited to check it regularly during the autumn term. The page is dormant in the spring term.
Luca Aceto, Department of Mathematics and Computer Science, Aalborg University.
Last modified: Fri Dec 3 09:27:59 MET 1999