LecturerVasco BrattkaDepartment of Mathematics & Applied Mathematics University of Cape Town 
Course DescriptionComputability and complexity theory are two basic areas of mathematics and computer science and the main goal of these disciplines is to understand up to which extend problems can be solved algorithmically. While algorithms have been implicitly studied since ancient times (Euclid's algorithm is an example), it is only since the seminal work of Turing, Gödel and others that there is a precise notion of an algorithm. Applying this precise notion it turns out that certain problems are not solvable algorithmically in principle (for instance, there is no general method to decide whether two programs do the same job). Other problems turn out to be unsolvable for more practical reasons (there is no known feasible method to check whether a propositional formula is satisfiable). It is computability and complexity theory which studies the underlying mathematical structures behind such problems.During this course we are going to address, among others, the following topics:

"Universal Turing Machine"
© 2003 Jin Wicked, USA. 
© 20042007 Vasco Brattka