Mathematical Informatics Seminar

We cordially invite you to the following talk by the visiting scholar Prof. Dr. Dieter Spreen of Siegen, which will be given on


The continuity problem in computability theory

After the discovery of the paradoxes in Cantor's set theory, mathematics was in a deep foundational crisis. Various suggestions of how to get out of this situation have been made. The more radical among them required that it is no longer sufficient to derive the existence of an object by indirect reasoning, but to present a concrete construction of the object under consideration. Here, the problem is what is meant by a construction. Markov replaced ‚construction‘ by ‚algorithm‘: only those objects should be considered that are generated by an algorithm.

This should in particular be true for functions. So, in the Markov school, also known as Russian Constructivism, a function is given by an algorithm that takes as input an algorithm generating the object the function is applied to, and delivers as output an algorithm generating the function value.

This is a rather restrictive concept. When dealing with functions on the real numbers, e.g., we are interested in their computability, but we do not want to restrict the function to only computable real numbers as arguments. Such functions turn out to be computable, if they are continuous with a computable modulus of continuity.

In several cases it turned out that Markov computable functions can be extended to computable functions in the sense just mentioned. However, it is known that this is not true in general. The problem in which situations Markov computable functions can be extended to computable functions is known as the continuity problem. It will be discussed in this talk.