definition of the final topology gives a recipe: take an open subset $U$ of $\mathcal{N}$, and test whether it is consistent with the representation in the sense that two names of the same point are on the same side of $U$; if that is the case, then $U$ induces an open subset of $N\langle n \rangle$, obtained as the image of $U$ under the representation. However, this recipe is useless because it does not give us more information about how to obtain the open sets. Theorem 8.3.1 tells us that in a sense, there is no better recipe.

Indeed, the complexity of testing whether an open set $U \subseteq \mathcal{N}$ is consistent is precisely $\Pi_n^1$, which explains why $N\langle n \rangle$ is $\Pi_n^1$-based, or equivalently $\Sigma_{n+1}^1$-based. Therefore, the fact that $N\langle n \rangle$ is not $\Sigma_n^1$-based tells us that there is no simpler way of describing its open sets. However, it does not exclude the possibility of finding a more “concrete” indexing of the open subsets of $N\langle n \rangle$ by elements of $N\langle n + 1 \rangle$ for instance (they can be continuously indexed by a $\Pi_n^1$-set), where “concrete” is understood in an informal and subjective sense.

We now briefly explain the proof of Theorem 8.3.1.

*Informal proof.* Our goal is to prove that there is no continuous surjection from a $\Sigma_n^1$-subset of $\mathcal{N}$ to $\mathcal{O}(N\langle n \rangle)$. We use the diagonal argument. To do so we first show that it can be reformulated as follows: there is no continuous surjection

$$ \phi: N\langle n \rangle \to \mathcal{C}(N\langle n \rangle, \mathcal{O}(N\langle n \rangle)). \qquad (8.2) $$

This reformulation follows from the following facts:

* The $\Sigma_n^1$-sets are the continuous images of $N\langle n \rangle$ (Theorem 6.1 in [SS15]),

* Two elements of $N\langle n \rangle$ can be encoded into one, i.e. there is a homeomorphism between $N\langle n \rangle$ and $N\langle n \rangle \times N\langle n \rangle$, which we write $N\langle n \rangle \cong N\langle n \rangle \times N\langle n \rangle$,

* So $\mathcal{O}(N\langle n \rangle) \cong \mathcal{O}(N\langle n \rangle \times N\langle n \rangle) \cong \mathcal{C}(N\langle n \rangle, \mathcal{O}(N\langle n \rangle))$.

We then show that there is a continuous multi-valued function $h: \mathcal{O}(N\langle n \rangle) \to \mathcal{O}(N\langle n \rangle)$ without fixed-point, which means that for each input $x$, the set of outputs $h(x)$ does not contain $x$ (see Theorem 8.3.2 below).

We finally apply the diagonal argument. If $h$ was single-valued, then the argument would go as follows: if there is a continuous surjection $\phi: N\langle n \rangle \to \mathcal{C}(N\langle n \rangle, \mathcal{O}(N\langle n \rangle))$ as in (8.2), then we take its diagonal composed with $h$, obtaining a continuous function $F \in \mathcal{C}(N\langle n \rangle, \mathcal{O}(N\langle n \rangle))$ defined by $F(x) = h(\phi(x)(x))$. This function $F$ cannot be in the range of $\phi$, because $h$ has no fixed-point so for each $x$, $F \neq \phi(x)$ because $F(x) \neq \phi(x)(x)$. It contradicts the surjectiveness of $\phi$.

However, this argument does not work because $h$ is *multi-valued*, so the function $F$ that we obtain is multi-valued as well: it is not an element of $\mathcal{C}(N\langle n \rangle, \mathcal{O}(N\langle n \rangle))$. However, it is possible to fix this problem by replacing $N\langle n \rangle$ with an intermediate space on which every continuous multi-valued function admits a continuous single-valued selector. We do not present the details here, the complete solution can be found in [Hoy22]. □

One of the key ingredients in the proof is the existence of a continuous multi-valued function $h: \mathcal{O}(N\langle n \rangle) \to \mathcal{O}(N\langle n \rangle)$ without fixed-point. This property is not specific to $N\langle n \rangle$ and actually holds for any space which is not countably-based.

**Theorem 8.3.2.** Let $X$ be an admissibly represented topological space. The following statements are equivalent:
• *X is countably-based,*

• *Every continuous multi-valued function h : O(X) ↦→ O(X) has a fixed-point.*

Observe that both Knaster-Tarski's and Kleene's fixed-point theorems imply that for every $X$, every continuous single-valued function $h : \mathcal{O}(X) \to \mathcal{O}(X)$ has a fixed-point. Thus, Theorem 8.3.2 is an illustration of the flexibility of multi-valued functions, in comparison with single-valued functions, and of their ability to detect topological properties of the underlying space. Another example of this flexibility is related to Brouwer's fixed-point theorem. That theorem asserts that every continuous function $h : [0,1]^n \to [0,1]^n$ has a fixed-point, while for every $T_1$-space $X$ which is not a singleton, there exists a continuous multi-valued function $h : X \Rightarrow X$ without fixed-point.

We explain the proof of Theorem 8.3.2.

*Informal proof.* We show that if $X$ is not countably-based, then we can build a continuous multi-valued function $h : \mathcal{O}(X) \Rightarrow \mathcal{O}(X)$ without fixed-point. One can think of $h$ as an algorithm taking an open set $U \subseteq X$ as input and producing another open set $V \subseteq X$, such that $V \neq U$. The fact that $h$ is a multi-valued function means that $V$ does not only depend on $U$, but also on the way $U$ is presented.

A name of an open set $U$ essentially consists in a growing sequence of sets $U_n$ such that $U = \cup_n U_n$. When $X$ is countably-based, we can assume that the sets $U_n$ are open (they are finite unions of basic open sets). However, when $X$ is not countably-based, the $U_n$'s are not open in general, and one can prove that there always exists an open set $V$, a point $x_0 \in V$ and a name of $V$ consisting of a growing sequence $V_n$ such that no $V_n$ is a neighborhood of $x_0$. So we can produce a name of the neighborhood $V$ of $x_0$ in such a way that no finite approximation of $V$ is a neighborhood of $x_0$.

The pseudo-algorithm for $h$ is the following. We start producing a name of $V$ and test in parallel whether $x_0 \in U$. If $x_0 \notin U$, then in the limit we output $V$, which is different from $U$ as it contains $x_0$. If we eventually see that $x_0 \in U$, then we stop producing an output, which is currently some $V_n$, and search for some $y \in U \setminus V_n$. We know that such a $y$ exists, because $V_n$ is not a neighborhood of $x$ so it cannot contain $U$. Once we have found $y$, we extend the current output as a name of an open set that does not contain $y$: simply take $X \setminus \text{cl}(\{y\})$. In that case, the open set that we produce is different from $U$ because it does not contain $y$, which is in $U$.

To make the argument work, we actually need to show that the set $X \setminus \text{cl}(\{y\})$ is consistent with our current output $V_n$. The trick is that we can always assume that the sets $V_n$, although not open, are upper sets for the specialization ordering, so that if $y \notin V_n$, then $\text{cl}(\{y\})$ is disjoint from $V_n$. □

### 8.3.1 Discussion

Let us come back to our original question in Section 2.4 about higher-order functionals. Let us take $n = 2$, so that $N\langle n \rangle = N\langle 2 \rangle = N^{N^2}$. An element of $N\langle 2 \rangle$ is a continuous function $F : N^N \to N$ (also written $F(N \to N) \to N$) and is represented as a list of pairs $(\sigma, n) \in N^* \times N$ such that $F(f) = n$ for all $f : N \to N$ extending $\sigma$, and so that every $f : N \to N$ has a prefix $\sigma$ in this list. A way to understand what information such names give about $F$ is to identify the properties of $F$ that are semidecidable given such names. One can easily come up with more and more complicated properties:

1. Whether $F$ is not constant is semidecidable,
2. Let $h: \mathbb{N} \to \mathbb{N}$ be some computable function. Whether $F(h) = 0$ is decidable,

3. Let $h \in \mathcal{N}$ be some computable function. Whether $F$ is constantly 0 on $\{p \in \mathcal{N} : p \le h\}$ is decidable,

4. For each $n \in \mathbb{N}$, let $h_n \in \mathcal{N}$ be some computable function. Whether $F(\lambda p.F(h_n)) = 0$ is decidable,

5. Let $F_0 \in \mathbb{N}\langle 2 \rangle$ be computable. Whether $F \neq F_0$ is semidecidable.

6. etc.

Properties 2.,3.,4. give classes of decidable properties obtained by varying $h, h_n$. These classes of properties have computable $\Pi_2^0$-indexings because the total computable functions $h$ have a computable $\Pi_2^0$-indexing.

Property 5. gives a class of semidecidable properties obtained by varying $F_0$. This class has a computable $\Pi_1^1$-indexing, because the computable elements $F_0$ of $\mathbb{N}\langle 2 \rangle$ have a computable $\Pi_1^1$-indexing.

The effective version of Theorem 8.3.1 shows that the general semidecidable properties have no $\Pi_1^1$-indexing so there are many more properties, expressible in more complicated ways.
# Chapter 9

## Finite representations

### Contents

<table><tr><td>9.1 Introduction</td><td>77</td></tr><tr><td>9.2 Historical results</td><td>78</td></tr><tr><td>9.3 What additional information?</td><td>79</td></tr><tr><td>9.3.1 An intermediate representation</td><td>79</td></tr><tr><td>9.3.2 δ<sub>K</sub> and δ<sub>M</sub> are interchangeable</td><td>79</td></tr><tr><td>9.4 Subrecursive classes</td><td>80</td></tr><tr><td>9.5 Indexing complexity</td><td>82</td></tr></table>

### 9.1 Introduction

In my work as well as in most of the modern literature on computable analysis, the model of computation consists of oracle or type-2 Turing machines, i.e. machines that take an infinite object as input. This approach, initiated by Kreitz and Weihrauch in [KW85], has its origins in the Polish school of computable analysis led by Grzegorczyk.

Another approach to computable mathematics, known as the Russian school, was led by Markov. It is based on the computation model of ordinary, or type-1 Turing machines, that take a finite object as input. It is done by taking a constructivist viewpoint, allowing computable objects only, and representing them by finite programs. This approach culminated in the works of Ershov on numberings.

The comparison between these two models has been thoroughly investigated in the 50s, notably by Rice [Ric53], Shapiro [Sha56], Kreisel, Lacombe, Shozenfield [KLS57], Friedberg [Fri58] and Ceitin [Ce162]. Most of the results identify situations when these two models are equivalent (for instance, functions from computable reals numbers to computable real numbers), but Friedberg's result provides an example witnessing the difference. Further comparisons have been studied, for instance by Sreen [Spr98, Spr01, Spr10] and Hertling [Her05].

We are interested in comparing these two approaches.

The first difference is that Markov computability is limited to working with computable objects only, which already separates the two models: there is a computable function from the computable real numbers to the computable real numbers that cannot be extended to a computable function from the whole set of real numbers to real numbers. However we ignore this difference by comparing Markov and type-2 computability on computable objects only. A
famous theorem due to Kreisel-Lacombe-Shoenfield and independently Ceitin states that the two models give the same class of computable functions from the space of computable real numbers to itself.

The second difference is that an infinite name can be derived from a finite program but not the other way round, so finite programs may contain more information than infinite names, making Markov computability more powerful than type-2 computability. Friedberg eventually showed that the two models are indeed non-equivalent in this sense.

We are interested in understanding the second difference through, by investigating what additional information is given by a finite representation, in comparison with an infinite one.

We are going to see that the only additional information given by a finite program is not contained in the program itself but in its size: every algorithmic task that can be performed given a finite program can be as well carried out given an infinite name and any upper bound on the size of a program computing the object.

Moreover, we study the case of objects lying in an arbitrary subrecursive class, i.e. objects that can be described by programs in a restricted programming language with total programs only. We give a characterization of the decidable properties of such objects, when represented by finite programs.

## 9.2 Historical results

Let us first review important results from the 50s comparing Markov and type-2 computability. The input objects are either partial or total computable functions on the natural numbers. The problem is then to investigate which properties of such objects are decidable or semidecidable in the two models.

For partial computable functions, the decidable and semidecidable properties are the same in the Markov and type-2 models. This is the content of Rice's and Rice-Shapiro's theorems [Ric53, Sha56].

For total computable functions, the Kreisel-Lacombe-Shoenfield/Ceitin's theorem states that the decidable properties are the same in the two models [KLS57, Cei62]. However, Friedberg surprisingly showed that the semidecidable properties are not the same in the two models [Fri58].

<table><caption>Figure 9.1: Comparison between Markov and type-2 computability</caption><thead><tr><th>Computable functions</th><th>Decidability</th><th>Semidecidability</th></tr></thead><tbody><tr><td>Partial</td><td>Markov ≡ type-2<br><i>Rice</i></td><td>Markov ≡ type-2<br><i>Rice-Shapiro</i></td></tr><tr><td>Total</td><td>Markov ≡ type-2<br><i>Kreisel et al/Tseitin</i></td><td>Markov &gt; type-2<br><i>Friedberg</i></td></tr></tbody></table>

Selivanov [Sel84] showed that for partial functions, Markov computability and type-2 computability strongly disagree at the next level, decidability with 2 mind changes. More precisely, there is a property of partial functions which is:

* Decidable with 2 mind-changes in the Markov model,

* Not $\Sigma_2^0$ in the type-2 model.
## 9.3 What additional information?

We study objects living in an effective countably-based topological $T_0$-space $X$ with its standard representation $\delta_S$. In order to be fair in the comparison between the two models, we actually work with the subspace $X_c$ of computable points of $X$.

* A $\delta_S$-name of a point $x \in X$ is any enumeration of its basic neighborhoods,

* An index of $x$ is any $i \in \mathbb{N}$ such that the $i$th partial computable function $\varphi_i$ is a name of $x$.

In the type-2 model, points are given via names while in the Markov model, points are given via indices. Let $\delta_M$ be the representation of computable points by indices, where $M$ stands for Markov.

In this section, we show that in many cases, having an index of $x$ is equivalent to having a name of $x$ and any upper bound on an index of $x$.

### 9.3.1 An intermediate representation

In order to formulate the results, we introduce another representation $\delta_K$ of $X_c$.

**Definition 9.3.1.** We define a representation $\delta_K: \subseteq \mathcal{N} \to X_c$ as follows. A $\delta_K$-name of $x \in X_c$ is a pair $(n, p)$ where

* $n$ is any upper bound on the minimal index of $x$,

* $p$ is a $\delta_S$-name of $x$.

Note that having an upper bound on the minimal index of $x$ is equivalent to having a finite set of natural numbers containing an index of $x$. The letter $K$ in $\delta_K$ stands for Kolmogorov complexity, because the minimal index of $x$ is a quantity that is similar to the Kolmogorov complexity of $x$.

Observe that from an index one can compute a $\delta_K$-name, from which one can compute a $\delta_S$. In general one cannot go in the other direction.

**Proposition 9.3.1.** In general, the representations $\delta_{X_c}$, $\delta_K$ and $\delta_M$ are not pairwise computably equivalent.

It can be proved for $X_c = \mathcal{N}_c$ and many other spaces. Although $\delta_K$ and $\delta_M$ are usually non-equivalent, we show that they can be interchangeably used to perform most algorithmic tasks. More precisely, we show that they induce the same effective descriptive complexity classes, at least at some levels.

Friedberg and Selivanov examples show that the representations $\delta_S$ and $\delta_M$ do not induce the same effective descriptive complexity classes.

### 9.3.2 $\delta_K$ and $\delta_M$ are interchangeable

In Chapter 7 we considered the symbolic complexity of a subset of a represented space as the descriptive complexity of the corresponding set of names. We recall Definition 7.2.1: in a represented space $(X, \delta_X)$, and for a descriptive complexity class $\Gamma$,

$$A \in [\Gamma](X) \iff \delta^{-1}(A) \in \Gamma(\mathrm{dom}(\delta_X)).$$
We can apply this definition to $\delta_K$ and $\delta_M$, which are representations of $X_c$.

**Main Theorem 9.3.1: Finite vs infinite representation**

Let $X$ be an effective countably-based $T_0$-space and let $\Gamma \in \{\Sigma_1^0, D_n, \Sigma_2^0\}$.
The representations $\delta_K$ and $\delta_M$ induce the same complexity classes $[\Gamma](X_c)$.

For instance, the case $\Gamma = \Sigma_1^0$ can be reformulated as follows. A subset $A \subseteq X_c$ is semidecidable given an index of $x \in X_c$ if and only if $A$ is semidecidable given a name of $x$ and an upper bound on the minimal index of $x$.

In more concrete terms, it means that the only intrinsic information that a finite program $p$ contains about the function $f: \mathbb{N} \to \mathbb{N}$ it computes is:

* The values of $f$, obtained by running the program $p$ on any input,

* A bound on the Kolmogorov complexity of $f$, i.e. on the length of the shortest program computing $f$, obtained by measuring the length of $p$.

In particular, no intrinsic information about $f$ is contained in the details of the code of the program.

## 9.4 Subrecursive classes

The previous results give some information about what properties can be decided or semidecided when the objects are given via finite programs. We would like to go further and obtain a characterization of these properties, or a way to generate all of them. It seems to be a difficult problem in general, but we can provide such a characterization in a restricted setting, where the objects are functions from a subrecursive class.

Perhaps surprisingly, the key for solving this purely computability-theoretic result is to use topology, by showing how a subrecursive class behaves like a coPolish space and using the understanding of coPolish spaces that we developed in Chapter 8.

**Definition 9.4.1.** A subrecursive class is a class $\mathcal{C}$ of total computable functions from $\mathbb{N}$ to $\mathbb{N}$ together with an effective enumeration $\mathcal{C} = \{f_i : i \in \mathbb{N}\}$, such that $f_i$ is computable uniformly in $i$. If $f_i = f$ then $i$ is called a **$\mathcal{C}$-index** of $f$.

Primitive recursive functions and usual complexity classes are subrecursive classes, but the whole class of total computable functions is not a subrecursive class. In a subrecursive class, an index can be seen as a program in some restricted programming language whose programs are all total. Having a $\mathcal{C}$-index of $f$ is stronger than having any index in the standard numbering of partial computable functions. Is it strictly stronger? Does it provide more information about $f$? Does it allow to decide more properties of functions?

The answer is positive. Let us introduce a class of properties that are decidable from $\mathcal{C}$-indices, but not necessarily from arbitrary indices.

**Definition 9.4.2.** Let $\mathcal{C}$ be a subrecursive class. The $\mathcal{C}$-complexity of $f: \mathbb{N} \to \mathbb{N}$ is

$$K_{\mathcal{C}}(f) = \min\{i \in \mathbb{N} : f_i = f\}.$$

The $\mathcal{C}$-complexity of $f$ up to $n$ is

$$K_{\mathcal{C}}(f, n) = \min\{i \in \mathbb{N} : f_i(0) = f(0), \dots, f_i(n) = f(n)\}.$$
There are a few observations to make:

* $f$ belongs to $C$ if and only if $K_C(f)$ is finite,

* For $f \in C$, $K_C(f, n)$ is nondecreasing in $n$ and eventually constant with value $K_C(f)$,

* For any $C$-index $i$ of $f$, one has $K_C(f, n) \le K_C(f) \le i$ for all $n \in \mathbb{N}$,

* The function $n \mapsto K_C(f, n)$ is computable, given $f$ as oracle.

**A computable order** is a nondecreasing unbounded computable function $h: \mathbb{N} \to \mathbb{N}$. Typical examples are $h(n) = n$, $h(n) = \lfloor\sqrt{n}\rfloor$ or $h(n) = \lfloor\log(n)\rfloor$.

**Definition 9.4.3.** Let $h$ be a computable order. A function $f: \mathbb{N} \to \mathbb{N}$ is $h$-compressible if for every $n$, $K_C(f, n) \le h(n)$.

**Proposition 9.4.1.** Let $h$ be a computable order. For $f \in C$, being $h$-compressible is decidable given a $C$-index of $f$.

*Proof.* Given a $C$-index $i$ of $f$, one has $K_C(f, n) \le K_C(f) \le i$ for all $n$. Compute $n_0$ such that $h(n_0) \ge i$. $f$ is $h$-compressible if and only if $K_C(f, n) \le h(n)$ for all $n < n_0$, which is decidable. $\square$

However, for most recursive classes, being $h$-compressible is not decidable given $f$ as oracle. Observe that for trivial classes is may be decidable: if $C$ is the class of constant functions with the obvious numbering $f_i(n) = i$, having a $C$-index for $f$ is equivalent to having $f$ as oracle: given $f$ as oracle, one can evaluate $i := f(0)$, which a $C$-index of $f$ (actually, the only one).

The class $C$ is a subset of the Baire space endowed with the product topology. A function $f \in C$ is not isolated in $C$ if every neighborhood of $f$ contains an another element of $C$.

**Proposition 9.4.2.** If $C$ contains a non-isolated function then for some computable order $h$, being $h$-compressible is not decidable given $f$ as oracle.

*Proof.* Let $f$ be a non-isolated function and $i$ an index of $f$. We define $h$. First, let $h(0) = i$, so that $f$ is $h$-compressible. We build $h$ so that for each $n$ there is some function $g \in C$ that coincides with $f$ on inputs $0, \dots, n$ and that is not $h$-compressible. As a result, $f$ does not belong to the interior of the set of $h$-compressible, which is therefore not open.

Assume that $h(n)$ is defined. As $f$ is not isolated there exist infinitely many functions that coincide with $f$ on inputs $0, \dots, n$. As a result, $C$ contains a function $g$ such that $K_C(g) > h(n)+1$, hence $K_C(g, p) > h(n) + 1$ for some $p > n$. One can compute an index of such a $g$ and $p$ by exhaustive search. Let then $h(p) = h(n) + 1$ (and $h$ is constant between $n$ and $p-1$). By construction, $g$ is not $h$-compressible. $\square$

**Main Theorem 9.4.1: Semidecidable properties of subrecursive functions**

Every semidecidable property $P$ can be written as an effective disjunction of basic properties of the form "$f \in [u]$" and of the form "$f$ is $h$-compressible".

More precisely, $P \subseteq C$ is semidecidable if and only if there exist a computable sequence of finite strings $(u_i)_{i \in \mathbb{N}}$ and a computable sequence of order functions $(h_i)_{i \in \mathbb{N}}$ such that

$$f \in P \iff \exists i, f \in [u_i] \text{ and } f \text{ is } h_i\text{-compressible.}$$
In order to prove this result, we first compare two ways of representing a function $f \in C$. The $C$-representation is the representation using $C$-indices: a $\delta_C$-name for $f$ is any $C$-index of $f$, i.e. any $i$ such that $f = f_i$ (names usually live in $N$, but $N$ can be easily embedded into $N$, identifying $i$ with the constant function with value $i$). The $K$-representation is defined as follows: a $\delta_K$-name for $f$ is any pair $(k, f)$ such that $k$ is an upper bound on $K_C(f)$ (again, $(k, f)$ can be seen as an element $g$ of $N$, defined by $g(0) = k$ and $g(n + 1) = f(n)$). Observe that $\delta_K$-names can be uniformly computed from $\delta_C$-names: send $i$ to the pair $(i, f_i)$.

We obtain an analog to Theorem 9.3.1, but the proof is much easier because $C$-indices only represent total functions, contrary to arbitrary indices.

**Lemma 9.4.1.** *The representations $\delta_C$ and $\delta_K$ induce the same semidecidable properties.*

*Proof.* Let $A \subseteq C$ be a $\delta_C$-semidecidable set. Given a $\delta_K$-name $(k, f)$ for $f$, accept $f$ if and only if for each $i \le k$, either $f_i \in A$ or $f_i \ne f$. One can easily check that $f$ is accepted if and only if $f \in A$. $\square$

*Proof of Theorem 9.4.1.* The key is to observe that $\delta_K$ is a representation of $C$ as a coPolish space, therefore we can apply the effective version of Theorem 8.2.1. Indeed, the class $C$ can be decomposed into a growing union of uniformly effective compact sets

$$C_n = \{f \in C : \exists i \le n, f_i = f\}.$$

In other words, $f \in C_n \iff K_C(f) \le n$. The sets $C_n$ are effectively compact in the metric topology inherited from the Baire space. The effective version of Theorem 8.2.1 shows that the $\delta_K$-semidecidable properties in this coPolish space are generated by:

* The basic metric balls, which are the cylinders,

* The sets $A_\epsilon = \{f \in C : \forall n, d(f, C_n) < \epsilon_n\}$.

Taking $\epsilon_n = 2^{-h(n)}$, the set $A_\epsilon$ is precisely the set of $h$-compressible functions. $\square$

The proof of this result shows how topology, notably the use of coPolish spaces, can give
insight into a purely computability-theoretic question.

## 9.5 Indexing complexity

Theorem 9.3.1 gives some information about the Markov semidecidable properties of total computable functions, but does not tell us what they look like in general, i.e. it does not provide an explicit description of them. We would like to obtain an analog to Theorem 9.4.1 for the whole class of total computable functions.

The idea of a “concrete description” is vague and can hardly be formalized. Let us have a closer look to the example of Theorem 9.4.1. It gives an explicit description of the semidecidable properties of functions in a subrecursive class, which is a recipe to build any such property from simpler objects: given a computable sequence of order functions $h_i : N \to N$ and a computable sequence of finite strings $u_i$, one can build a semidecidable property, and all of them can be obtained this way. One can measure the “simplicity” of this recipe by observing that it induces a computable indexing $(P_i)_{i \in A}$ of the semidecidable properties for some index set $A \in \Pi_2^0(N)$. One can show that this is optimal, i.e. that there is no $\Sigma_2^0$-indexing of the semidecidable properties (a $\Sigma_2^0$-indexing could actually be converted into a total indexing, which can be proved impossible).
In the quest to obtain an explicit description of the Markov semidecidable properties of total
computabe functions, we identify their minimal indexing complexity, and show that they have
no Π<sub>2</sub><sup>0</sup>-indexing. It implies in particular that there is no effective receipe to build any such
property from a computable sequence of order functions like in Theorem 9.4.1. On the other
hand, the very definition of Markov semidecidable properties induces a natural Π<sub>3</sub><sup>0</sup>-indexing
(whether a Turing machine semidecides a property, i.e. whether it behaves the same of all
indices of each total computable function, is a Π<sub>3</sub><sup>0</sup> predicate).

**Theorem 9.5.1** ([Hoy22]). *There is no computable indexing $(P_i)_{i \in A}$ of the Markov semidecidable properties, with $A \in \Pi_2^0(\mathbb{N})$.*

Observe that the same result holds if $A \in \Sigma_3^0(\mathbb{N})$ because a $\Sigma_3^0$-indexing can always be
turned into a $\Pi_2^0$-indexing: a $\Sigma_3^0$-set $A$ is $A = \{i : \exists j, \langle i, j \rangle \in B\}$ where $B \in \Pi_2^0(\mathbb{N})$, so an
indexing $(P_i)_{i \in A}$ induces the indexing $(Q_k)_{k \in B}$ where $Q_{\langle i,j \rangle} = P_i$.

Solving this question has been particularly difficult and was possible only after studying
a different topic, the base-complexity of topological spaces (see Chapter 8) and developing
a technique using fixed-points free algorithms. Again, a topological understanding can give
effective tools to solve a computability-theoretic question.

*Informal proof.* As one might expect, the proof is based on the diagonal argument: given such an indexing, build a new property which is not listed.

A key ingredient in the diagonal argument is the existence of an algorithm with no fixed-
point point: given an index of a Markov semidecidable property *P*, one can compute an index of
a Markov semidecidable property *Q* ≠ *P* (it is not true of type-2 semidecidable, i.e. effectively
open properties).

As in the proof of Theorem 8.3.1, more development is needed to make the diagonal argument
actually work. The main issue is that the fixed-point free algorithm is not extensional: given
different indices of the same *P*, it will output different properties *Q* ≠ *P*. Half of the proof is
about overcoming this problem. □
# Chapter 10

## Future directions

### 10.1 Computability of compact Polish spaces

We present several interrelated research projects about the computable aspects of compact Polish spaces, that we have already started.

#### 10.1.1 Encoding information in a space

I have recently worked on the computability of compact Polish spaces, in collaboration with Kihara and Selivanov [HKS20]. The general problem is to understand, for a compact Polish space, the difficulty of producing a presentation of the space, which is the sequence of values of some complete metric one some dense sequence. This type of questions originates from computable structure theory, which is traditionally about countable structures such as graphs, countable groups or countable partial orders, and is about the intrinsic information that can be encoded in a structure. The study of topological spaces is particularly challenging because it is much more difficult to encode and extract information from a topology than from a discrete algebraic structure.

We have proved in [HKS20] that it is not possible to encode information in Polish spaces: if a set $A \subseteq \mathbb{N}$ is computable relative to every presentation of a Polish space $X$, then $A$ must be computable. One of the main questions that remains open is whether information can be encoded into *compact presentations* of compact Polish spaces. A compact presentation is a presentation together with a list of the finite covers of the spaces. The precise question is then: is there a non-computable set $A \subseteq \mathbb{N}$ and a compact Polish space $X$ whose compact presentations all compute $A$?

#### 10.1.2 Computable type

I am currently working with a PhD student Djamel Eddine Amir on a related project about computability of compact sets. Several notions of computability exist for compact sets, the two most important ones are often called *computable sets* and *semicomputable sets*. It turns out that for some compact sets, these notions are equivalent, and that this equivalence comes from the topological properties of the set. It has led to the following definition (already encountered in Section 5.5.3): a set has **computable type** if every homeomorphic copy that is semicomputable is actually computable. It was proved by Miller [Mil02] that spheres have computable type, by Iljazović and Sušić [IS18] that closed manifolds have computable type, and other sets were studied by Iljazović and his co-authors.
Our goal is to study broader classes of compact sets, and to relate more explicitly this
computability property to the topological properties of the sets. We are led to investigating the
computable aspects of algebraic topology, in particular homology.

We have obtained purely topological characterizations of the finite simplicial complexes
having computable type [AH22]. In particular, these results enable one to reduce the global
property to a local property of the vertices of the simplicial complex. Preliminary results in
the 2-dimensional case suggest a relationship between this local property and homology. Our
next project is to establish the precise relationship between the computable type property and
homology.

10.1.3 Descriptive complexity of topological invariants

Informally, this project is about the difficulty of recognizing a certain set, given arbitrarily
precise pictures of it. For instance, if one has access to a compact set drawn on a screen at any
precision, how difficult is it to recognize that it is homeomorphic to a line segment? to a circle?
to a disk? What properties can be recognized using a limited level of complexity?

All these questions are about the descriptive complexity of topological invariants. This ques-
tion has been partially studied in the literature: it is known for instance that path-connectedness
is Π<sub>2</sub><sup>0</sup>-complete, simple connectedness is Π<sub>1</sub><sup>0</sup>-hard [Bec92], local connectedness is Π<sub>3</sub><sup>0</sup>-complete
[DS20]. Most of the topological invariants arising from topology have high complexity and we
are especially interested in the expressiveness of low complexity invariants. In other words, we
want to understand what properties can be detected with limited complexity, for instance Σ<sub>2</sub><sup>0</sup>.

A standard result from Descriptive Set Theory about actions of Polish groups implies that if we fix a compact space X, then the complexity of recognizing that a compact set is homeomorphic to X is Borel. It opens a whole line of research:

* For each compact space $X$, what is the exact complexity of recognizing its copies? We have already obtained that the complexity of recognizing copies of the line segment is precisely $\Pi_3^0$,

• Given two compact spaces *X*, *Y*, what is the complexity of distinguishing *X* from *Y*?

* Our work on the computable type property also reveals that Σ₂⁰ topological invariants play an important role, which raises the question: which pairs of spaces X, Y can be distinguished using Σ₂⁰ invariants?

**10.2 Multi-valued functions**

We briefly explain two projects about multi-valued functions.

10.2.1 Structural aspects of multi-valued functions

Functions are central in most mathematical theories. Each mathematical structure comes with a corresponding notion of morphisms, i.e. structure-preserving functions. By contrast, multi-valued, or set-valued functions are rather unusual.

Multi-valued functions are important in computable analysis, because many problems are naturally multi-valued: each instance may have several acceptable solutions. Moreover, recent works have shown that multi-valued functions can play an important role even in the study of
problems that do not involve computability. In particular, multi-valued functions are able to
capture certain properties of topological spaces, that ordinary functions cannot.

Let us give examples of this phenomenon. In a represented space $(X, \delta_X)$, the following problems have been recently studied:

1. Given a non-empty closed set $A \subseteq X$ with positive information, produce an element $x \in A$ (this problem is called *overt choice* in [dBPS20]),

2. Given a point $x \in X$ as input, output a point $y \neq x$ [BG21, Hoy22],

It turns out that when the represented space is a topological space, the solvability of these
problems captures essential properties of the space:

* When $X$ is countably-based and $T_1$, problem 1. is solvable if and only if $X$ is quasiPolish [dBPS20]; when $X$ is countably-based, a variant of problem 1. (taking any $\Pi_2^0$-set rather than a closed set as input) is solvable if and only if $X$ is quasiPolish (we are preparing an article presenting this result),

* When $X$ is countably-based, problem 2. is unsolvable if and only if $X$ is an $\omega$-continuous domain with the Scott topology; when $X = \mathcal{O}(Y)$ is a space of open sets, then problem 2. is unsolvable if and only if $Y$ is countably-based [Hoy22].

We would like to identify other classes of spaces where these problems are solvable. More
generally, we want to investigate what properties of a space can be captured by multi-valued
functions, and to better understand the interaction between multi-valued functions and struc-
tures.

10.2.2 Descriptive complexity of multi-valued functions

Descriptive Set Theory (DST) provides a full understanding of the complexity of subsets of Polish spaces. In computable analysis, one is naturally led to work in represented spaces rather than Polish spaces and with multi-valued functions rather than sets. Therefore, it would be useful to develop measures of descriptive complexity of multi-valued functions between represented spaces.

Let us briefly explain a feature of DST from which we would like to take inspiration. Descriptive set theory provides a notion of reducibility between sets (Wadge reducibility) as well as complexity hierarchies (Borel hierarchy, Hausdorff difference hierarchy, fine Hierarchy). Each individual set (among the Borel sets) can be assigned a definite complexity, and the comparison between sets reduces to the comparison between their complexities.

The situation is very different for functions and multi-valued functions. They can be com-
pared using Weihrauch reducibility and its variants such as computable reducibility [BGP21,
Dzh15], but there is no intrinsic complexity for an individual multi-valued function. Multi-
valued functions have a wide range of aspects for which different complexity notions may be
defined: the complexity of decomposing the input space to make it computable on each piece,
the complexity of convergence of a mind-change algorithm, the minimal advice that is needed
to make it computable, etc. These aspects are central in the literature on the computability of
multi-valued functions and Weihrauch reducibility, for instance in [Bra05, BP10, Zie12, PdB12].

It would be interesting to define and study intrinsic notions of complexity for multi-valued
functions. It would help classify problems by comparing their respective complexities. Moreover,
knowing the intrinsic complexity (or complexities) of a problem is a more condensed and precise
piece of information than knowing how it compares to all other problems, in the same way as
saying that the set $\mathbb{Q}$ of rational numbers is $\Sigma_2^0$-complete in $\mathbb{R}$ summarizes all the isolated facts
that each problem is or is not reducible to it.

We will take inspiration from notions recently introduced by Goh, Pauly and Valenti [GPV21]
and Dzhafarov, Solomon and Yokoyama respectively: the deterministic and first-order parts of
a multi-valued functions offer a way to capture some of its aspects.
# Main definitions, theorems and open questions

## Main definitions

<table><tr><td>5.3.1 Effectively generically weaker</td><td>36</td></tr><tr><td>5.5.1 Effectively generically weaker</td><td>45</td></tr><tr><td>6.2.1 Upper-generic point</td><td>51</td></tr><tr><td>6.3.1 Right-generic real</td><td>52</td></tr><tr><td>7.2.1 Symbolic complexity</td><td>60</td></tr></table>

## Main theorems

<table><tr><td>5.3.2 τ'-computable but not τ-computable</td><td>37</td></tr><tr><td>5.5.2 τ₁-computable but not τ₂-computable</td><td>45</td></tr><tr><td>6.2.2 Existence of upper-generic computable points</td><td>51</td></tr><tr><td>7.4.1 Symbolic vs topological complexity</td><td>62</td></tr><tr><td>7.5.4 Classification – Negative results</td><td>66</td></tr><tr><td>8.3.1 Base-complexity of Kleene-Kreisel spaces</td><td>72</td></tr><tr><td>9.3.1 Finite vs infinite representation</td><td>80</td></tr><tr><td>9.4.1 Semidecidable properties of subrecursive functions</td><td>81</td></tr></table>

## Main open questions

<table><tr><td>5.4.3 Weihrauch vs strong Weihrauch reducibility</td><td>43</td></tr><tr><td>6.5.2 Right-genericity vs Baire category</td><td>56</td></tr><tr><td>7.4.4 Symbolic vs topological complexity in Hausdorff spaces</td><td>63</td></tr><tr><td>7.5.5 Symbolic vs topological complexity on O(X)</td><td>67</td></tr><tr><td>7.5.6 Symbolic vs topological complexity on O(N)</td><td>67</td></tr></table>
Bibliography

[AH22] Djamel Eddine Amir and Mathieu Hoyrup. Computability of finite simplicial complexes. In *ICALP 2022*, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. To appear. 8, 23, 46, 86

[AH23] Djamel Eddine Amir and Mathieu Hoyrup. Comparing computability in two topologies. Preprint, 2023. 40

[BCSS12] L. Blum, F. Cucker, M. Shub, and S. Smale. *Complexity and Real Computation*. SpringerLink : Bücher. Springer New York, 2012. 4

[BDH+12] Laurent Bienvenu, Adam R. Day, Mathieu Hoyrup, Ilya Mezhirov, and Alexander Shen. A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points. *Information and Computation*, 210:21-30, 2012. 7, 22

[Bec92] Howard Becker. Descriptive set theoretic phenomena in analysis and topology. In Haim Judah, Winfried Just, and Hugh Woodin, editors, *Set Theory of the Continuum*, pages 1-25, New York, NY, 1992. Springer US. 86

[BEGH15] Guillaume Bonfante, Mohamed El-Aqqad, Benjamin Greenbaum, and Mathieu Hoyrup. Immune systems in computer virology. In Arnold Beckmann, Victor Mintrana, and Mariya Ivanova Soskova, editors, *Evolving Computability - 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, June 29 - July 3, 2015. Proceedings*, volume 9136 of *Lecture Notes in Computer Science*, pages 127-136. Springer, 2015. 7, 23

[BG21] Vasco Brattka and Guido Gherardi. Completion of choice. *Ann. Pure Appl. Log.*, 172(3):102914, 2021. 87

[BGH+11] Laurent Bienvenu, Peter Gács, Mathieu Hoyrup, Cristóbal Rojas, and Alexander Shen. Algorithmic tests and randomness with respect to a class of measures. *Proceedings of the Steklov Institute of Mathematics*, 274(1):34-89, November 2011. 7, 22

[BGP21] Vasco Brattka, Guido Gherardi, and Arno Pauly. Weihrauch complexity in computable analysis. In Vasco Brattka and Peter Hertling, editors, *Handbook of Computability and Complexity in Analysis, Theory and Applications of Computability*, pages 367-417. Springer, Cham, 2021. 87

[BH02] Vasco Brattka and Peter Hertling. Topological properties of real number representations. *Theor. Comput. Sci.*, 284(2):241-257, 2002. 4, 32
[BH03] Olivier Bournez and Mathieu Hoyrup. Rewriting logic and probabilities. In Robert Nieuwenhuis, editor, *RTA*, volume 2706 of *Lecture Notes in Computer Science*, pages 61–75. Springer, 2003. 23

[BH10] Laurent Bienvenu and Mathieu Hoyrup. Une brève introduction à la théorie de l'aléatoire. *Gazette des mathématiciens*, 123:35–47, 2010. 23

[BH21] V. Brattka and P. Hertling. *Handbook of Computability and Complexity in Analysis. Theory and Applications of Computability*. Springer International Publishing, 2021. 4

[BHS17] Laurent Bienvenu, Mathieu Hoyrup, and Alexander Shen. Layerwise computability and image randomness. *Theory Comput. Syst.*, 61(4):1353–1375, 2017. 7, 22

[BHW08] Vasco Brattka, Peter Hertling, and Klaus Weihrauch. A tutorial on computable analysis. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, *New Computational Paradigms*, pages 425–491. Springer New York, 2008. 27

[Bis67] E. Bishop. *Foundations of Constructive Analysis*. McGraw-Hill series in higher mathematics. McGraw-Hill, 1967. 4

[BP03] Vasco Brattka and Gero Presser. Computability on subsets of metric spaces. *Theoretical Computer Science*, 305(1-3):43–76, 2003. 32

[BP10] Vasco Brattka and Arno Pauly. Computation with advice. In Xizhong Zheng and Ning Zhong, editors, *Proceedings Seventh International Conference on Computability and Complexity in Analysis, CCA 2010, Zhenjiang, China, 21-25th June 2010.*, volume 24 of *EPTCS*, pages 41–55, 2010. 32, 87

[Bra99] Vasco Brattka. Computable invariance. *Theor. Comput. Sci.*, 210(1):3–20, 1999. 32

[Bra05] Vasco Brattka. Effective Borel measurability and reducibility of functions. *Mathematical Logic Quarterly*, 51(1):19–44, 2005. 4, 39, 57, 87

[BW99] Vasco Brattka and Klaus Weihrauch. Computability on subsets of euclidean space i: Closed and compact subsets. *Theoretical Computer Science*, 219(1-2):65–93, 1999. 32

[Car21] Raphaël Carroy. Personal communication. 2021. 40, 42

[Cei62] G. S. Ceitin. Algorithmic operators in constructive metric spaces. *Trudy Matematiki Instituta Steklov*, 67:295–361, 1962. English translation: *American Mathematical Society Translations*, series 2, 64:1-80, 1967. 77, 78

[CFHR22] Daniel Coronel, Alexander Frank, Mathieu Hoyrup, and Cristóbal Rojas. Realizing semicomputable simplices by computable dynamical systems. *Theoretical Computer Science*, 2022. To appear. 7, 21, 39

[CH20] Antonin Callard and Mathieu Hoyrup. Descriptive complexity on non-Polish spaces. In Christophe Paul and Markus Bläser, editors, *37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France*, volume 154 of *LIPIcs*, pages 8:1–8:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. 7, 14, 23, 41, 58, 60, 61, 62, 63
[dB13] Matthew de Brecht. Quasi-Polish spaces. *Ann. Pure Appl. Logic*, 164(3):356-381, 2013. 4, 14, 41, 57, 59, 60

[dBPS20] Matthew de Brecht, Arno Pauly, and Matthias Schröder. Overt choice. *Computability*, 9(3-4):169-191, 2020. 87

[dBSS16] Matthew de Brecht, Matthias Schröder, and Victor Selivanov. Base-complexity classifications of qcb₀-spaces. *Computability*, 5(1):75-102, 2016. 16, 70, 72

[dBY09] Matthew de Brecht and Akihiro Yamamoto. $\Sigma_\alpha^0$ - Admissible Representations (Extended Abstract). In Andrej Bauer, Peter Hertling, and Ker-I Ko, editors, *6th International Conference on Computability and Complexity in Analysis (CCA'09)*, volume 11 of *OpenAccess Series in Informatics (OASICS)*, Dagstuhl, Germany, 2009. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. 14, 41, 57, 60

[DL02] Rodney G. Downey and Geoffrey LaForte. Presentations of computably enumerable reals. *Theor. Comput. Sci.*, 284(2):539-555, 2002. 54

[DS20] Gabriel Debs and Jean Saint Raymond. The descriptive complexity of connectedness in Polish spaces. *Fundamenta Mathematicae*, 249(3):261-286, 2020. 86

[Dzh15] Damir D. Dzhafarov. Cohesive avoidance and strong reductions. *Proceedings of the American Mathematical Society*, 143(2):869-876, 2015. 87

[Eda97] Abbas Edalat. Domains for computation in mathematics, physics and exact real arithmetic. *The Bulletin of Symbolic Logic*, 3(4):401-452, 1997. 4

[Esc04] Martín Escardó. Synthetic topology: of data types and classical spaces. *Electronic Notes in Theoretical Computer Science*, 87:21-156, 2004. Proceedings of the Workshop on Domain Theoretic Methods for Probabilistic Processes. 4

[FGH13] Hugo Férée, Walid Gomaa, and Mathieu Hoyrup. On the query complexity of real functionals. In *Proceedings of the 28th Annual IEEE Symposium on Logic in Computer Science, LICS 2013, June 25-28, New Orleans, LA, USA*, pages 103-112. IEEE Computer Society, 2013. 7, 23

[FGH14] Hugo Férée, Walid Gomaa, and Mathieu Hoyrup. Analytical properties of resource-bounded real functionals. *J. Complexity*, 30(5):647-671, 2014. 7, 23

[FH13] Hugo Férée and Mathieu Hoyrup. Higher-order complexity in analysis. CCA 2013, July 8-10, Nancy, 2013. 23

[FHHP10] Hugo Férée, Emmanuel Hainry, Mathieu Hoyrup, and Romain Péchoux. Interpretation of stream programs: Characterizing type 2 polynomial time complexity. In Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park, editors, *Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I*, volume 6506 of *Lecture Notes in Computer Science*, pages 291-303. Springer, 2010. 7, 23

[FHHP15] Hugo Férée, Emmanuel Hainry, Mathieu Hoyrup, and Romain Péchoux. Characterizing polynomial time complexity of stream programs using interpretations. *Theor. Comput. Sci.*, 585:41-54, 2015. 7, 23
[Fri58] Richard M. Friedberg. Un contre-exemple relatif aux fonctionnelles récursives. *Comptes Rendus de l'Académie des Sciences*, 247:852-854, 1958. 77, 78

[GHR09a] Peter Gács, Mathieu Hoyrup, and Cristóbal Rojas. Randomness on computable probability spaces - A dynamical point of view. In Susanne Albers and Jean-Yves Marion, editors, *STACS*, LIPIcs, pages 469-480. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009. 21

[GHR09b] Stefano Galatolo, Mathieu Hoyrup, and Cristóbal Rojas. A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties. *Theoretical Computer Science*, 410(21-23):2207-2222, 2009. 21

[GHR10a] Stefano Galatolo, Mathieu Hoyrup, and Cristóbal Rojas. Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems. In Xizhong Zheng and Ning Zhong, editors, Proceedings Seventh International Conference on *Computability and Complexity in Analysis*, Zhenjiang, China, 21-25th June 2010, volume 24 of *Electronic Proceedings in Theoretical Computer Science*, pages 7-18. Open Publishing Association, 2010. 21

[GHR10b] Stefano Galatolo, Mathieu Hoyrup, and Cristóbal Rojas. Effective symbolic dynamics, random points, statistical behavior, complexity and entropy. *Information and Computation*, 208(1):23-41, 2010. 22

[GHR11a] Péter Gács, Mathieu Hoyrup, and Cristóbal Rojas. Randomness on computable probability spaces - a dynamical point of view. *Theory of Computing Systems*, 48(3):465-485, 2011. 22

[GHR11b] Stefano Galatolo, Mathieu Hoyrup, and Cristóbal Rojas. Dynamics and abstract computability: computing invariant measures. *Discrete and Continuous Dynamical Systems - A*, 29(1):193-212, jan 2011. 7, 21

[GHR12] Stefano Galatolo, Mathieu Hoyrup, and Cristóbal Rojas. Statistical properties of dynamical systems - simulation and abstract computation. *Chaos, Solitons and Fractals*, 45(1):1-14, 2012. 7, 21

[GPV21] Jun Le Goh, Arno Pauly, and Manlio Valenti. Finding descending sequences through ill-founded linear orders. *The Journal of Symbolic Logic*, 86(2):817-854, 2021. 88

[Gra64] R. L. Graham. On finite sums of reciprocals of distinct nth powers. *Pacific J. Math.*, 14(1):85-92, 1964. 55

[Gra74] Jacques Grassin. Index sets in Ershov's hierarchy. *The Journal of Symbolic Logic*, 39:97-104, 3 1974. 58, 64

[Grz57] Andrzej Grzegorczyk. On the definitions of computable real continuous functions. *Fundamenta Mathematicae*, 44(1):61-71, 1957. 4

[Her05] Peter Hertling. A Banach-Mazur computable but not Markov computable function on the computable real numbers. *Ann. Pure Appl. Log.*, 132(2-3):227-246, 2005. 77

[HG17] Mathieu Hoyrup and Walid Gomaa. On the extension of computable real functions. In *32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017*,
Reykjavik, Iceland, June 20-23, 2017, pages 1-12. IEEE Computer Society, 2017. 7, 12, 22, 50, 54

[HKL08] Mathieu Hoyrup, Arda Kolçak, and Giuseppe Longo. Computability and the morphological complexity of some dynamics on continuous domains. *Theoretical Computer Science*, 398(1-3):170-182, 2008. 21

[HKS20] Mathieu Hoyrup, Takayuki Kihara, and Victor Selivanov. Degree Spectra of Homeomorphism Types of Polish Spaces. working paper or preprint, April 2020. 8, 85

[Hoy07] Mathieu Hoyrup. Dynamical systems: stability and simulability. *Mathematical Structures in Computer Science*, 17(2):247-259, 2007. 21

[Hoy11] Mathieu Hoyrup. Randomness and the ergodic decomposition. In Benedikt Löwe, Dag Normann, Ivan N. Soskov, and Alexandra A. Soskova, editors, *CiE*, volume 6735 of *Lecture Notes in Computer Science*, pages 122-131. Springer, 2011. 7, 22

[Hoy12] Mathieu Hoyrup. The dimension of ergodic random sequences. In Christoph Dürr and Thomas Wilke, editors, *STACS*. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012. 7, 22

[Hoy13] Mathieu Hoyrup. Computability of the ergodic decomposition. *Annals of Pure and Applied Logic*, 164(5):542-549, 2013. 7, 21, 32, 38

[Hoy14] Mathieu Hoyrup. Irreversible computable functions. In Ernst W. Mayr and Natacha Portier, editors, *31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France*, volume 25 of *LIPIcs*, pages 362-373. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. 6, 11, 12, 22, 37, 38

[Hoy15] Mathieu Hoyrup. Que calcule cet algorithme ?, 2015. Images des Mathématiques, CNRS. 19, 23

[Hoy16a] Mathieu Hoyrup. The decidable properties of subrecursive functions. In *ICALP 2016, July 11-15, 2016, Rome, Italy*, volume 55 of *LIPIcs*, pages 108:1-108:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. 7, 19, 23

[Hoy16b] Mathieu Hoyrup. The typical constructible object. In Arnold Beckmann, Laurent Bienvenu, and Natasa Jonoska, editors, *Pursuit of the Universal - 12th Conference on Computability in Europe, CiE 2016, Paris, France, June 27 - July 1, 2016, Proceedings*, volume 9709 of *Lecture Notes in Computer Science*, pages 115-123. Springer, 2016. 24

[Hoy17] Mathieu Hoyrup. Genericity of weakly computable objects. *Theory Comput. Syst.*, 60(3):396-420, 2017. 6, 11, 12, 22, 50, 53

[Hoy18] Mathieu Hoyrup. Topological analysis of representations. In Florin Manea, Russell G. Miller, and Dirk Nowotka, editors, *Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, July 30 - August 3, 2018, Proceedings*, volume 10936 of *Lecture Notes in Computer Science*, pages 214-223. Springer, 2018. 24
[Hoy20a] Mathieu Hoyrup. Algorithmic randomness and layerwise computability. In Johanna N. Y. Franklin and Christopher P. Porter, editors, *Algorithmic Randomness: Progress and Prospects*, chapter 4, pages 115–133. Cambridge University Press, Cambridge, 2020. 7, 24

[Hoy20b] Mathieu Hoyrup. Descriptive complexity on non-Polish spaces II. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, *47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference)*, volume 168 of LIPIcs, pages 132:1–132:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. 7, 14, 23, 58, 63, 64

[Hoy22] Mathieu Hoyrup. The fixed-point property for represented spaces. *Annals of Pure and Applied Logic*, 173(5):103090, 2022. 7, 17, 19, 23, 72, 73, 83, 87

[HR09a] Mathieu Hoyrup and Cristóbal Rojas. An application of Martin-Löf randomness to effective probability theory. In Klaus Ambos-Spies, Benedikt Löwe, and Wolfgang Merkle, editors, *CiE, volume 5635 of Lecture Notes in Computer Science*, pages 260–269. Springer, 2009. 7, 22

[HR09b] Mathieu Hoyrup and Cristóbal Rojas. Applications of effective probability theory to Martin-Löf randomness. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, and Wolfgang Thomas, editors, *ICALP 2009*, volume 5555 of Lecture Notes in Computer Science, pages 549–561. Springer, 2009. 7, 22

[HR09c] Mathieu Hoyrup and Cristóbal Rojas. Computability of probability measures and Martin-Löf randomness over metric spaces. *Information and Computation*, 207(7):830–847, 2009. 22

[HR15] Mathieu Hoyrup and Cristóbal Rojas. On the information carried by programs about the objects they compute. In *STACS 2015, March 4-7, 2015, Garching, Germany*, volume 30 of LIPIcs, pages 447–459. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. 7, 19, 23

[HR17] Mathieu Hoyrup and Cristóbal Rojas. On the information carried by programs about the objects they compute. *Theory Comput. Syst.*, 61(4):1214–1236, 2017. 7, 19, 23, 32

[HR21] Mathieu Hoyrup and Jason Rute. Computable Measure Theory and Algorithmic Randomness. In Vasco Brattka and Peter Hertling, editors, *Handbook of Computability and Complexity in Analysis*. Springer, 2021. 7, 24

[HRSS19] Mathieu Hoyrup, Cristóbal Rojas, Victor L. Selivanov, and Donald M. Stull. Computability on quasi-Polish spaces. In Michal Hospodár, Galina Jirásková, and Stavros Konstantinidis, editors, *Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Košice, Slovakia, July 17-19, 2019, Proceedings*, volume 11612 of Lecture Notes in Computer Science, pages 171–183. Springer, 2019. 7, 23

[HRW11] Mathieu Hoyrup, Cristóbal Rojas, and Klaus Weihrauch. Computability of the Radon-Nikodym derivative. In Benedikt Löwe, Dag Normann, Ivan N. Soskov, and Alexandra A. Soskova, editors, *CiE, volume 6735 of Lecture Notes in Computer Science*, pages 132–141. Springer, 2011. 7, 22
[HRW12] Mathieu Hoyrup, Cristóbal Rojas, and Klaus Weihrauch. Computability of the Radon-Nikodym derivative. *Computability*, 1(1):3–13, 2012. 7, 22

[HS19] Mathieu Hoyrup and Donald M. Stull. Semicomputable points in Euclidean spaces. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, *44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany*, volume 138 of *LIPIcs*, pages 48:1–48:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. 7, 12, 22, 56

[HSS18] Mathieu Hoyrup, Diego Nava Saucedo, and Don M. Stull. Semicomputable geometry. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, *45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic*, volume 107 of *LIPIcs*, pages 129:1–129:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. 7, 12, 22, 56

[HY88] J.G. Hocking and G.S. Young. *Topology*. Addison-Wesley series in mathematics. Dover Publications, 1988. 27

[Ilj11] Zvonko Iljazović. Co-c.e. spheres and cells in computable metric spaces. *Logical Methods in Computer Science*, 7(3), 2011. 32

[Ing81] M.A. Ingrassia. *P-genericity for Recursively Enumerable Sets*. PhD thesis, University of Illinois at Urbana-Champaign, 1981. 50

[IS18] Zvonko Iljazović and Igor Sušić. Semicomputable manifolds in computable topological spaces. *J. Complex.*, 45:83–114, 2018. 32, 46, 85

[Joc80] Carl G. Jockush. Degrees of generic sets. In F. R. Drake and S. S. Wainer, editors, *Recursion Theory: its Generalisations and Applications*, pages 110–139. Cambridge University Press, 1980. 50

[Joc85] Carl G. Jockusch. Genericity for recursively enumerable sets. In Heinz-Dieter Ebbinghaus, Gert H. Müller, and Gerald E. Sacks, editors, *Recursion Theory Week*, pages 203–232, Berlin, Heidelberg, 1985. Springer Berlin Heidelberg. 50

[Jon99] Sara Hawtrey Jones. Applications of the Baire category theorem. *Real Anal. Exchange*, 23(2):363–394, 1999. 11

[Kec95] Alexander S. Kechris. *Classical Descriptive Set Theory*. Springer, January 1995. 59

[KLS57] Georg Kreisel, Daniel Lacombe, and Joseph R. Shoenfield. Fonctionnelles récursivement définissables et fonctionnelles récursives. *Comptes Rendus de l'Académie des Sciences*, 245:399–402, 1957. 77, 78

[KNP19] Takayuki Kihara, Keng Meng Ng, and Arno Pauly. Enumeration degrees and non-metrizable topology. arXiv:1904.04107, 2019. 32, 33

[KP14] Takayuki Kihara and Arno Pauly. Point degree spectra of represented spaces. *CoRR*, abs/1405.6866, 2014. 4, 32, 33

[Kur81] S. Kurtz. *Randomness and genericity in the degrees of unsolvability*. PhD thesis, University of Illinois at Urbana, 1981. 50
[KW85] Christoph Kreitz and Klaus Weihrauch. Theory of representations. *Theoretical Computer Science*, 38:35 – 53, 1985. 4, 18, 77

[Lac59] Daniel Lacombe. Quelques procédés de définition en topologie récursive. In A. Heyt- ing, editor, *Journal of Symbolic Logic*, pages 129–158. Amsterdam: North-Holland Pub. Co., 1959. 4

[Lac73] A.H. Lachlan. The priority method for the construction of recursively enumerable sets. In A.R.D. Mathias and H. Rogers, editors, *Cambridge Summer School in Math- ematical Logic*, volume 337 of *Lecture Notes in Mathematics*, pages 299–310. Springer Berlin Heidelberg, 1973. 50

[Lut21] Patrick Lutz. *Results on Martin's Conjecture*. PhD thesis, University of California, Berkeley, 2021. 40

[Maa82] Wolfgang Maass. Recursively enumerable generic sets. *The Journal of Symbolic Logic*, 47(4):809–823, 1982. 50

[Mil02] Joseph S. Miller. Effectiveness for embedded spheres and balls. *Electronic Notes in Theoretical Computer Science*, 66(1):127 – 138, 2002. CCA 2002, Computability and Complexity in Analysis (ICALP 2002 Satellite Workshop). 32, 46, 85

[NR85] A. Nerode and J. B. Remmel. Generic objects in recursion theory. In Heinz-Dieter Ebbinghaus, Gert H. Müller, and Gerald E. Sacks, editors, *Recursion Theory Week*, pages 271–314, Berlin, Heidelberg, 1985. Springer Berlin Heidelberg. 50

[Pau16] Arno Pauly. On the topological aspects of the theory of represented spaces. *Computability*, 5(2):159–180, 2016. 4, 27

[PdB12] Arno Pauly and Matthew de Brecht. Non-deterministic computation and the Jayne-Rogers theorem. In Benedikt Löwe and Glynn Winskel, editors, *Proceedings 8th International Workshop on Developments in Computational Models, DCM 2012, Cambridge, United Kingdom, 17 June 2012*, volume 143 of *EPTCS*, pages 87–96, 2012. 32, 87

[PdB15] Arno Pauly and Matthew de Brecht. Descriptive set theory in the category of represented spaces. In *30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015*, pages 438–449. IEEE Computer Society, 2015. 58

[PER89] Marian B. Pour-El and J. Ian Richards. *Computability in Analysis and Physics. Perspectives in Mathematical Logic*. Springer, Berlin, 1989. 32, 36, 37

[PS09] Janusz Pawlikowski and Marcin Sabok. The Solecki dichotomy for bianalytic maps. Preprint, 2009. 34, 40

[PS12] Janusz Pawlikowski and Marcin Sabok. Decomposing Borel functions and structure at finite levels of the Baire hierarchy. *Annals of Pure and Applied Logic*, 163(12):1748–1764, 2012. 34, 40

[Ray07] Jean Saint Raymond. Preservation of the Borel class under countable-compact-covering mappings. *Topology and its Applications*, 154(8):1714 – 1725, 2007. 57
[Ric53] Henry G. Rice. Classes of recursively enumerable sets and their decision problems. *Transactions of the American Mathematical Society*, 74(2):pp. 358–366, 1953. 77, 78

[Ric54] H. G. Rice. Recursive real numbers. *Proceedings of the American Mathematical Society*, 5:784–791, 1954. 4

[Šan68] N.A. Šanin. *Constructive Real Numbers and Constructive Function Spaces*, volume 21 of *Translations of Mathematical Monographs*. American Mathematical Society, Providence, 1968. 4

[Sch02a] Matthias Schröder. *Admissible Representations for Continuous Computations*. PhD thesis, FernUniversität Hagen, 2002. 4, 14, 29, 58, 66

[Sch02b] Matthias Schröder. Extended admissibility. *Theor. Comput. Sci.*, 284(2):519–538, 2002. 14

[Sch04] Matthias Schröder. Spaces allowing type-2 complexity theory revisited. *Math. Log. Q.*, 50(4-5):443–459, 2004. 4, 61

[Sch21] Matthias Schröder. Admissibly represented spaces and Qcb-spaces. In Vasco Brattka and Peter Hertling, editors, *Handbook of Computability and Complexity in Analysis*. Springer, 2021. 27

[Sel84] Victor L. Selivanov. Index sets in the hyperarithmetic hierarchy. *Siberian Mathematical Journal*, 25:474–488, 1984. 58, 78

[Sel08] Victor Selivanov. On the difference hierarchy in countably based t0-spaces. *Electronic Notes in Theoretical Computer Science*, 221:257–269, 12 2008. 57

[Sha56] Norman Shapiro. Degrees of computability. *Transactions of the American Mathematical Society*, 82:281–299, 1956. 77, 78

[Sol98] Slawomir Solecki. Decomposing Borel sets and functions and the structure of Baire class 1 functions. *Journal of the American Mathematical Society*, 11(3):521–550, 1998. 34, 40

[Spr98] Dieter Sreen. On effective topological spaces. *Journal of Symbolic Logic*, 63(1):185–221, 1998. 77

[Spr01] Dieter Sreen. Representations versus numberings: on the relationship of two computability notions. *Theor. Comput. Sci.*, 262(1):473–499, 2001. 77

[Spr10] Dieter Sreen. Effectivity and effective continuity of multifunctions. *J. Symb. Log.*, 75(2):602–640, 2010. 77

[SS15] Matthias Schröder and Victor L. Selivanov. Hyperprojective hierarchy of qcb₀-spaces. *Computability*, 4(1):1–17, 2015. 73

[Tay11] Paul Taylor. *Foundations for Computable Topology*, pages 265–310. Springer Netherlands, Dordrecht, 2011. 4

[Tur36] Alan Turing. On computable numbers, with an application to the entscheidungsproblem. *Proceedings of the London Mathematical Society*, 2, 42:230–265, 1936. 4
[Wei00] Klaus Weihrauch. *Computable Analysis*. Springer, Berlin, 2000. 4, 27, 29, 31

[Wei01] Klaus Weihrauch. On computable metric spaces Tietze-Urysohn extension is com-
putable. In Jens Blanck, Vasco Brattka, and Peter Hertling, editors, *Computability
and Complexity in Analysis*, pages 357–368, Berlin, Heidelberg, 2001. Springer Berlin
Heidelberg. 71

[Zie02] Martin Ziegler. Computability on regular subsets of euclidean space. *Mathematical Logic Quarterly*, 48(S1):157–181, 2002. 32

[Zie12] Martin Ziegler. Real computation with least discrete advice: A complexity theory of nonuniform computability with applications to effective linear algebra. *Annals of Pure and Applied Logic*, 163(8):1108–1139, 2012. Continuity, Computability, Constructivity: From Logic to Algorithms. 4, 32, 87
Index

Base-complexity, 68

Borel hierarchy, 55

C-complexity, 76

Compressible, h-, 77

Computable
order, 77

Computable type, 42

CoPolish space, 57

$\delta_K$, 75

$\delta_M$, 75

Descriptive complexity class, 54

Ergodic decomposition, 34

Generic
right-, 48
upper-, 47
weakly-1-, 49

Generically weaker, 29
$\tau-$, 39
effectively, 41
effectively, 32

Hausdorff difference hierarchy, 55

Kleene-Kreisel functionals, 68

Left-c.e. dense open set, 52

Lower boundary, 47

Projective hierarchy, 68

$\sigma$-continuous, 29

Simple real, 49, 50

Sparse set, 51

Specialization pre-order, 46

Subrecursive class, 76

Symbolic complexity, 56

Witness, 30