Computability Theory

Beginning: October 14 1999

Room: BA 9908

A number of RISC-lectures deal with algorithms for specific problems like sorting, polyomial factorization etc. Computability theory deals with the concept of algorithm in a mathematically precise fashion, the class of algorithmically computable functions, and with the related classes of decidable and of recursively enumerable sets. So it provides a rigorous mathematical basis for programming, similarly as logic provides a basis for mathematical reasoning. Such a systematic approach is necessary in particular to prove negative results: certain problems can not be solved algorithmically, even in principle.