Topological analysis of representations

Mathieu Hoyrup

Université de Lorraine, CNRS, Inria, LORIA, F 54000 Nancy, France Abstract. Computable analysis is the theoretical study of the abilities of algorithms to process infinite objects. The algorithms abilities depend on the way these objects are presented to them. We survey recent results on the problem of identifying the properties of objects that are decidable or semidecidable, for several concrete classes of objects and representations of them. Topology is at the core of this study, as the decidable and semidecidable properties are closely related to the open sets induced by the representation.

In order to process mathematical objects with algorithms one has to encode or represent these objects, by symbolic sequences or sequences of natural numbers. The choice of the representation has a direct impact on the algorithmic tasks that can be performed on these objects, for instance on the class of properties that can be decided or semidecided. A property is decidable if there is a program or Turing machine that given a representation of an input, halts and answers whether the input satisfies the property. A property is semidecidable if the program halts exactly when the input satisfies the property.

The problem of understanding the classes of decidable and semidecidable properties with respect to a given representation has been addressed in many ways in computability theory and computable analysis. Usually, a representation induces a topology (its final topology), and the semidecidable properties are the effective open sets and the computable functions are the effectively continuous ones. Therefore the problem often amounts to understanding what are the open sets in that topology.

The abstract correspondence between computability and topology has been thoroughly studied, on countably-based topological spaces in [START_REF] Weihrauch | Computable Analysis[END_REF], on more general spaces in [START_REF] Schröder | Extended admissibility[END_REF] and [START_REF] Pauly | On the topological aspects of the theory of represented spaces[END_REF] among others.

Our general problem is to understand, for a given class of objects with a particular representation, the information contained in the representation of objects. We investigate this problem by identifying what can be known about the objects from their representations, more precisely: Problem 1 Given a class of objects and a representation, identify the properties of objects that are semidecidable w.r.t. this representation.

The decidable properties are then the ones that are semidecidable and have a semidecidable complement.

We will see several cases where a solution to this problem is known. When the class of semidecidable properties is not well-understood, one can try to identify the difficulty of describing these properties: Problem 2 Given a class of objects and a representation, identify the minimal complexity of a set A ⊆ N such that there is a computable indexing (P i ) i∈A of the semidecidable properties.

The complexity of A is usually measured in terms of the arthmetical or hyperarithmetical hierarchies.

We present some recent results on this problem for various classes of objects and their representations:

-When considering computable objects only, they can be represented by finite programs, which is at the basis of Markov computability. -Sometimes a task cannot be performed w.r.t. a particular representation, unless some finite advice is provided, which induces another representation. -While computable analysis behaves very well on countably-based topological spaces, it is less understood on other spaces. A typical example is the space of higher-order partial or total continuous functionals, introduced by Kleene [START_REF] Kleene | Countable functionals[END_REF] and Kreisel [5].

Problems 1 and 2 are formulated for semidecidable properties but also make sense for other classes of properties. In N N , the semidecidable properties are the effective open sets, or the Σ 0 1 -sets from the effective Borel hierarchy. This hierarchy provides different levels of computability of properties and can be transferred from the Baire space to any set X with a representation δ X : dom(δ

X ) ⊆ N N → X as follows: say that A ⊆ X is a Σ 0 n -subset of X if there exists a Σ 0 n -subset P of N N such that δ -1 X (A) = P ∩ dom(δ X ).
This definition is at the basis the development of descriptive set theory on represented spaces [START_REF] Pauly | Descriptive set theory in the category of represented spaces[END_REF].

With this definition, the semidecidable properties of points of X are exactly the Σ 0 1 -subsets of X. Then Problems 1 and 2 can also be formulated for Σ 0 nproperties.

In this paper we use the approach to computable analysis using representations. We mention another important branch using domain theory [START_REF] Escard | PCF extended with real numbers[END_REF][START_REF] Edalat | Domains for computation in mathematics, physics and exact real arithmetic[END_REF][START_REF] Blanck | Domain representations of topological spaces[END_REF].

Countably-based spaces

The standard way of representing a real number x is by giving a sequence of rational numbers converging at a certain fixed rate to x. Any such sequence can be encoded as an element of N N and is called a name of x. A function f : R → R is then computable if there is a Turing machine converting any name of any x ∈ R to a name of f (x). One of the earliest results in computable analysis is that every computable function is continuous. It implies for instance that no non-trival subset of R is decidable because it should be clopen. Similarly, the semidecidable subsets of R are exactly the effective open sets, i.e. the open sets that can be expressed as computable unions of open intervals with rational endpoints.

The relationship between computability and continuity has been taken for granted and has suggested a standard way of representing points in an arbitrary topological space with a countable basis: a point x is represented by any list of (indices of) the basic neighborhoods of x. With this representation, every computable function is continuous and moreover a function is continuous if and only if it is computable relative to some oracle. Similarly, the semidecidable sets are the effective open sets (i.e., the unions of computable sequences of basic open sets) and a set is open if and only if it is semidecidable relative to some oracle.

Thus for countably-based spaces with the standard representation, the situation is pretty clear and the solution to Problem 1 is:

Solution to Problem 1. The semidecidable properties are the computable unions of basic open sets.

Therefore, the answer to Problem 2 is as simple as possible: there is computable enumeration of the semidecidable properties, derived from a computable enumeration of the c.e. subsets of N, so one can take A = N.

Solution to Problem 2. The minimal complexity is ∆ 0 1 .

Examples of countably-based spaces are:

-The real numbers with the Euclidean topology, generated by the rational open intervals: the standard representation is equivalent to the Cauchy representation.

-The Baire space N N , or space of total functions from N to N with the product topology induced by the cylinders: the standard representation is equivalent to the trivial representation, where each f : N → N is a name of itself, -The partial functions from N to N, with the Scott topology induced by the cylinders.

For a complete development of computable analysis on countably-based spaces, we refer the reader to [START_REF] Weihrauch | Computable Analysis[END_REF].

Markov computability

In Markov's school of recursive constructive mathematics, a real number is a program computing a Cauchy sequence of rationals converging at a certain fixed rate. A function on real numbers is Markov computable if there is a procedure that transforms a program for the input into a program for the output. The comparison of this notion with the more standard notion of computable function (defined in Section 1) has been thoroughly studied in the 50's.

When the inputs are the partial computable functions, having a program (or an index, or Gödel number) for the input or a standard name makes no difference: the decidable and semidecidable properties are the same (Rice and Rice-Shapiro theorems), the computable functionals are the same (Myhill-Shepherdson theorem).

When the inputs are the total computable functions or the computable real numbers, having a program for the input or a name makes no difference when computing a total functional or deciding some property (Kreisel-Lacombe-Schoenfield/Ceitin Theorem), however it does make a difference when computing a partial functional or semideciding some property (Friedberg). Let us give an example of a property of total computable functions f that is Markov semidecidable (i.e., semidecidable from any index of f ) but not semidecidable from f itself. Let (ϕ e ) e∈N be some canonical effective numbering of the partial computable functions. The property of function f is: for all n, there exists e ≤ n such that ϕ e coincides with f on inputs 0, . . . , n.

So Problem 1 arises here: what do the Markov semidecidable properties of total computable functions look like?

More generally, what exactly can be computed given an index, that cannot be computed given a name? What additional information does the index contain? We first show that the only additional information is an upper bound on the index. If X is a countably-based space and δ its standard representation, then let X c be the set of computable points of X (the points that have a computable name),

-Let δ M be the Markov representation, representing a point x ∈ X c by any index of a computable name of x, -And let δ K be the representation of X c that represents a point x by a standard name of x and any upper bound on an index of x. One can think of this upper bound as an upper bound on the Kolmogorov complexity of the point, or as giving a finite list of programs such that one of them computes the point.

Theorem 1 ([10]

). Let X be an effective topological space. A subset of X c is Markov-semidecidable iff it is semidecidable given a standard name and an upper bound on any index.

More generally, the representations δ and δ K induce the same properties that are decidable with at most n mind changes (for any fixed n ∈ N) and the same Σ 0 2 properties.

For k ≥ 3, the representations δ, δ K and δ M induce the same Σ 0 k properties, simply because X c is a Σ 0 3 -set. Is it possible to have a concrete description of the Markov semidecidable properties? To date Problem 1 remains open, however we now give a solution to Problem 2.

A property is Markov semidecidable if there exists a c.e. set W ⊆ N that is extensional, i.e. if ϕ i = ϕ j is total then i ∈ W ⇐⇒ j ∈ W . The set {e ∈ N : W e is extensional} is a Π 0 3 -set and immediately induces an indexing of the Markov semidecidable properties, so the complexity of describing the Markov semidecidable properties is at most Π 0 3 . We recently proved that this bound is optimal.

Theorem 2 ([11]

). There is no Σ 0 3 -indexing of the Markov semidecidable properties of total computable functions.

The proof is based on a diagonalization, but requires several technical obstacles to be overcome. It follows the same structure as the proof of Theorem 5 below.

Thus,

Solution to Problem 2. The minimal complexity of an indexing of the Markov semidecidable properties of total computable functions is Π 0 3 .

Finite advice

Let X be a set with a representation. In many situations, an algorithm taking points of X as inputs needs an additional finite information about the input to perform a given task. Computations with finite advice have been studied in details by Ziegler [START_REF] Ziegler | Real computation with least discrete advice: A complexity theory of nonuniform computability with applications to effective linear algebra[END_REF]. Without loss of generality, that finite information is a natural number. If we denote by X n ⊆ X the set of points for which n ∈ N is a correct advice, then one has X = n∈N X n , and we define a new representation by describing a point x ∈ X by a name of x together with any n such that x ∈ X n .

If we understand the former representation, can we understand the new one?

Example 1. A polynomial is represented as an infinite sequence of real numbers (its coefficients) and an upper bound on its degree. Giving the coefficients only, without an upper bound on the degree, would make evaluation uncomputable (a precise account on the difficulty of bounding the degree from the coefficients can be found in [START_REF] Pauly | Comparing representations for function spaces in computable analysis[END_REF]). The representation only gives an upper bound on the degree, because giving the exact degree would make simple operations such as addition uncomputable. We denote this representation by δ poly .

Example 2. We saw that representing a computable object by an index is equivalent to representing it by a name plus an upper bound on an index of the object, in the sense that the two representations induce the same semidecidable properties.

Example 3. Given a random sequence s ∈ {-1, 1} N , the random harmonic series n∈N sn n converges and the sum can be uniformly computed from s and an upper bound on its randomness deficiency (it is layerwise computable, see [START_REF] Hoyrup | An application of Martin-Löf randomness to effective probability theory[END_REF]).

We give an answer to Problem 1 in a particular case. Theorem 3. Let (X, d) be a computable metric space such that X = n X n where X n are uniformly effective compact sets. When representing points x by pairs (p, n) where p is a Cauchy name of x and n is such that x ∈ X n , the semidecidable properties are:

-The basic open metric balls, -The set {x : ∀n, d(x, X n ) < n }, where ( n ) n∈N is any computable sequence of positive rationals, -Effective unions of finite intersections of these properties. This result is unpublished, but its proof in a particular case appears in [START_REF] Hoyrup | The decidable properties of subrecursive functions[END_REF].

So we obtain a concrete description of the semidecidable properties, solving Problem 1. It implies a solution to Problem 2: there is a Π 0 2 -indexing of the semidecidable properties (the computable sequences of positive rationals can be enumerated from a Π 0 2 -set). Whether this complexity is optimal depends on the decomposition (X n ) n∈N .

Solution to Problem 1. A polynomial is a sequence of coefficients c n ∈ R that is eventually null. The properties of polynomials that are semidecidable w.r.t. δ poly are:

-Given a rational interval (a, b) and n ∈ N, whether c n ∈ (a, b), -Given a positive sequence ( n ) n∈N , whether c n < n for all n, -Effective unions of finite intersections of these properties.

Unfortunately, Theorem 3 does not apply to Example 2, i.e. to the Markov semidecidable properties of total computable functions. Indeed, the set X n of total computable functions having an index smaller than n, although effectively compact, is not so uniformly in n. However when considering subrecursive classes rather than arbitrary total computable functions, one ends up with a uniformly effective compact decomposition to which Theorem 3 can be applied, as we now show.

Subrecursive classes of functions. Let PR ⊆ N N be the set of primitive recursive functions. For the purpose of semideciding a property, it can be easily shown that having a primitive recursive definition of f ∈ PR is equivalent to having a direct access to f and an upper bound on an arbitrary primitive recursive definition of f , thus we are in the case of Theorem 3 where PR n is the set of functions having a primitive recursive definiton of length at most n (for any reasonable measure of length).

Solution to Problem 1 ([15]

). The semidecidable properties of primitive recursive functions are:

-Given a, b ∈ N, whether f (a) = b, -Given a computable non-decreasing unbounded function h, whether for all n there exists a primitive recursive definition of length ≤ h(n) compatible with f on inputs 0, . . . , n, -Effective unions of finite intersections of these properties.

This result actually holds for any subrecursive class, i.e. any class C of total computable functions that admits a sound and complete programming language, i.e. a decidable language L ⊆ Σ * (where Σ is some finite alphabet) with computable semantics, i.e. with a computable surjective map from L to C. Again, for the purpose of semideciding a property of functions, having a program w ∈ L of f is equivalent to having a direct access to f and an upper bound on the length of any program w ∈ L for f .

Examples of subrecursive classes are: the polynomial-time computable functions, the elementary functions, the computable functions that are provably total in Peano Arithmetic, etc.

All the details and proofs of the results in this section can be found in [START_REF] Hoyrup | Results in descriptive set theory on some represented spaces[END_REF].

So far, we have given results about semidecidable properties only, but it is possible to consider other classes of properties. In N N , the semidecidable properties are the effective open sets, or the Σ 0 1 -sets from the effective Borel hierarchy. This hierarchy provides different levels of computability of properties.

Any space X with a representation δ X :⊂ N N → X automatically inherits the effective Borel hierarchy: say that A ⊆ X is a Σ 0 n -subset of X if there exists a Σ 0 n -subset P of N N such that δ -1 X (A) = P ∩ dom(δ X ). With this definition, the semidecidable properties are exactly the Σ 0 1 -subsets of X. Then Problems 1 and 2 can also be formulated for Σ 0 n -properties. For usual countably-based spaces such as R, or any effective Polish space [START_REF] Brattka | Effective borel measurability and reducibility of functions[END_REF] or quasi-Polish space [START_REF] De Brecht | Quasi-polish spaces[END_REF], the effective Borel hierachy over X behaves nicely: the Σ 0 n -subsets of X are the computable unions of (differences of) Π 0 n-1 -sets, so they can be inductively described (solving Problem 1) and effectively enumerated from N (i.e., solution to Problem 2 is trivial).

We will see that some other spaces are not so well-behaved. -Given an effective compact set K ⊆ N N , whether K ⊆ U , -Effective unions of these properties.

An effective compact set can be obtained as {f : f ≤ g} \ V , where g is computable and V is an effective open set. In particular there is a Π 0 2 -indexing of the semidecidable properties, and this is optimal.

Therefore the semidecidable or Σ 0 1 properties are well-understood. However understanding the Σ 0 2 properties is an open problem. Contrary to what happens on Polish or quasi-Polish spaces, they cannot all be obtained as countable unions of differences of Π 0 1 -sets, and more generally as countable boolean combinations of open sets. We formalize it by using the notion of Borel set, for which some explanation is needed first.

The representation on the space O(N N ) induces a topology. Observe that this standard notion of Borel sets should not be confused with the one derived from the representation, consisting of the sets having a Borel pre-image. The following result shows in particular that the notion derived from the representation is strictly more restrictive than the standard notion. Theorem 4. There exists a Σ 0 2 -subset of O(N N ) that is not Borel. An ingredient of the proof is to show that the evaluation map Eval : N N × O(N N ) → S, which is known to be discontinuous for the product topology on N N × O(N N ) as N N is not locally compact (see [START_REF] Escardó | Topologies on spaces of continuous functions[END_REF] for instance), is not even Borel. Said differently, the set {(f, U ) : f ∈ U } is not a Borel subset of the space N N ×O(N N ) with the product topology. However, that set is open in the induced by the representation. In general, the topology induced by the representation on a product space is not in general the product topology but a stronger topology, except for countably-based spaces. Here, O(N N ) is not countably-based and the set {(f, U ) : f ∈ U } is an example of a set that discriminates between the two topologies.

If K ⊆ N N is compact then the set {U ∈ O(N N ) : K ⊆ U } is
Problems 1 and 2 for the Σ 0 2 -subsets of O(N N ) are still to be studied.

Kleene-Kreisel functionals

The previous space is similar to the space of continuous partial functionals from N N to N. We now consider the continuous total functionals from N N to N. Such a functional F : N N → N is represented by a list of pairs ([u], n) such that the value of F on [u] is n (we do not require to list all such pairs, but a list that covers the whole space N N ). What are the semidecidable properties of functionals? What are the open subsets of N N N ? These questions are difficult and we do not have an answer so far. This topological space is not well-understood, although some of its properties are known [START_REF] Schröder | The sequential topology on N N N is not regular[END_REF]. We give a solution to Problem 2, which also classifies this space in terms of its base-complexity as defined in [START_REF] De Brecht | Base-complexity classifications of qcb0spaces[END_REF].

Theorem 5. There is no continuous surjection from N N N to O(N N N ).

There is no Σ 1 2 -indexing of the semidecidable properties of functionals from N N to N.

However there is a straightforward Π 1 2 -indexing of the semidecidable properties, which is optimal by the previous result, solving Problem 2.

Solution to Problem 2. The minimal complexity of an indexing of the semidecidable subsets of

N N N is Π 1 2 .
The proof of Theorem 5 (and Theorem 2) is based on a diagonalization, but several technical problems have to be overcome. Let us briefly explain how it works.

The diagonal argument is very simple: if Y admits a fixed-point free function then there is no surjection from X to Y X , because given φ : X → Y X one can build f (x) = h(φ(x)(x)) which is not in the range of φ. In this general form, all set-theoretic functions are considered, but it applies as is to subclasses of functions: there is no continuous surjection from X to the space C(X, Y ) of continuous functions from X to Y (for the suitable topologies). In other words, the argument applies in any cartesian-closed category (this general formulation was done by Lawvere in [START_REF] Lawvere | Diagonal arguments and cartesian closed categories[END_REF]). In order apply it to X = N N N and Y = O(N N N ), two problems have to be overcome:

-For any Z, every continuous function h : O(Z) → O(Z) is Scott continuous hence has a fixed-point by the Kleene fixed-point theorem. However we show that there is a continuous multi-valued function h : O(N N N ) ⇒ O(N N N ) that has no fixed-point, i.e. such that U / ∈ h(U ) for all U ∈ O(N N N ). -But then the diagonal argument only produces a multi-valued function, and not a function, unless X is the Baire space or a subspace of it (a continuous multi-valued function defined on a subset of the Baire space always admits a continuous selection function). It happens that N N N cannot be embedded into N N . However we show a way of extending the argument to spaces X that contain a sufficiently rich closed set that can be embedded into the Baire space. We show that N N N satisfies this property, hence there is no continuous surjection from

N N N to C(N N N , O(N N N )) ∼ = O(N N N × N N N ) ∼ = O(N N N ).
Higher order functionals can be generalized to any finite type:

-N 0 = N, -N k + 1 = N N k ,
In the same way, we show that there is no continuous surjection from N k to O(N k ), and that there is no indexing of the semidecidable subsets of N k from any Σ 1 k -subset of N. The hierarchy of continuous functionals can be extended to the countable ordinals by adding:

-N λ = α<λ N α for a limit countable ordinal λ (where some enumeration of the ordinals below λ is fixed).

We can then prove that for each countable ordinal α, there is no continuous surjection from N α to O(N α ). An effective version for the constructive ordinals probably holds, but we did not investigate it.

4. 1

 1 Open subsets of the Baire space Here the objects are the open subsets of N N . The space of these open subsets is denoted by O(N N ). An open subset of N N is naturally represented by any list of cylinders whose union is the open set. For this space, Problems 1 and 2 have a simple solution. The semidecidable properties of open sets U ⊆ N N are:

  an open subset of O(N N ), and the topology on O(N N ) is generated by all these sets where K ranges over the compact subsets of N N . As a topological space, O(N N ) has a notion of Borel subset: the class of Borel subsets of O(N N ) is the smallest class of sets containing the open sets and closed under taking complements and countable unions. In this sense, the Borel sets can be seen as countable boolean combinations of open sets.