Mathieu Hoyrup

Irreversible computable functions

The strong relationship between topology and computations has played a central role in the development of several branches of theoretical computer science: foundations of functional programming, computational geometry, computability theory, computable analysis. Often it happens that a given function is not computable simply because it is not continuous. In many cases, the function can moreover be proved to be non-computable in the stronger sense that it does not preserve computability: it maps a computable input to a non-computable output. To date, there is no connection between topology and this kind of non-computability, apart from Pour-El and Richards "First Main Theorem", applicable to linear operators on Banach spaces only.

In the present paper, we establish such a connection. We identify the discontinuity notion, for the inverse of a computable function, that implies non-preservation of computability. Our result is applicable to a wide range of functions, it unifies many existing ad hoc constructions explaining at the same time what makes these constructions possible in particular contexts, sheds light on the relationship between topology and computability and most importantly allows us to solve open problems. In particular it enables us to answer the following open question in the negative: if the sum of two shift-invariant ergodic measures is computable, must these measures be computable as well? We also investigate how generic a point with computable image can be. To this end we introduce a notion of genericity of a point w.r.t. a function, which enables us to unify several finite injury constructions from computability theory.

Introduction

Many problems in classical computability theory [START_REF] Jr | Theory of Recursive Functions and Effective Computability[END_REF] and computable analysis [START_REF] Pour-El | Computability in Analysis and Physics[END_REF][START_REF] Weihrauch | Computable Analysis[END_REF] amount to studying the computability of some function f defined on continuous spaces such as the Cantor space or the space of real numbers. One is usually interested in three increasingly stronger notions of computability for f : (i) f (x) is computable for every computable x;

(ii) f (x) is computable relative to x for every x;

(iii) f (x) is computable relative to x for every x, uniformly in x.

In the first case we say that f is computably invariant (terminology introduced in [START_REF] Brattka | Computable invariance[END_REF]). In the third case we simply say that f is computable. It happens that many interesting functions are not computable and even not computably invariant. For instance Braverman and Yampolsky proved in [START_REF] Braverman | Non-computable Julia sets[END_REF] that the function mapping a parameter to the corresponding Julia set does not satisfy (ii); they later strengthened that result in [BY07] by proving that it does not satisfy (i) either. By contrast, the function mapping a parameter to the corresponding filled Julia set does satisfy condition (ii), while it does not satisfy (iii) because it is discontinuous [BY08].

While functions that are not computable often fail to be computably invariant, the proof of the former is usually much simpler than the proof of the latter. Indeed, it is often based on the fundamental result that a computable function must be continuous. Hence proving that a function is not computable is often a purely topological argument.

However proving that a function is not computably invariant is usually much more challenging, as a counterexample must be constructed, by encoding the halting set or by using more involved computability-theoretic arguments based on priority methods, e.g. Our point is that topology is still at play in many computability-theoretic constructions1 . Usually the construction of a computable element whose image is not computable implicitly makes use of the discontinuity of the function. Of course mere discontinuity is not sufficient in general to carry out such a construction: there exist discontinuous functions that are computably invariant, such as the floor function or the function that maps a real number to its binary expansion. More is needed and our question is: what discontinuity property is needed to make such a construction possible?

Such discontinuity properties have already been sought by several authors. Pour-El and Richards "First Main Theorem" [START_REF] Pour-El | Computability in Analysis and Physics[END_REF] shows that in the case of linear operators with c.e. closed graph, if the operator is unbounded (i.e., discontinuous) then it is not computably invariant (it is actually an equivalence). Their result subsumes many ad hoc constructions, such as Myhill's differentiable computable function whose derivative is not computable [Myh71]. As part of their open problem no. 7, Pour-El and Richards ask whether their First Main Theorem can be extended to nonlinear operators. A generalization of their theorem to certain algebraic structures was proved by Brattka [START_REF] Brattka | Computable invariance[END_REF], applicable to operators on the set of compact subsets of R.

In these results, the underlying algebraic structures enable the authors to provide counterexamples via explicit expressions (such as linear combinations of basic elements with well-chosen weights) by encoding the halting set, which contrasts with many situations in computability theory where explicit constructions are rarely possible and priority methods are often needed to build counterexamples (Friedberg-Muchnik construction of Turing incomparable c.e. sets, e.g.). This observation allows one to hope for stronger results whose proofs involve more complicated, non-explicit constructions.

In this paper we present such a result, applicable to inverses of computable functions. We work on effective topological spaces and effective Polish spaces without additional structure, which makes our result applicable in many situations. We introduce a topological notion, irreversibility of a function, whose effective version entails the existence of a non-computable point whose image is computable. We think that this notion is rather simple to verify on particular instances. The proof of the result implicitly uses the priority method with finite injury. We think that our discontinuity notion is rather natural and, in concrete situations, much easier to verify than constructing a computable element whose pre-image is not computable. In other words, our result is not merely an abstract generalization of existing constructions, but a powerful theorem that provides insight into computability theory, as illustrated by the numerous examples we give.

This work was originally motivated by the following question, left open in [START_REF] Hoyrup | Randomness and the ergodic decomposition[END_REF]: are there two non-computable shift-invariant ergodic measures whose sum is computable? As an application of our main result, we positively answer this question.

We push our investigation further by studying the following question: how non-computable can a point with a computable image be? We introduce a notion of genericity of a point w.r.t. a function and prove that generic points with computable images exist. The construction unifies several finite injury arguments.

The paper is organized as follows: in Section 2 we introduce basic notions of computable analysis; in Section 3 we introduce a notion of continuous invertibility at a point and prove that for "almost" every point, if a function is computably invertible at that point then it is continuously invertible there (Theorem 3.1). In Section 4 we introduce the notion of an irreversible function, which in substance expresses that a function is topologically hard to inverse. In Section 5 we present our main result: a function that is topologically hard to inverse is computably hard to inverse, in particular it maps a non-computable point to a computable image. In Section 5.1 we present an application of our main result to the non-computability of the ergodic decomposition. In Section 6 we introduce a notion of genericity w.r.t. a function which unifies several finite injury constructions.

Background and notations

We assume familiarity with basic computability theory on the natural numbers. We implicitly use Weihrauch's notions of computability on effective topological spaces, based on the standard representation (see [START_REF] Weihrauch | Computable Analysis[END_REF] for more details), however we do not express them in terms of representations.

Notations

In a metric space (X, d), if x ∈ X and r ∈ (0, +∞) then we denote the open ball with center x and radius r by B(x, r) = {x ′ ∈ X : d(x, x ′ ) < r}. We denote the corresponding closed ball by B(x, r) = {x ′ ∈ X : d(x, x ′ ) ≤ r}. The Cantor space of infinite binary sequences, or equivalently subsets of N, is denoted by 2 N . The halting set, denoted ∅ ′ , is the set of numbers of Turing machines that halt. It is a noncomputable set that is computably enumerable (c.e.).

Effective topology

An effective topological space (X, τ, B) consists of a topological space (X, τ ) together with a countable basis B = {B 0 , B 1 , . . .} numbered in such a way that the finite intersection operator is computable. An open subset U ⊆ X is effectively open if U = k∈W B k for some c.e. set W ⊆ N.

To a point x ∈ X we associate N (x) = {n ∈ N : x ∈ B n }. By an enumeration of N (x) we mean a total function f : N → N whose range is N (x). A point x is computable if N (x) is c.e., i.e. if N (x) has a computable enumeration.

Given points x, y in effective topological spaces X, Y respectively, we say that y is computable relative to x if there is an oracle Turing machine M that, given any enumeration of N (x) as oracle, outputs an enumeration of N (y). We denote it by M x = y. In other words, y is computable relative to x if N (y) is enumeration reducible to N (x). As proved by Selman [Sel71] and pointed out by Miller [Mil04], y is computable relative to x if and only if every enumeration of N (x) computes an enumeration of N (y) (uniformity is not explicitly required, but is a consequence).

A (possibly partial) function f : X → Y is computable if there is a machine M such that for every x ∈ dom(f ), M x = f (x). A computable function is always continuous.

Effective Polish spaces

An effective Polish space is a topological space such that there exists a dense sequence s 0 , s 1 , . . . of points, called simple points and a complete metric d inducing the topology, such that all the reals numbers d(s i , s j ) are computable uniformly in (i, j). Every effective Polish space can be made an effective topological space, taking as canonical basis the open balls B(s, r) with s simple point and r positive rational together with a standard effective numbering.

In an effective Polish space, a point x is computable if and only if for every ǫ > 0 a simple point s can be computed, uniformly in ǫ, such that d(s, x) < ǫ.

We will be concerned with computability and Baire category, so we will naturally meet the notion of a 1-generic point: a point that does not belong to any "effectively meager set" in the following sense.

Definition 2.1. x ∈ X is 1-generic if x does not belong to the boundary of any effective open set. In other words, for every effective open set U , either x ∈ U or there exists a neighborhood B of x disjoint from U .

By the Baire category theorem, every Polish space is a Baire space so 1-generic points exist and form a co-meager set.

A non-uniform result

Let X be an effective Polish space, Y an effective topological space and f : X → Y a (total) computable function.

To introduce informally the results of this section, assume temporarily that f is one-toone. If f -1 is computable, i.e. if every x is computable relative to f (x) uniformly in x, then f -1 is continuous. As mentioned earlier uniformity is crucial here: that some x is computable relative to f (x) does not imply in general that f -1 is continuous at f (x). Theorem 3.1 below surprisingly shows that a non-uniform version can still be obtained, valid at most points.

Let us now make it precise and formal. We do not assume anymore that f is one-to-one. When focusing on the problem of inverting a function, one comes naturally to the following basic notions:

• f is invertible at x if x is the only pre-image of f (x),
• f is locally invertible at x if x is isolated in the pre-image of f (x).

If one has access to x via its image only, then x is determined unambiguously in the first case, with the help of a discrete advice (a basic open set isolating x) in the second case. However, "being uniquely determined" is not sufficient in practice: physically or computationally, one cannot know entirely f (x) in one step, but progressively as a limit of finite approximations. We need to consider stronger, topological versions of the two basic notions of invertibility, expressing that x can be recovered from the knowledge of its image given by finer and finer neighborhoods.

Definition 3.1. Let f : X → Y be a function.
We say that f is continuously invertible at x if the pre-images of the neighborhoods of f (x) form a neighborhood basis of x, i.e. for every neighborhood U of x there exists a neighborhood

V of f (x) such that f -1 (V ) ⊆ U .
We say that f is locally continuously invertible at x if there exists a neighborhood B of x such that the restriction of f to B is continuously invertible at x, i.e. for every neighborhood U of x there exists a neighborhood

V of f (x) such that B ∩ f -1 (V ) ⊆ U .
Observe that these notions are very natural when investigating the problem of inverting a function: we think that they are not technical ad hoc conditions.

Every effective topological space Y has a countable basis hence is sequential, i.e. continuity notions can be expressed in terms of sequences, which may be more intuitive. We will be particularly interested in the negations of these notions, which we characterize now. Proposition 3.1. f is not continuously invertible at x if and only if there exist δ > 0 and a sequence x n such that d(x, x n ) > δ and f (x n ) converges to f (x).

f is not locally continuously invertible at x if and only if for every ǫ > 0 there exist δ > 0 and a sequence x n such that ǫ > d(x, x n ) > δ and f (x n ) converges to f (x).

Let us illustrate these notions on a few examples.

Example 1. If f is one-to-one then f is continuously invertible at x if and only if f -1 is continuous at f (x).
Example 2. The real function f (x) = x 2 is continuously invertible exactly at 0, and locally continuously invertible everywhere (for x = 0 take for B an open interval avoiding 0).

Example 3. The projection π 1 : 2 N → 2 N which maps A 1 ⊕A 2 = {2n : n ∈ A 1 }∪{2n+1 : n ∈ A 2 } to A 1 is not locally continuously invertible anywhere. Indeed, given A 1 , A 2 ∈ 2 N , A 1 ⊕ A 2 is not isolated in the pre-image by π 1 of A 1 = π 1 (A 1 ⊕ A 2 ).
Example 4. Let X be the Cantor space 2 N with the product topology τ generated by the cylinders [u], u ∈ 2 * , Y be the Cantor space with the positive topology τ Scott generated by the sets {A ⊆ N : F ⊆ A} where F varies among the finite subsets of N. The computable elements of the two effective topological spaces are the computable sets and the c.e. sets respectively. Consider the enumeration operator Enum := id : X → Y . Enum is computable and one-to-one but its inverse is discontinuous. More precisely, (i) it is continuously invertible exactly at N, (ii) it is locally continuously invertible exactly at the co-finite sets: if A is co-finite then let B be a cylinder specifying all the 0's in A, every cylinder containing A is the intersection of a Scott open set with B.

In general continuous invertibility at a point is strictly stronger than local continuous invertibility. This is not the case for linear operators, where a dichotomy appears. Following Pour-El and Richards [START_REF] Pour-El | Computability in Analysis and Physics[END_REF], by a linear operator T : X → Y between Banach spaces we mean a linear function T : D(T ) → Y where D(T ) is a subspace of X.

Proposition 3.2. Let X, Y be Banach spaces and T : X → Y a one-to-one linear operator.

• If T -1 is bounded then T is continuously invertible everywhere.

• If T -1 is unbounded then T is nowhere locally continuously invertible.

Proof. The first point simply follows from the fact that T -1 is continuous. Assume that T -1 is unbounded. There exists a sequence a n ∈ X such that a n = 1 and T (a n ) → 0. Let x ∈ X and ǫ > 0. Take δ = ǫ/3 and define

x n = x + 2δa n : T (x n ) converges to T (x) and ǫ > x -x n > δ for all n.
Observe that in the case when T is not one-to-one, T is also nowhere locally continuously invertible, with exactly the same proof (one can take a n = a for some a with a = 1 and T (a) = 0).

We now come to our first result.

Theorem 3.1. Let f : X → Y be a computable function and x ∈ X a 1-generic point. If x is computable relative to f (x) then f is locally continuously invertible at x.

Proof idea. Assume that f is not locally continuously invertible at x and that there is a Turing machine M that computes x on oracle f (x). We show that x belongs to the boundary of an effective open set U , i.e. that x is not 1-generic. Given a point y, there are two possible ways in which a machine may fail to compute y from f (y): either it diverges, or it outputs something that is incompatible with y. The latter can be recognized in finite time: we then say that M f (y) positively fails to compute y. Our effective open set U is the set of points y such that M f (y) positively fails to compute y.

First, if f is not continuously invertible at x, there exists δ > 0 and a sequence x n such that d(x n , x) > δ and f (x n ) converges to f (x). If n is sufficiently large then f (x n ) is arbitrarily close to f (x) so M f (xn) computes an arbitrarily refined approximation of x. If we take n so large that M f (xn) computes x at precision < δ/2, then M f (xn) positively fails to compute x n so x n belongs to U . Now, if f is not locally continuously invertible at x then x n can be taken arbitrarily close to x, so x belongs to the closure of U .

In the sequel we introduce a condition on f which roughly means that f is "almost nowhere" locally continuously invertible and that entails (i) the existence of an x that is not computable relative to f (x) (Theorem 4.1) and, better, (ii) the existence of a non-computable x such that f (x) is computable (Theorem 5.1).

Reversibility

We define two dual notions for a function: reversibility (Section 4.1) and irreversibility (Section 4.2). In the sense of Baire category, a reversible function is continuously invertible almost everywhere; an irreversible function is almost nowhere locally continuously invertible.

Reversible functions

Let X, Y be T 0 topological spaces. For a continuous function f : X → Y , the following are equivalent:

• f is one-to-one and f -1 : f (X) → X is continuous,
• the initial topology of f is the topology of X, i.e. for every open set U ⊆ X there exists an open set V ⊆ Y such that U = f -1 (V ).

A function satisfying these conditions can be reversed in the sense that x can be recovered from f (x) for every x: x is not only uniquely determined by f (x), but a neighborhood basis of x can be progressively constructed from a neighborhood basis of f (x).

We first consider a slight weakening of this notion.

Definition 4.1. We say that f is reversible if for every non-empty open set

U ⊆ X there is an open set V ⊆ Y such that ∅ = f -1 (V ) ⊆ U . We say that f is effectively reversible if V = V U can moreover be computed from U (basic open set).
Proposition 4.1. If f is continuous and reversible then it is continuously invertible at every point in a dense G δ -set.

If f is computable and effectively reversible then there is a dense effective G δ -set D such that f |D is one-to-one and its inverse is computable on f (D), i.e. x is uniformly computable from f (x) when x ∈ D.

Proof. Assume that f is reversible. For each basic ball U ⊆ X there exists

V U ⊆ Y such that ∅ = f -1 (V U ) ⊆ U . Let W n be the union of f -1 (V U ) over all basic balls U of radius < 2 -n . W n is a dense open set. If x ∈ W n
for all n then f is continuously invertible at x. Indeed, for every n there exists a ball

U of radius < 2 -n such that x ∈ f -1 (V U ) ⊆ U .
If f is effectively irreversible then the sets are W n are uniformly effective open sets and if x ∈ n W n then for each n there exists a basic ball U of radius < 2 -n such that f (x) ∈ V U , which can be found from any enumeration of N (f (x)). It gives an approximation of x within 2 -n .

In particular if x is 1-generic then x is computable relative to f (x).

Irreversible functions

We now consider the dual notion: an irreversible function is a function that is not reversible, not even locally.

V satisfying ∅ = f -1 (V ) ∩ B ⊆ U B .
In other words, each pre-image of an open set that intersects B does so outside U B . If x ∈ U B then we will never know it from f (x), even with the help of the advice x ∈ B.

Observe that one can assume w.l.o.g. that f -1 (V ) ∩ B U B . Indeed, one can replace U B by some ball B(s, r) such that B(s, r) ⊆ U B .

An application of an irreversible function f to x comes with a loss of information about x, that can hardly be recovered. Being irreversible is orthogonal to not being one-to-one: the function x → x 2 is not one-to-one but not irreversible: x can be (continuously or computably) recovered from x 2 ; a one-to-one function can be irreversible if its inverse is dramatically discontinuous (examples of such functions will be encountered in the sequel).

In terms of sequences, f is irreversible if and only if for every B there exists a non-empty open set U B ⊆ B such that for every x ∈ U B there is a sequence

x n ∈ B \ U B such that f (x n ) converges to f (x).
As announced, the set of points at which an irreversible function is locally continuously invertible is small in the sense of Baire category.

Proposition 4.2. Let f be irreversible. There is a dense G δ -set D such that f is not locally continuously invertible at any x ∈ D.

Proof. Let W n be the union of U B for all basic open sets B of radius < 2 -n . W n is a dense open set. Let x ∈ n W n . For each n there is a ball of radius < 2 -n such that x ∈ U B . For every neighborhood V of f (x), x ∈ f -1 (V ) ∩ B = ∅ so f -1 (V ) ∩ B U B .
In other words, for almost every x the application of f to x comes with a "topological information" loss.

The preceding proposition does not rule out the possibility that the restriction of f to a "large" set be continuously invertible (for instance, the characteristic function of the rational numbers is nowhere continuous, but its restriction to the co-meager set of irrational numbers is continuous). The next assertion shows that this is not possible. Example 5. Let f be a constant function defined on the Polish space X. f is irreversible if and only if X is perfect, i.e. has no isolated point.

Example 6. The first projection π 1 : 2 N → 2 N from Example 3 is irreversible. Indeed, to B = [w], associate U B = [w00]. The intersection with [w] of the pre-image of any cylinder cannot be contained in [w00]: knowing arbitrarily many bits of π 1 (A) and the first |w| bits of A does not give any information about the next odd bit of A, so it does not enable one to guess that A belongs to [w00].

In the definition of an irreversible function (Definition 4.2), B and U B can be assumed w.l.o.g. to be basic balls.

Definition 4.3. f is effectively irreversible if U B can be computed from B.
The following result is the effective version of Proposition 4.3.

Theorem 4.1. If f is effectively irreversible then for every 1-generic x, x is not computable relative to f (x).

Proof. The dense G δ -set provided by Proposition 4.2 is effective when f is effectively irreversible so it contains every 1-generic point. Hence for every 1-generic x, f is not locally continuously invertible at x. We now apply Theorem 3.1.

In other words, if x is 1-generic then the application of f to x comes with an "algorithmic information" loss. So if f is effectively irreversible then there exists some x that is not computable relative to f (x).

Examples

Several well-known results in computability theory can be interpreted using Theorem 4.1 as consequences of the effective irreversibility of some computable function. Example 8. The projection π 1 : 2 N → 2 N from Examples 3 and 6 is effectively irreversible. Applying Theorem 4.1 to π 1 and symmetrically to the second projection π 2 gives Jockush and Posner's result [JP78] that if A = A 1 ⊕ A 2 is 1-generic then A 1 and A 2 are Turing incomparable, which implies Kleene-Post theorem, taking a ∅ ′ -computable 1-generic set.

Example 9. Jockush [START_REF] Carl | Degrees of generic sets[END_REF] proved that every 1-generic A ∈ 2 N is c.e.a., i.e. A computes some B such that A is c.e. relative to B but not computable relative to B. The proof goes as follows: let

f (A) = { i, j : i ∈ A ∧ i, j /
∈ A} (where is a computable one-to-one pairing function such that i, j > i). f is computable, if A is 1-generic then A is c.e. in f (A) as i ∈ A ⇐⇒ ∃j, i, j ∈ f (A). We show that f is effectively irreversible, which by Theorem 4.1 implies that if A is 1-generic then A T f (A).

First observe that f is not one-to-one: given A and i such that i / ∈ A and i, 0 / ∈ A, there exists  = A such that f ( Â) = f (A). Add i, 0 to A, and each time some k is added, add all the pairs k, j that are not already in. One easily checks that f ( Â) = f (A). As a result, given a cylinder

B = [u], let U B = [u] ∩ {A : i / ∈ A and i, 0 / ∈ A}. For every A ∈ U B there is  ∈ B \ U B such that f ( Â) = f (A), so f -1 f (A) intersects B \ U B : knowing f (A) and that A ∈ B does not enable one to know that A ∈ U B .
Again, linear operators provide a large class of examples. An effective Banach space is a Banach space which is an effective Polish space with the metric induced by the norm, such that 0 is a computable point and the vector space operations are computable functions. Many classical Banach spaces R, C [0, 1] (with the uniform norm) or L 1 [0, 1] are effective Banach spaces.

Proposition 4.4. Let X, Y be effective Banach spaces and T : X → Y a computable linear operator. Assume that either T is not one-to-one or T is one-to-one and T -1 is unbounded. Then T is effectively irreversible. Proof. To a ball B = B(s, r) associate U B = B(s, r/2). According to the assumption about T , for every ǫ there exists a such that a = r/2 and T (a) < ǫ. For every x ∈ U B and ǫ > 0 there exists λ ∈ {-1, 1} such that r/2 ≤ d(x + λa, s) < r, i.e. x + λa ∈ B \ U B . Indeed, d(x + a, s) + d(xa, s) ≥ 2 a = r and d(x ± a, s) < r. Moreover, d(T (x ± λa), T (x)) < ǫ.

Example 10. Applying Proposition 4.4 and Theorem 4.1 to the integration operator that maps

f ∈ C [0, 1] to F : x → x 0 f (t) dt gives that if f ∈ C [0, 1] is 1-generic then f is not computable relative to its primitive F that vanishes at 0.
Example 11. Applying Proposition 4.4 and Theorem 4.1 to the canonical injection from C [0, 1] to L 1 [0, 1] gives that if f ∈ C [0, 1] is 1-generic then it is not computable relative to itself, as an element of L 1 [0, 1]. In other words, the description of f as an element of L 1 [0, 1] contains strictly less algorithmic information than the description of f as an element of C [0, 1].

Example 12. A function f : N → N can be described by enumerating its graph or by enumerating the complement of its graph. The former alternative gives in general strictly more information about the function than the latter. Let us make it precise.

Every function F with finite domain induces the cylinder [F ] of functions f : N → N extending F . The product topology on the Baire space B is generated by the cylinders. The negative topology is generated by the complements of the cylinders, as a subbasis. The identity id : (B, τ ) → (B, τ neg ) is computable: from f one can enumerate the cylinders that are incompatible with f , but the converse cannot be done. id is effectively irreversible: to a cylinder B = [F ], associate U B = [F ] ∪ {n → 0}] where n is fresh, i.e. not in the domain of F .

By Theorem 4.1, if f : N → N is 1-generic then it is not computable relative to every co-enumeration of its graph.

The constructive result

We now present the main result of the paper. It is the constructive version of Theorem 4.1 as it makes f (x) computable. The construction uses a priority argument with finite injury.

Theorem 5.1. If f is effectively irreversible then there exists a non-computable x such that f (x) is computable.

The proof is given in the appendix. The proof uses the priority method with finite injury, which can be seen as a game between a player, computing f (x), and infinitely many opponents (all the Turing machines) trying to compute x.

Application to the ergodic decomposition

We now present an application of Theorem 5.1. Let P be a Borel probability measure P over the Cantor space. P is computable if the real numbers P [w] are uniformly computable. P is shift-invariant if P [w] = P [0w] + P [1w] for each finite string w. P is ergodic if it cannot be written as P = 1 2 (P 1 + P 2 ) with P 1 = P 2 both shift-invariant.

The ergodic decomposition theorem says that every shift-invariant measure can be uniquely decomposed into a convex combination (possible uncountable) of ergodic measures. Our question is: given a computable shift-invariant measure, can we compute in a sense its ergodic decomposition? This question was implicitly addressed by V'yugin [V'y97] who constructed a counter example: a countably infinite combination of ergodic measures which is computable but not effectively decomposable. In [START_REF] Hoyrup | Randomness and the ergodic decomposition[END_REF] we raised the following question: does the ergodic decomposition become computable when restricting to finite combinations? As an application of Theorem 5.1, we solve the problem and prove that it is already non-effective in the finite case:

Theorem 5.2. There exist two ergodic shift-invariant measures P and Q such that neither P nor Q is computable but

P + Q is computable.
The strategy is as follows: the mapping (P, Q) → P + Q is computable, two-to-one on the space E × E of pairs of ergodic measures and we prove Theorem 5.3. The function (P, Q) → P + Q defined on E × E is effectively irreversible. which implies Theorem 5.2 applying Theorem 5.1. The proof of Theorem 5.3 is given in the appendix.

Genericity

Given an effectively irreversible function f ,

• Theorem 4.1 tells us that if x is 1-generic then x is not computable relative to f (x),

• Theorem 5.1 tells us that there exist non-computable x such that f (x) is computable.

The two results are "disjoint" in the sense that in general a single x cannot at the same time be 1-generic and have a computable image, except for some particular functions like constant functions. We raise the following question: is it possible to bring the two results closer together? How far can x be from being computable, given that f (x) is computable? How generic can x be?

We now give an answer to that question. We recall that a topological space always comes with an order called the specialization order : x ≤ y iff every neighborhood of x is also a neighborhood of y. x ≤ y means that if one describes x by listing its basic neighborhoods then one can never distinguish x from y. When the space is Hausdorff, the specialization order is trivial. Here ≤ denotes the specialization order on the target space Y of f . Definition 6.1.

x is f -generic if x is 1-generic in the subspace ↑ f x := {x ′ : f (x) ≤ f (x ′ )}. In other words, x is f -generic if for every effective open set U , either x ∈ U or there exists a neighborhood B of x such that B ∩ U ∩ ↑ f x = ∅.
For instance, taking the first projection π

1 : 2 N → 2 N of Example 8, A = A 1 ⊕A 2 is π 1 -generic iff A 1 is 1-generic relative to A 2 .
Here we focus on a few particular instances of this notion, when f is the identity from a space to itself with two different topologies. We will consider 1. the enumeration operator Enum = id : (2 N , τ prod ) → (2 N , τ Scott ) (Examples 4 and 7), 2. id : (2 N , τ prod ) → (2 N , τ lex ) where τ lex is generated by the sets {y ∈ 2 N : x < lex y} and 3. id : (CL(2 N ), τ hit-or-miss ) → (CL(2 N ), τ miss ). Here, CL(2 N ) is the set of non-empty closed subsets of the Cantor space. τ miss is generated by the sets U u = {P ∈ CL(2 N ) : P ∩[u] = ∅} where u ∈ 2 * . τ hit-or-miss is generated by the sets U u together with their complements. Definition 6.1 is instantiated as follows:

Definition 6.2. 1. A generic c.e. set x is a c.e. set that is 1-generic in the subspace {y ∈ 2 N : x ⊆ y}.

2. A generic left-c.e. real x is a left-c.e. real that is 1-generic in the subspace {y ∈ 2 N : x ≤ lex y}.

3. A generic Π 0 1 -class P is a Π 0 1 -class that is 1-generic in the subspace {Q ∈ CL(2 N ) : Q ⊆ P }.
Informally, a generic element belongs to every effective open set that is dense above it, for the corresponding specialization order (while a 1-generic elements belongs to every effective open set that is dense along it). The next result is the sought combination of Theorems 4.1 and 5.1. Theorem 6.1. There exists a co-infinite generic c.e. set, a co-infinite generic left-c.e. real and a generic Π 0 1 -class without isolated points. Proof idea (detailed in the appendix). Kurtz built a left-c.e. weakly 1-generic real (see [Nie09] for a proof). The construction actually gives a generic left-c.e. real. The construction of a generic c.e. set and of a generic Π 0 1 -class are exactly the same, replacing the lexicographic order ≤ lex by inclusion ⊆ of sets and reverse inclusion of classes respectively, which are the specialization orders of the corresponding topologies. Theorem 6.1 is indeed a strengthening of Theorem 5.1: in Theorem 3.1, the 1-genericity assumption can actually be weakened to f -genericity (at least in the particular functions under consideration). Proposition 6.1. In each one of the three cases, if x is generic inside ↑ f x and f is not locally continuously invertible at x then x is not computable.

Proof. Using compactness of the space, one can show that f is not locally continuously invertible at x iff x is not isolated in ↑ f x, i.e. x belongs to the closure of ↑ f x \ {x}. If x is computable then the complement of {x} is an effective open set, so x cannot be generic inside ↑ f x.

Let us illustrate the three notions on a few examples. Generic c.e. set. As the next result shows, Theorem 6.1 embodies simple finite injury arguments as Friedberg-Muchnik theorem, e.g. Proposition 6.2. Let A be a co-infinite generic c.e. set. A is hypersimple, A = A 1 ⊕ A 2 where A 1 and A 2 are Turing incomparable, A is not autoreducible.

Proof. Same argument as for 1-generic sets, observing that the involved open set is not only dense along A, but even above A. For instance, to prove that A 2 T A 1 , given a Turing functional φ, let

U = {A 1 ⊕ A 2 : ∃n, φ A 1 (n) = 0 ∧ A 2 (n) = 1}. If φ A 1 = A 2
then replacing a 0 in A 2 by a 1 arbitrarily far gives an element of U arbitrarily close to A 1 ⊕ A 2 that is above (i.e. is a superset of) A 1 ⊕ A 2 .

It happens that the co-infinite generic c.e. sets are exactly the p-generic sets defined by Ingrassia [START_REF] Ingrassia | P-genericity for Recursively Enumerable Sets[END_REF].

Generic left-c.e. real. Downey and LaForte [DL02] proved the existence of non-computable left-c.e. reals x all of whose presentations are computable: each prefix-free c.e. set A of finite binary strings satisfying w∈A 2 -|w| = x is actually a computable set. A corollary of a result of Stephan and Wu [START_REF] Stephan | Presentations of K-trivial reals and Ksolmogorov complexity[END_REF] is that any such real is weakly 1-random. It must even be a generic left-c.e. real. Proposition 6.3. If x is a non-computable left-c.e. real all of whose presentations are computable then x is a generic left-c.e. real.

Proof. Let U be an effective open set that does not contain x: we must find y > x such that [x, y) is disjoint from U . First replace U by V = U ∪ [0, x). Let A be a prefix-free c.e. set such that V = w∈A [w]. The set A <x = {w ∈ A : w < lex x} is a presentation of x hence it is computable, so A >x = {w ∈ A : w > lex x} = A \ A <x is c.e. hence := inf w∈A>x [w] is right-c.e. As x is not computable and x ≤ y, one has x < y and we get the result as [x, y) is disjoint from U .

Generic Π 0 1 -class.
Proposition 6.4. A generic Π 0 1 -class without isolated point has no computable member.

Proof. Let x be computable. Consider the collection U = {P : x / ∈ P }. U is an effective open set in the space (CL(2 N ), τ hit-or-miss ) (and even in the topology τ miss ). U is dense and better: for every P without isolated point, there exist Q ⊆ P in U arbitrarily close to P , so U is dense below P (here the specialization order is the reverse inclusion). As a result, if P is a generic Π 0 1 -class without isolated point then P belongs to U, i.e. x / ∈ P .

Verification. By construction one has B n+1 [s] ⊆ B n [s] and B n+1 [s] = U Bn[s] for sufficiently large n so B n [s] is a shrinking sequence. We call the settling time of n the minimal number s such that n s ′ ≥ n for all s ′ ≥ s.

We say that n ∈ ∅ ′ is a forward element if no element m < n is enumerated into ∅ ′ after the enumeration stage of n: in other words, the settling time of n coincides with its enumeration stage. As ∅ ′ is infinite, it has infinitely many forward elements.

Claim. For each n, B n [s] is a stationary sequence.

Proof. Let s be the settling time of n: B n [s] = B n [s 0 ] for all s ≥ s 0 . Let B n be its limit. B n is a shrinking sequence as well, let x be the member of its intersection. Observe that the sequence x[s] converges to x: given ǫ, let n be such that B n has radius < ǫ and s 0 be the settling time n: for all s ≥ s 0

, x[s] ∈ B n [s] = B n so d(x[s], x) < ǫ. Claim. f (x) is computable. Proof. We prove that a basic open set V k contains f (x) if and only if k is enumerated into the list L = s L s .
If k ∈ L s for some s, let n be a forward element which is enumerated at some stage s

′ ≥ s. x ∈ B n+1 = B n+1 [s ′ + 1] ⊆ f -1 (V s ′ +1 ) ⊆ f -1 (V s ) ⊆ f -1 (V k ). Now let V k be a basic neighborhood of f (x). Let i 0 be such that x ∈ O k,i 0 . As x[s] converges to x there is s such that x[s] ∈ O k,i 0 for all s ′ ≥ s. Let t = max(s, i 0 ): x[t] ∈ O k,i 0 ⊆ O k,t
so k must be added to the list at stage t + 1 or earlier.

Claim. ∅ ′ is computable relative to x.

Proof. Let p i be the increasing sequence of forward elements. ∅ ′ can be computed from the sequence p i and the (computable) enumeration of ∅ ′ .

From x one can inductively compute the sequence p i . First, p 0 is the minimal n such that x / ∈ B n+1 [0]. Once p i is known, let s be the stage at which p i is enumerated into ∅ ′ , i.e. n s = p i . p i+1 is the minimal n > p i such that x / ∈ B n+1 [s + 1].

B Proof of Theorem 5.3

Before proving the theorem, we need some preliminaries so show that E × E is an effective Polish space.

Let X be an effective Polish space. X ′ ⊆ X is an effective Polish subspace if it is an effective Polish space with the induced topology and such that the canonical injection from X ′ to X to be a computable homeomorphism. Alexandrov theorem gives a way to obtain Polish subspaces of a Polish space, and has an effective version, which we present now.

A set A is an effective G δ -set if there exists a family of uniformly effective open sets U n such that A = n U n . Such a set is c.e. if it contains a dense computable sequence. Examples of such sets are given by the computable Baire theorem [START_REF] Yasugi | Effective properties of sets and functions in metric spaces with computability structure[END_REF][START_REF] Brattka | Computable versions of Baire's category theorem[END_REF]: any dense effective G δ -set is a c.e. effective G δ -set.

Proposition B.1 (Effective Alexandrov Theorem). Every c.e. effective G δ -set is an effective Polish subspace of X.

We consider the space P(2 N ) of Borel probability measures over the Cantor space together with the complete metric

d(P, Q) = w∈{0,1} * 2 -|w| |P [w] -Q[w]|.
The finite rational combination of Dirac measures are dense in P(2 N ) and d is computable over them, so P(2 N ) is an effective Polish space. The subset I of shift-invariant measures is closed so d is complete over I as well. I easily contains a dense computable sequence, so I is an effective Polish subspace of P(2 N ). Let E ⊆ I be the set of ergodic shift-invariant measures. d is no more complete over E, but Proposition B.1 implies that E is an effective Polish subspace. We work with the basis given by the intersection of the canonical basis of I with E.

We now present the proof of Theorem 5.3. Let B ⊆ I × I be an open set and (P 0 , Q 0

) ∈ B with P 0 = Q 0 . Let ǫ > 0 be such that d(P 0 , Q 0 ) > ǫ and B(P 0 , ǫ) × B(Q 0 , ǫ) ⊆ B. Let δ = ǫ/4 and U B = B(P 0 , δ) × B(Q 0 , δ) ⊆ B.
Observe that U B can be effectively obtained from B. We now show how a pair (P 1 , Q 1 ) ∈ U B can be moved outside U B , but still inside B, nearly without changing its sum. By the choice of δ,

if (P 1 , Q 1 ) ∈ U B then d(P 1 , Q 1 ) > 2δ. For λ ∈ [0, 1], define P (λ) = λP 1 + (1 -λ)Q 1 , Q(λ) = λQ 1 + (1 -λ)P 1 . Observe that P (λ) + Q(λ) = P 1 + Q 1 and d(P 1 , P (λ)) = d(Q 1 , Q(λ)) = (1 -λ)d(P 1 , Q 1 ).
As d(P 1 , Q 1 ) > 2δ there exists λ ∈ (0, 1) such that (1λ)d(P 1 , Q 1 ) = 2δ. One has d(P 0 , P (λ)) ≤ d(P 0 , P 1 ) + d(P 1 , P (λ)) < 3δ < ǫ and d(P 0 , P (λ)) ≥ d(P 1 , P (λ))d(P 0 , P 1 ) > δ,

and similarly δ < d(Q 0 , Q(λ)) < ǫ so (P (λ), Q(λ)) ∈ B \ U B .
Observe that the shift-invariant measures P (λ) and Q(λ) are not ergodic. As the ergodic measures are dense in the set of shift-invariant measures, there exist two sequences P n , Q n of ergodic measures converging to P (λ) and Q(λ) respectively. As (P (λ), Q(λ)) belongs to the open set B \ U B , we can assume w.l.o.g. that (P n , Q n ) ∈ B \ U B for all n. The mapping (P, Q) → P + Q is continuous so P n + Q n converges to P (λ) + Q(λ) = P 1 + Q 1 .

C Proof of Theorem 6.1

Let us slightly reformulate the three results in a unified way.

Let X = 2 N or the space CL(2 N ) of non-empty compact subsets of 2 N . Both are effective Polish spaces with the usual topologies. Let ≤ be an ordering: inclusion or lexicographic ordering on 2 N , reverse inclusion on CL(2 N ). Let X 0 be the sequence of simple points. ≤ is computable on X 0 . It is important to observe that given a clopen set C ⊆ X and s ∈ X 0 , it is decidable whether C intersects ↑ s.

We say that x ∈ X is ≤-c.e. if the set {s ∈ X 0 : s < x} is c.e., or equivalently x is the supremum of a computable increasing sequence of simple points. We say that x is ≤generic if for every effective open set W ⊆ X, either x ∈ W or there exists ǫ > 0 such that B(x, ǫ) ∩ W ∩ ↑ x = ∅.

Theorem C.1. Let U n ⊆ X be uniformly effective dense open sets. There exists x ∈ n U n which is ≤-c.e. and ≤-generic.

The notions of generic c.e. set, generic left-c.e. real and generic Π 0 1 -class correspond to the notions of ≤-c.e. and ≤-generic points, when ≤ is the corresponding ordering. Being a co-infinite subset of N or being a closed set without isolated points can both be expressed as an intersection of dense effective open sets in the corresponding space.

Proof. The proof is a finite injury argument. We want to satisfy the requirements By construction, x ∈ B e+1 ⊆ U e so x ∈ e U e . The sequence x s converges to x. As x s ≤ x s+1 , x s also converges to sup s x s , so x = sup s x s . As the sequence x s is computable, x is c.e.

Claim.

x is ≤-generic.

Assume x /

∈ W e . Given e, let s be such that no requirement e ′ < e acts from stage s on. R e cannot act at a stage s ′ ≥ s, otherwise x ∈ B e = B e [s ′ + 1] ⊆ W e which contradicts the assumption about x. As R e never acts after stage s, it means that x ∈ B e = B e [s] and B e [s] ∩ W e ∩ ↑ x = ∅, otherwise there exists s ′ ≥ s such that B e [s] ∩ W e,s ′ ∩ ↑ x = ∅, hence B e [s ′ ] ∩ W e,s ′ ∩ ↑ x s ′ = ∅ as B e [s ′ ] = B e [s] and x s ′ ≤ x, and then R e must act at stage s ′ which is impossible.

Proposition 4. 3 .

 3 Let f be irreversible and C ⊆ X be such thatf |C : C → f (C) is an homeomorphism. Then C is nowhere dense. Proof. Assume the closure of C contains a ball B. U B ∩ C is non-empty. Let x ∈ U B ∩ C. There exists a sequence x n ∈ B \ U B such that f (x n ) converges to f (x). By density of C in B, x n can be taken in C. As f |C is an homeomorphism and f (x n ) converges to f (x), x n should converges to x and eventually enter U B , which gives a contradiction.

Example 7 .

 7 Consider the enumeration operator of Example 4. Enum is effectively irreversible: to each cylinder B = [w] associate U B = [w0]. Applying Theorem 4.1 then gives: if A is 1-generic then A and N \ A have incomparable enumeration degrees. Such an A was first proved to exist by Selman [Sel71].

R

  e : x ∈ W e or ∃ǫ, B(x, ǫ) ∩ W e ∩ ↑ x = ∅, where W e is the effective open set with number e (in the sequel, W e,s will be computable growing clopen sets with union W e ). At stage s, each requirement R e is assigned a ball B e [s]. They satisfy B e+1 [s] ⊆ B e [s] ∩ U e . For each e, the sequence B e [s] is stationary when s grows. At the same time, a computable sequence x s ≤ x s+1 is built. The requirement R e tests whether B e [s] intersects W e ∩ ↑ x s . Stage 0. Start with any ball for B 0 [0] and inductively choose B e+1 [0] ⊆ B e [0] ∩ U e of radius < 2 -e . x 0 is the center of B 0 [0]. Stage s. Let e ≤ s be minimal such that B e [s] ∩ W e,s ∩ ↑ x s = ∅, if it exists (decidable property). Let B e [s + 1] ⊆ W e,s ∩ ↑ x s ∩ U e-1 and x s+1 be the center of B e [s + 1]. Define inductively B e ′ +1 [s + 1] ⊆ B e ′ [s + 1] ∩ U e ′ of radius < 2 -e ′ for e ′ ≥ e. If e does not exist then let B e [s + 1] = B e [s] for all e and x s+1 = x s . Verification. By the usual analysis of finite injury arguments, each requirement acts finitely many times, so for each e there is s 0 such that B e [s] = B e [s 0 ] for all s ≥ s 0 . Let B e = B e [s 0 ]. One has B e+1 ⊆ B e . Let x be the unique member of e B e . Claim. x is c.e. and belongs to e U e .

  Definition 4.2. f is irreversible if for every open set B ⊆ X the restriction f |B : B → f (B) is not reversible. Formally, f is irreversible if for every non-empty open set B there exists a non-empty open set U B ⊆ B such that there is no open set

for instance the role of Baire category in computability theory has been revealed by several authors (see [Myh61] e.g.)

Acknowledgements

The author wishes to thank Peter Gács, Emmanuel Jeandel and Cristóbal Rojas for discussions on the subject and helpful comments on a draft of the paper, Christopher Porter for suggesting Example 9 and the anonymous referees for useful comments.

A Proof of Theorem 5.1

We fix a one-to-one computable enumeration n 0 , n 1 , . . . of the halting set ∅ ′ . We construct x ∈ X such that f (x) is computable and ∅ ′ is computable relative to x. We construct a shrinking sequence of balls B n and define x as the unique member of their intersection. Of course, B n must not be computable otherwise x would be computable. The sequence B n is constructed in stages: at stage s we define B n [s] and for each n the sequence B n [s] is stationary, with limit B n . For each s, the sequence B n [s] is shrinking, so the limiting sequence B n will be shrinking as well. One may imagine, for each s, the sequence B n [s] as an infinite path in a tree. At stage s + 1, n s is enumerated into A ′ and the current path branches at depth n s .

In order to make f (x) computable we enumerate along the construction all its basic neighborhoods into a list L. L is the union of a computable growing sequence of finite lists L s . At stage s, the current neighborhood of f (x), denoted V s is the (finite) intersection of the members of

In order to construct the list L, we start with a technical point: in the space X, we make an effective change of simple points and basic open sets. We can assume w.l.o.g. that the radius of U B is at most half the radius of B. Given a basic ball B, consider the computable sequence

B is a computable shrinking sequence and the unique member a of n U (n) B is computable, uniformly in B. The canonical enumeration B j of basic balls induces a computable dense sequence a j , which will serve as simple points.

We then change the basic open subsets of X. Let (V k ) k∈N be the canonical enumeration of the basic open subsets of Y .

Lemma A.1. There is a double-sequence of open sets

• the predicate a j ∈ O k,i is decidable.

Proof. By a standard diagonalization argument (computable Baire theorem on the real numbers), there exists a computable dense sequence of positive real numbers r n such that d(s i , a j ) = r n for all i, j, n. The metric balls B(s i , r n ) form an effective basis and the predicate a j ∈ B(s i , r n ) is decidable. f -1 (V k ) can be expressed as an effective union of such balls. Define O k,i as the union of the first i balls enumerated into f -1 (V k ).

We now proceed to the construction of the sequence B n [s] for each stage s. For each s, B n [s] will be a shrinking sequence, x[s] will be defined as the unique member of their intersection and will be one of the points {a j : j ∈ N}.

Stage 0. We start with a ball

Let n = n s be the next element enumerated into the halting set. Let B n+1 [s + 1] be a ball satisfying