Research Interests
- Computability Theory, in particular computability on topological structures
- Domain Theory
- Complexity Theory, in particular Implicit Computational Complexity
- Logic
Central to Theoretical Computer Science - if not to Computer Science generally - is the notion of algorithm. An algorithm for the solution of a problem or the computation of a function is a finite unambiguous instruction for the execution of simple finite operations on a (digital) machine, which after finitely many steps will yield a result for any special case of the given problem class and/or any argument of the given function.
Of course, this is not a precise mathematical definition. The formalisation of the above described intuitive notion of algorithm is one of the greatest intellectual achievements of the last century. The notion was carefully analysed and various formalisms - partly of quite different nature - were proposed. As turned out, all these formalisms result in the same notion of computable function (over the natural numbers or the finite words over some fixed alphabet, respectively). This led to the by now generally accepted thesis that an adequate (mathematically precise) formalisation of the intuitive notion of algorithm has been obtained (Church-Turing Thesis).
Once this step had been done, new question came up:
- What can be done algorithmically, i.e., which problems can be solved and which functions can be computed mechanically?
- Are there any limits?
- Which resources (time, space, ...) are needed at least (at most) in order to solve a given problem or compute a given function?
- Given a program, does it really do what it is supposed to do?
Questions like these are dealt with in Computability Theory, Complexity Theory and Theory of Programming, respectively.
Usually in computability and complexity investigations, functions and problems are considered that are defined on finite data like the natural numbers or finite words over some alphabet. In many areas as logic and graph theory it is sufficient to consider such data sets. In physics and engineering, however, one has to deal with continuous data like real numbers. Already in the very beginning of computability theory people started to think about what it means to compute a real number or a real-valued function. In the last years interest in these questions has much increased. There are plenty of reasons. Of course, one wants to study questions as those listed above in the area of Scientific Computation.
In general, in numerical computations one uses floating-point numbers to approximate real numbers. Since the domain of such numbers that can be used in an actual machine is limited, this leads to rounding errors. Results may be unreliable. Even worse than this: the algebraic structure of the collection of these numbers is much different from the structure of the reals. This means that the usual implementations of the data type of the reals are not sound with respect to the assumed semantics.
A large part of the above mentioned modern research in Theoretical Computer Science can be subsumed under the slogan Computing with Exact Real Numbers. To this end the space of the reals is enlarged by including also partial reals, i.e. objects which are used for approximation - mostly closed rational intervals - and which are the intermediate results during a computation. Programming languages are designed that work with the extended real number data type. By this way sound implementations are obtained. As a consequence formal correctness proofs can be given. Normally, first writing a program and then deriving its correctness is a tedious task. A more promising way is to first prove a statement of the form (∀ x)(∃ y)R(x,y) and then try to extract a program that computes a function f such that (∀ x)R(x,f(x)). This insight has led to a huge research programme that aims at reworking large parts of analytical mathematics so that its algorithmic and/or constructive content becomes more visible.
In mathematical programming language semantics one preferably deals with a structure called domain and generalisations hereof. Domains introduced by Dana Scott are lattice-like and come with a canonical topology that reflects essential properties of computations. Topology and order structure determine each other. Usually the order is interpreted as the relation ``is more defined than'' or ``contains more information than''. As a consequence, in the language of this structure only qualitative approximation statements can be made. In analytical mathematics, on the other hand, we are used to deal with a metric structure and to make quantitative approximation statements. Fortunately, it has turned out that domains allow weak notions of distance. This has led to several new questions.
Investigations in complexity theory usually are based on a very simple machine model, the Turing machine. The use of time or space of a computation on this machine is studied. Having these results in mind the programmer can choose the algorithm that suites best his needs. However, the structure of Turing programs corresponds only badly to the structure of modern programming languages. He would need results allowing to estimate the consumption of resources by considering only the structure of the program, in particular the control structures herein. This is the aim of a new branch of complexity theory: Implicit Computational Complexity.