WP1 — Foundations

Research objectives.

(I) to study the relationship between the two central approaches to computing with infinite data, TTE and Markov computability, in more depth, and in particular, to better understand Markov computability in structural terms;

(II) to extend the way algorithmic difficulty is measured to spaces that have become important to computer science.


Objective 1-I: In case all elements of a given space are such that its finite approximations can effectively be generated, each element can be represented in a finite way, namely by the program computing the stream of finite approximations. Computations then only deal with finite objects: they transform generator programs for the input into ones for the output. This approach is due to Markov and is the basis of Russian Constructivism.

The comparison of Markov and type-two computability has been the topic of intensive research. In particular, it is now rather well understood for which spaces both computation models are equivalent and for which spaces they are not. While TTE can be understood in topological terms, Markov computability fails to have such a simple interpretation. A presentation of Markov computability in structural terms promises to greatly advance our understanding with a view to incorporating results from Russian constructivism in our practical work.

The non-equivalence means that in addition to computing an object, a program provides some additional information that can be exploited by an algorithm performing a given task. A way to better understand Markov computability is then to identify what this additional information is. In recent work, it was shown that this additional information is, in many situations, just the size of the program computing the object. In other words, a program for an object gives as much additional information as any upper bound on the Kolmogorov complexity of the object. This use of Kolmogorov complexity is novel in this kind of research and opens the way for a better understanding of Markov computability. For example, it has been found that for some classes of programs, such as the primitive recursive ones, a complete classification of Markov computability can be achieved by characterising, in terms of Kolmogorov complexity, which properties of primitive recursive functions are Markov-decidable.

Markov computability has also made an unexpected appearance in a novel approach to descriptive set theory expressed in terms of computable endofunctors on the category of represented spaces and type-two computable functions. In order to obtain an adjunction, it often seems essential to work with Markov-computable endofunctors. Understanding the precise relationship between TTE and Markov computability seems essential for the success of this programme. It also links the first objective with the second one.

Summary of this research objective: develop a characterisation of Markov computability in terms of Kolmogorov complexity.

Objective 1-II: In contrast to computations on finite objects, the study of computations on infinite objects crucially depends on topological considerations. Here and in the sequel ‘computation’ always means ‘type-two computation’. Experience shows that in natural cases functions are not computable just because they are not continuous. There are essentially two ways to obtain a qualitative measure for the degree of discontinuity, and hence for algorithmic difficulty: through the use of hierarchies or by establishing a reducibility relationship with certain well-known problems.

In the case of hierarchies as they are studied in descriptive set theory (DST), problem complexity is determined by problem description. Classifications of this kind have already been used with large success in model checking and the related theory of ω-languages.

DST was initially developed for Polish spaces, that is, countably based Hausdorff spaces. Spaces occurring in computer science investigations, particularly in program semantics, however, are typically non-Hausdorff and need not be countably based. On the other hand, they are required to form Cartesian closed categories. Some progress in adjusting DST to computer science needs has already been made: based on earlier work by Scott/Tang as well as Selivanov, de Brecht developed essential parts of DST for quasi-Polish spaces. Adjusting the usual DST constructions to the more general case was by no means straightforward. The work, partly done in the recently finished FP7-IRSES project COMPUTAL, received much attention in the community and led to many new research activities. All Polish spaces as well as important spaces used in program semantics are quasi-Polish, but spaces of this kind are still countably based.

To continue this exciting line of work we want to extend the theory even further to a Cartesian closed subcategory of Schröder-Simpson qcb-spaces, large enough to also contain the non-countably based spaces. It is well understood that extending (essential parts of) DST to non-countably based spaces is an extremely difficult task. For Hausdorff spaces interesting attempts have already been made. In the COMPUTAL project Pauly suggested a very general and promising extension of classical DST to represented spaces. These are exactly the spaces required by the TTE approach and their category is Cartesian closed. To reach our goal we will search for specific (descriptive) complexity notions for qcb-spaces that allow singling out a sufficiently large class of simple enough spaces admitting deeper investigation.

In classical DST, along with the well-known hierarchies, Wadge introduced and studied an important reducibility relation on subsets of Baire space, which was later generalised in multiple ways to a reducibility relation for functions on a given topological space. In this way, the degrees of discontinuity of several important computational problems were classified. In recent years such reducibility relations have also been used to classify mathematical theorems by identifying their computational content. The programme led to deep insights into computable mathematics. We intend continuing work along these lines in collaboration with WP3 — Logical representation of data. In particular we will look for interesting well quasi-ordered substructures of the structure of Weihrauch degrees of multi-valued functions. From work of Hertling and Selivanov such substructures are known for single-valued functions, but not for the multi-valued ones.

We are furthermore keen to extend effective DST, that is, the marriage of DST with Computability Theory. It refines and extends results from classical DST. It is therefore natural to look for similar refinements and extensions to the more general case of spaces that are not necessarily Hausdorff. The challenge is to find the “correct” computable presentation of the spaces under consideration. In the literature various such presentations have already been considered and there is now increasing interest in studying the relationship between them. We will proceed along these lines. In particular, we aim at further exploring the interactions between the various effectivity notions so as to specify the adequate ones which can provide reasonable computable presentations for the above-mentioned spaces. Countable representations of frames as studied in WP3 — Logical representation of data seem closely relevant for this endeavour and interactions with this WP are expected.

Summary of this research objective: (a) extend DST to a Cartesian closed sub-category of qcb-spaces, large enough to also contain non-countably based spaces, in particular devise specific (descriptive) complexity notions for qcb-spaces that allow singling out a sufficiently large class of simply enough spaces;

(b) find interesting well quasi-ordered substructures of the structure of Weihrauch degrees of multi-valued functions;

(c) explore the interactions between the various effectivity notions so as to identify the adequate ones.