Mathieu Hoyrup
email: mathieu.hoyrup@inria.fr

Walid Gomaa
email: walid.gomaa@ejust.edu.eg

On the extension of computable real functions

We investigate interrelationships among different notions from mathematical analysis, effective topology, and classical computability theory. Our main object of study is the class of computable functions defined over an interval with the boundary being a left-c.e. real number. We investigate necessary and sufficient conditions under which such functions can be computably extended. It turns out that this depends on the behavior of the function near the boundary as well as on the class of left-c.e. real numbers to which the boundary belongs, that is, how it can be constructed. Of particular interest a class of functions is investigated: sawtooth functions constructed from computable enumerations of c.e. sets.

I. INTRODUCTION

Computable analysis is the area of research that investigates mathematical analysis from the computability perspective. It extends the classical computability theory which exclusively studies discrete objects (that have finite encodings) to larger topological and metric spaces [START_REF] Weihrauch | Computable Analysis: An Introduction[END_REF] [START_REF] Ko | Complexity Theory of Real Functions[END_REF].

Huge body of research have been invested in computable analysis in several directions. In particular how the notions and concepts developed in classical computability can be lifted and used to drive the development of both the computability-as well as the complexity-theoretic technologies for mathematical analysis as well as to develop a foundational framework for numerical algorithms. The converse direction has already been pursued, though to a much lesser extent, that is, the application of tools and concepts from mathematical analysis, topology, and computable analysis proper, to investigate and shed more light into classical computability theory.

The work in the current paper can be viewed as a contribution to both directions, the understanding of which parts of classical mathematical analysis can be carried over to the constructible setting, and the organization of notions from computability theory using analytical concepts.

One of the simplest problems in real analysis is to extend a continuous function defined on a set to a bigger set. Let us consider the following very simple case. Start from a real number a ∈ (0, 1) and a continuous function f : [0, a) → R. When can f be extended to a continuous function on [0, 1]?

The answer is immediate: it can be extended exactly when f has a limit at a, and then the value of the extension of f at a must be that limit.

In computable or constructive analysis, this construction can be easily carried by effectivizing the assumptions accordingly. Specifically, if a is a computable real number and f : [0, a) → R is computable then f has a computable extension on [0, 1] exactly when f converges effectively at a. This is exactly the counterpart of the classical result.

In this paper we raise the following question: what happens when a is not computable? Though very simple, this question does not admit a straightforward answer but instead reveals rich phenomena and deep relationship with computability theory. The complexity of the problem makes it presumably impossible to admit a complete and general answer. The reasons why some functions may or may not admit computable extensions are extremely diverse and involve different sorts of arguments and concepts. We prove results that can be organized in three categories: (i) general results that hold independently of a, (ii) a thorough study of the problem for a restricted class of functions called the sawtooth functions, (iii) an investigation of the role of a in this problem, exhibiting several classes of reals for which the problem can be solved in different ways, with characterizations of these classes.

The main concepts involved in this investigation are: presentations of left-c.e. real numbers and their computation power, computable linear orderings, notions of genericity for left-c.e. reals and c.e. sets.

The general problem being too complex, we focus on a restricted problem. We assume that a is a left-c.e. real rather than an arbitrary real number, and we assume that the computable function f : [0, a) → R converges to 0 (or equivalently to any computable number) at a. These assumptions may seem very restrictive, but it happens that the problem is already quite rich and difficult in that case. At the end of the paper we briefly discuss the case when a is not left-c.e. and argue that the leftc.e. case is almost the only interesting one. We do not discuss the problem for functions that converge to non-computable numbers at a: it is a possible future direction that would need a complete study.

a) Main results: Let us present the structure of the paper together with the main results.

We prove a first result that will be very useful in the sequel, and that can be stated informally as follows.

Theorem A. If a is not right-c.e. and f : [0, a) → R has a computable extension g on [0, 1] then every effectively compact property satisfied by f must be essentially satisfied by g.

Here "essentially" means that g must satisfy the property on some interval [0, b] with b > a. Examples of such properties are being 1-Lipschitz, or having a sawtooth shape, as formalized later in the paper.

b) Sawtooth functions: We study a particular class of functions. To each sequence of natural numbers (n i ) i∈N we associate a function consisting of juxtaposed sawtooth with heights 2 -ni . For this class of functions we obtain a characterization of the functions that admit a computable extension: Theorem B. The sawtooth function associated with the computable sequence (n i ) i∈N admits a computable extension on [0, 1] if and only if there exists a computable linear ordering over N such that the sequence (n i ) i∈N is a monotonically increasing initial segment of .

We then study in details a sufficient and a necessary condition for admitting a computable extension.

c) A sufficient condition: First, the null extension of f : [0, a) → R is computable if and only if f converges effectively to 0 at a, so effective convergence to 0 is a sufficient condition. We will easily see that this condition is not necessary in general. However for some a's, this sufficient condition is also necessary, and we obtain a characterization of this class of reals:

Theorem C. Let a be left-c.e. The following statements are equivalent:

• Every computable function f : [0, a) → R that admits a computable extension on [0, 1] converges effectively to 0 at a, • a is computable or right-generic.

We will of course recall the definition of right-generic reals, which was introduced in [START_REF] Hoyrup | Irreversible Computable Functions[END_REF]. These real numbers can be thought of as typical, or generic among the left-c.e. reals. d) A necessary condition: If f has a computable extension on [0, 1] then f must have a computable modulus of continuity, which is then a necessary condition. Again, this condition is not sufficient in general. This is not immediate, but the sawtooth functions studied earlier provide counterexamples. We also obtain a characterization of the reals a for which this necessary condition is also sufficient: Theorem D. Let a be left-c.e. The following statements are equivalent:

• Every computable function f : [0, a) → R having a computable modulus of continuity admits a computable extension, • a is simple, i.e. has only computable presentations.

Again we will recall the definition of simple reals, a notion that was introduced in [START_REF] Downey | Presentations of computably enumerable reals[END_REF].

e) Separating the two classes: We met two classes of left-c.e. reals that are strongly related to the computable extension problem: the right-generic reals and the simple reals. The latter is a subclass of the former (outside the computable reals). Is it a proper subclass? We positively answer this question, introducing the notion of generalized binary representation: if (u n ) n∈N is a computable sequence with a computable sum such as 1/n 2 , a generalized binary representation of a real a is a set A ⊆ N such that a = n∈A u n . While simple reals do not admit a c.e. generalized binary representation, we prove that right-generic reals can, which separates the two classes.

Theorem E. If the sequence (u n ) n∈N converges slowly to 0, formally if u n+1 /u n converges to 1, then there exists a c.e. set A such that n∈A u n is right-generic (and such a sum is never a simple real).

To prove this theorem, instead of building the set A by hand, we carefully choose a topology such that if A is in some sense generic in that topology then n∈A u n is right-generic.

f) Organization of the paper: Section I-A gives the core definitions and notions used throughout the rest of the paper. Section II starts the technical contribution of the paper. It proves several essential results about the computable extension problem. Sufficient and necessary conditions of extendability are studied, and we state and prove Theorem A. In Section III we investigate the computational extendability properties of a rich class of functions, namely sawtooth functions and prove Theorem B. In Section IV we obtain a characterization of the class of reals for which the sufficient (resp. necessary) condition mentioned above is also necessary (resp. sufficient), proving that they coincide with the right-generic (resp. simple) reals. Theorem C and D are proved there. In Section IV-C we prove Theorem E that separates the classes of simple and right-generic reals by introducing and studying the generalized binary representations. In Section V we briefly discuss the computable extension problem for a function f : [0, a) → R when a is not left-c.e. We terminate the paper in Section VI with open questions for future research directions.

A. Background

In this section we give the basic definitions that will be used throughout the rest of the paper.

Let N denote the set of natural numbers, Q the set of rational numbers, and R the set of real numbers. Let {0, 1} * denote the set of finite binary strings, and let 2 N denote the set of infinite binary strings or equivalently subsets of N. If α ∈ 2 N , then α n is the prefix of α of length n. We assume a computable bijection . from finite sequences of natural numbers to N.

We assume familiarity with the notions of a computable set of natural numbers, a computably enumerable (c.e.) set, a computable function from N to N. Now we define some notions from computable analysis. a) Computability in topological spaces: An effective topological space is a triple (X, τ, B) where (X, τ ) is a countably-based topological space and B = {B i : i ∈ N} is a countable basis coming with a numbering such that for each i, j there exists a set E ⊆ N that is c.e. uniformly in i, j, such that B i ∩ B j = k∈E B k . In the sequel for each effective topological space we will give the countable basis: each time there is an obvious canonical numbering that we will not expand on.

Let (X, τ, B) be an effective topological space. An open set

U ⊆ X is effectively open if U = i∈E B i for some c.e. set E ⊆ N. A closed set A ⊆ X is effectively closed if its complement X \ A is effectively open. A compact set K ⊆ X is effectively compact if the set { i 1 , . . . , i n : K ⊆ B i1 ∪ . . . ∪ B in } is c.e.
The intersection of an effective closed set and an effective compact set is always an effective compact set, and an effective compact set is always effectively closed [START_REF] Brattka | Computability on subsets of metric spaces[END_REF].

A point

x ∈ X is a computable point if the set {i ∈ N : x ∈ B i } is c.e. A function f : X → Y is a computable function if for all i ∈ N, f -1 (B Y i
) is effectively open, uniformly in i. A computable metric space is a triple (X, d, S) where (X, d) is a separable metric space and S = (s i ) i∈N is a dense sequence such that the real numbers d(s i , s j ) are computable uniformly in i, j. Every computable metric space is an effective topological space with the basis of metric balls B(s, r) = {x ∈ X : d(x, s) < r} where s ∈ S and r > 0 is rational.

In a computable metric space, the notions of computable point and computable function can be reformulated as follows. A name of x ∈ X is a function p : N → N such that d(s p(i) , x) ≤ 2 -i for all i. A point x is computable iff it has a computable name. A function f : D ⊆ X → Y is computable iff there exists an oracle Turing machine M such that for every name p of every x ∈ D, M with oracle p computes a name of f (x).

The following easy facts are very useful (they are stated in [START_REF] Weihrauch | Computable Analysis: An Introduction[END_REF] for Euclidean spaces, but they hold on arbitrary computable metric spaces, the classical proofs being effective; proofs can be found in [START_REF] Hoyrup | Computability of the ergodic decomposition[END_REF] for instance).

Proposition I.1. Let X, Y be computable metric spaces.

If K ⊆ X is effectively compact and f :

K → Y is computable then f (K) is effectively compact. If f is moreover one-to-one then its inverse f -1 : f (K) → K is computable. Proposition I.2 ([1]). A set A ⊆ [0, 1] is effectively closed if and only if there exists a computable function f : [0, 1] → R such that A = f -1 (0).

b) Examples of computable metric spaces:

The Cantor space 2 N is the space of subsets of N or equivalently infinite binary sequences, with the Cantor topology induced by the basis of cylinders

[w] = {x ∈ 2 N : w is a prefix of x} where w ∈ {0, 1} * . The associated metric is d(x, y) = 2 -n where n is minimal such that x n = y n .
The real line R is the space of real numbers with the Euclidean topology induced by the rational intervals (a, b). The associated metric is the Euclidean metric d(x, y) = |x-y|.

We will also need the space

C [0, 1] of continuous func- tions f : [0, 1] → R with the uniform metric d(f, g) = max x∈[0,1] |f (x) -g(x)
| and the polynomials with rational coefficients as countable dense subset.

A continuous function f : [0, 1] → R is computable as an element of C [0, 1] if and only if it is computable as a function between the effective topological spaces [0, 1] and R.

The following notion is central in this paper.

Definition I.1 (Left-c.e. real number). A real number x is left-c.e. if there exists a computable increasing sequence of rational numbers converging to a. Equivalently, x is left-c.e. if its left-cut {r ∈ Q : r < x} is a c.e. set of rationals.

The

interval [0, a) is effectively open iff [a, 1] is effectively compact iff a is left-c.e.
The following notion was introduced by Jockusch on the Cantor space and expresses the idea of a typical point with no particular property. Definition I.2 (1-generic [START_REF] Jockusch | Simple proofs of some theorems on high degrees[END_REF]). In a complete computable metric space X, a point x ∈ X is 1-generic if it does not belong to the boundary of any effective open set U ⊆ X.

Equivalently, x is 1-generic if for every effective open set U , either x ∈ U or there exists a neighborhood N of x such that N ∩ U = ∅.
The Baire category theorem implies the existence of such points, which are in a sense predominant. This notion is particularly used to prove existence results in an elegant way. In the Cantor space, 1-generic sets are not c.e. nor co-c.e. In the real line, 1-generic reals are not left-c.e. In the sequel we will see how the notion of 1-genericity can be adapted to express that a c.e. set or a left-c.e. real number are typical (Definitions III.2 and IV.1).

II. GENERAL RESULTS

Let a ∈ [0, 1]. Every continuous function f : [0, a) → R that has a limit at a can be extended to a continuous function on [0, 1]. Here we study an effective version, where a is a left-c.e. real number: if f : [0, a) → R is computable and lim x→a -f (x) = 0, then it is natural to ask, when can f be extended to a computable function over [0, 1]?

We first derive easy facts.

A. A sufficient condition

We start with a sufficient condition for computable extendability.

There is a canonical extension of f , the null extension defined by f 0 (x) = 0 for x ≥ a. It is easy to characterize the cases when f 0 is computable.

Definition II.1. A modulus of convergence for f : [0, a) → R is a function m between rational numbers such that for > 0, m( ) < a and |f | ≤ on [m( ), a).
We say that f : [0, a) → R effectively converges to 0 if it admits a computable modulus of convergence.

Proposition II.1. Let a be left-c.e. and f : [0, a) → R be computable. The null extension of f on [0, 1] is computable iff f effectively converges to 0.

Proof. Assume that the null extension

f 0 of f is computable. Given > 0, the set f -1 0 (-, ) is an effective open set which contains [a, 1]. As [a, 1] is effectively compact one can effectively find some rational q such that [a, 1] ⊆ (q, 1] ⊆ f -1 0 (-, ). Let m( ) = q.
For the other direction, assume f effectively converges to 0 with modulus m and f 0 be the null extension of f . To compute f 0 (x) up to , compute m( ) and test the inequalities x > q and x < a in parallel. If x > m( ) is recognized first then output 0. If x < a is recognized first then compute f (x) at precision .

Observe that if f has a computable extension which is essentially null, i.e. null on some interval [a, a+δ] with δ > 0, then the null extension is also computable and f converges effectively to 0.

The preceding result shows that effective convergence to 0 is a sufficient condition. We will see in Section IV-A that it is not necessary in general and we will characterize the class of numbers a for which it is necessary.

B. A necessary condition

Definition II.2. We say that f has a computable modulus of continuity if given a rational number > 0 one can compute a rational number δ > 0 such that for x, y < a, |x -

y| ≤ δ implies |f (x) -f (y)| ≤ .
As every computable function f : [0, 1] → R has a computable modulus of continuity, a computable function f : [0, a) → R must have a computable modulus of continuity to admit a computable extension on [0, 1]. We will see in Section IV-B that it is not sufficient in general and we will obtain a characterization of the class of left-c.e. reals for which it is sufficient.

In the degenerate case when a is computable the two conditions seen so far are necessary and sufficient.

Proposition II.2. If a is computable and f : [0, a) → R is computable and converges to 0 then f has a computable extension iff f converges effectively to 0 iff f has a computable modulus of continuity.

Proof. If f has a computable modulus of continuity then it converges effectively to 0. Indeed, given , compute δ coming from the modulus of continuity and compute q ∈ (a -δ, a). One obviously has |f | ≤ on [q, a), so m( ) := q defines a computable modulus of convergence. a) Another necessary condition: Admitting a computable extension has a consequence on the computability content of the convergence to 0 at a: it is computable or it computes a.

Proposition II.3. Let a be left-c.e. and f : [0, 1] → R be computable with f (a) = 0. f converges effectively to 0 at a - or a is computable relative to any modulus of convergence for f . Proof. Assume that f does not converge effectively to 0. The remark following Proposition II.1 implies that f is not null on any interval [a, a + δ), δ > 0. Let m be a modulus of convergence for f . One has

a = inf >0 inf{q ∈ Q ∩ [0, 1] : q > m( ) and |f (q)| > }. (1)
Indeed, inequality ≤ holds because |f | ≤ on [m( ), a]. To prove inequality ≥, let δ > 0. As f is not null on [a, a+δ], for sufficiently small there exists q ∈ [a, a+δ] such that |f (q)| > , so the right-hand side is at most a+δ. As it is true for every positive δ, we get equality [START_REF] Weihrauch | Computable Analysis: An Introduction[END_REF]. Now observe that the right-hand side of ( 1) is right-c.e. relative to m. As a is left-c.e., it implies that a is computable relative to m.

We will see later that this necessary condition is not sufficient in general.

Observe that if f : [0, a) → R is computable and has a computable modulus of continuity then a computes a modulus of convergence for f , by relativization of Proposition II.2, so when f has a computable extension, computing a modulus of convergence of f is equivalent to computing a.

C. Uniqueness of the extension

Let us now investigate deeper properties. We first show that if f has a computable extension then surprisingly this extension is essentially unique unless a is computable. The reason for this is very simple.

Proposition II.4. Assume that a ∈ (0, 1) is not right-c.e. and f : [0, a) → R is computable. If f has a computable extension g, then every computable extension of f coincides with g on some interval [a, a + δ] with δ > 0.

Proof. Let g, h be computable extensions of f and b = inf{x : g(x) = h(x)}. One has b ≥ a and b is right-c.e. so b > a.

Observe that if g is a computable extension of f then it is not the unique computable extension: if q ∈ (a, 1) is a rational number, then one can modify g on [q, 1] in a computable way, giving another computable extension of f . However g cannot be modified in a computable way on every neighborhood of a at the same time.

A particular case of Proposition II.4 is that if a is leftc.e. but not computable and f converges effectively to 0, then every computable extension of f is essentially null, i.e., null on some interval [a, a+δ] with δ > 0. In other words, unless a is computable, f cannot admit both the null extension and an essentially non-null computable extension at the same time.

One can generalize Proposition II.4 in the following way: if f has a (non necessarily computable) extension satisfying a certain type of property, then every computable extension must essentially satisfy this property. Proposition II.4 is a particular case, for the property "being equal to g". The properties for which this result holds are the ones that are effectively compact.

Theorem II.1. Let K ⊆ C [0, 1] be effectively compact. Let a ∈ [0, 1] be a real number that is not right-c.e., and f : [0, a) → R be computable. If f has an extension in K, then for every computable extension g there exists b > a such that g [0,b] has an extension in K.

Again one cannot conclude that g belongs to K, but only that g belongs to K "up to some b > a" (this is formalized as in the statement).

Proof. For x ∈ [0, 1], let K x be defined as follows: for any g ∈

C [0, 1], g ∈ K x iff there exists h ∈ K such that g [0,x] = h [0,x] . One has K x ⊆ K y if x ≥ y. Claim. For q ∈ Q ∩ [0, 1], the complement of K q is effectively open, uniformly in q. Indeed, let Φ q = C [0, 1] → C [0, 1] map g to g defined by g (x) = g(x) if x ≤ q g(q) if x ≥ q.
Φ q is computable uniformly in q and K q = Φ -1 q (Φ q (K)). As K is effectively compact, by Proposition I.1 Φ q (K) is effectively compact so its complement is effectively open, and so is its preimage. Everything is uniform in q and the claim is proved.

Let g be a computable extension of f . Let

c = inf{q ∈ Q ∩ [0, 1] : g / ∈ K q }, with inf ∅ = 1.
As f has an extension in K, one has g ∈ K a so c ≥ a. As the complement of K q is effectively open uniformly in q, c is right-c.e. As a is not right-c.e., c > a. Hence, for any b ∈ (a, c), g ∈ K b (one can actually prove that g ∈ K c since K is compact).

Examples of effective compact sets are: the class of 1-Lipschitz functions with some computable fixed value at 0, the class of functions with some fixed computable modulus of continuity and some computable fixed value at 0, the class of sawtooth functions introduced in the next section.

Sometimes we are interested in effectively closed properties. For these properties one can still derive a result with an additional assumption.

Corollary II.1. Let C ⊆ C [0, 1] be an effectively closed set. Assume that a ∈ (0, 1) is not right-c.e. and let f : [0, a) → R be computable. If f has an extension in C having a computable modulus of continuity, then for every computable extension g there exists b > a such that g [0,b] has an extension in C.

Proof. Let m be the assumed computable modulus of continuity and K m be the set of functions having this modulus of continuity, and having value f (0) at 0. K m is effectively compact so K := K m ∩ C is also effectively compact. By assumption, f has an extension in K so by Theorem II.1 every computable extension of f belongs to K b ⊆ C b for some b > a.

For some properties K we can conclude that f has a computable extension in K.

Definition II.3. A class K has the computable extension property if for every rational number q ∈ [0, 1], every computable function f : [0, q] → R that has an extension in K has a computable extension in K.

Proposition II.5. Let K ⊆ C [0, 1] be an effectively compact class that has the computable extension property. Assume that a ∈ (0, 1) is not right-c.e. and let f : [0, a) → R be computable. If f has an extension in K and has a computable extension, then it has a computable extension in K.

Proof. By Theorem II.1, there is b > a such that g [0,b] has an extension in K. One can take b rational, so g [0,b] (hence f ) has a computable extension in K by the computable extension property.

III. SAWTOOTH FUNCTIONS

We now study the problem in a restricted setting, and obtain a characterization of the functions admitting a computable extension. We restrict ourselves to left-c.e. real numbers a that can be expressed as a = n∈A 2 -n for some c.e. set A ⊆ N, and functions f : [0, a) → R of a particular shape, called the sawtooth functions.

The results are interesting on their own as they give a rather clear understanding of the problem in a restricted case. They will also prove useful in the sequel, as a source of examples and counter-examples.

They provide in particular a computable function having a computable modulus of continuity but no computable extension.

A. Sawtooth functions

Let h : N → N be a one-to-one computable function, let

a = i∈N 2 -h(i)-1 ∈ [0, 1]
and a i = 2 -h(0)-1 + . . . + 2 -h(i-1)-1 with a 0 = 0. The real number a is left-c.e. We then define a computable function f : [0, a) → R as follows. On [a i , a i+1 ],

f (a i ) = f (a i+1 ) = 0, (2)
f a i + a i+1 2 = a i+1 -a i 2 = 2 -h(i)-2 , ( 3
)
and f is linear in between (see Fig. 1). To make it clear that a and f are obtained from h, we will sometimes denote them by a h and f h respectively.

0 x f (x) a i a i+1 2 -h(i)-1 2 -h(i)-2 a Fig. 1. Sawtooth function
Observe that f is 1-Lipschitz so it has a computable modulus of continuity. The function f converges effectively to 0 if and only if the set A h = {h(i) : i ∈ N} is computable if and only if a is computable: in that case the null extension of f is computable.

We obtain a characterization of the functions h for which f h admits a computable extension.

Theorem III.1. Let h : N → N be a one-to-one computable function and A h = {h(i) : i ∈ N}. The function f h : [0, a h ) → R has a computable extension on [0, 1] if and only if there exists a computable linear ordering on N such that

• h(0) ≺ h(1) ≺ h(2) ≺ . . .
• and A h is an initial segment of (i.e., m ≺ n for all m ∈ A h and n / ∈ A h ).

Intuitively, the linear ordering puts the elements of A h first, in order of h, then the rest of N. We now prove Theorem III.1.

B. Linear orderings

Given a linear ordering on N we define f : [0, 1] → R as follows. For each n ∈ N, let

x n = p≺n 2 -p-1 , y n = x n + 2 -n-1
and I n = (x n , y n ). One has m ≺ n iff y m ≤ x n so that I m is disjoint from I n when m = n. We define f on [x n , y n ] as follows:

f (x n ) = f (y n ) = 0, f x n + y n 2 = y n -x n 2 = 2 -n-2 ,
and f is linear in between. On the complement of n I n , f is null. Observe that f is 1-Lipschitz.

Claim. The function Φ mapping a linear ordering over N to f is computable.

Proof. Assume that is given as oracle. One can compute the sequences x n , y n . Indeed, the binary expansion of x n is computable as the bit at position p is 1 if and only if p ≺ n. The set U := n (x n , y n ) is dense in [0, 1] as its Lebesgue measure is n (y n -x n ) = 1. One can compute a sequence r i of rational numbers inside U . The numbers f (r i ) are uniformly computable (given i, find n such that r i ∈ (x n , y n ) and use the definition of f on that interval). As f is 1-Lipschitz, it has a computable modulus of continuity so it is computable (relative to ). All this is uniform in so Φ is computable.

Given h : N → N, if there is a computable linear ordering satisfying the conditions of Theorem III.1, then the sawtooth function associated to is a computable function extending f h , which proves one direction of the theorem. We now prove the other direction.

The space of linear orderings over N can be embedded as an effective compact subset of the Cantor space. Indeed, a linear ordering over N can be identified with the set { m, n : m n}, where ., . is a computable bijection between N 2 and N. The set of sequences that encode linear orderings is an effective closed set since the axioms of linear orderings are all universal statements. As the Cantor space is effectively compact, so is the subspace of linear orderings.

It implies that the image S of the space of linear orderings under Φ is an effective compact subset of C [0, 1]. Moreover, Φ is one-to-one. Indeed, can be read off f as follows: for each n ∈ N, f has exactly one point p n where f (p n ) = 2 -n-2 and p n is a local maximum. Then m n iff p m ≤ p n . Note that this argument is not necessarily effective, however by Proposition I.1 the inverse of Φ is computable, i.e. can be computed from f , uniformly.

Lemma III.1. The set S has the computable extension property.

Proof. If q is rational and f : [0, q] → R is a computable function admitting an extension g in S, then let b ≥ q be minimal such that g(b) = 0.

Claim. The real number b is computable.

If b = q then it is computable. If b > q then let c < q be maximal such that f (c) = 0. c is computable, because if q ∈ (c, q) is a rational number sufficiently close to c then c = q -f (q) because of the shape of f , so c is computable. One has b = c + 2 -n-1 for some n so b is computable and the claim is proved.

The function g corresponds to a linear ordering over N. The number b corresponds to an initial segment B of , such that n∈B 2 -n-1 = b. As b is computable, B is computable. Consider a computable linear ordering over N defined as follows: B is an initial segment of , coincides with on B, and coincides with the natural ordering on N \ B. The sawtooth function associated with extends f and is computable. Now let h : N → N be a computable one-to-one function and f h : [0, a h ) → R be the associated function. The function f h has an extension f for some linear ordering : andm n if m < n and m, n / ∈ A h . As a result, by Proposition II.5, if f has a computable extension, then it has a computable extension in S. This extension is f for some linear ordering over N which is computable as the inverse of Φ is computable. As f extends f h , one has h(0) h(1) . . . and A h is an initial segment of .

define h(i) h(j) if i < j, m n if m ∈ A h and n / ∈ A h ,
Theorem III.1 is proved.

C. Consequences

We now discuss the possibility of both negative and positive equivalence in Theorem III.1.

a) Non-extensible sawtooth functions.: Let h : N → N be one-to-one, computable and A be the range of h. Theorem III.1 implies in particular that if f h has a computable extension then A is an initial segment of a computable linear ordering over N. Such sets are well-known in computability theory. It was proved by MacLaughlin and Appel (unpublished, a proof can be found in [START_REF]Semirecursive sets and positive reducibility[END_REF]) that a set A is an initial segment of some computable linear ordering over N if and only if A is semirecursive, i.e. there exists a computable function s : N 2 → N, called a selector, such that for all x, y ∈ N, (i) s(x, y) ∈ {x, y} and (ii) if x ∈ A or y ∈ A then s(x, y) ∈ A. One direction is straightforward: if A is an initial segment of a computable linear ordering then let s(x, y) be minimal among x, y w.r.t. .

We then immediately obtain the following result.

Corollary III.1. Let A be a c.e. set that is not semirecursive. For no enumeration h of A the function f h can be computably extended.

There are many examples of c.e. sets that are not semirecursive. Let us list a two classes of such sets appearing in [START_REF]Semirecursive sets and positive reducibility[END_REF].

1) If a set is simple but not hypersimple then it is not semirecursive. 2) If a set is m-complete, i.e. the halting set is f -1 (A) for some computable function f , then it is not semirecursive.

Actually semirecursive sets are very particular, and a "typical" c.e. set is not semirecursive. Being typical for a c.e. set can be formalized by weakening the notion of 1-genericity (Definition I.2).

Definition III.1 ([3]). Let A ⊆ N and U ⊆ 2 N be effectively open. Then U is dense above A if U contains sets B ⊇ A arbitrarily close to A, i.e., in every cylinder [A n ].
Definition III.2 (Generic from above [START_REF] Hoyrup | Irreversible Computable Functions[END_REF]). A set A ⊆ N is generic from above if it belongs to every effective open set U ⊆ 2 N that is dense above A.

In other words, A is generic from above if for each effective open set U , either

A ∈ U or {B ∈ 2 N : B ⊇ A}∩[A n ]∩U = ∅ for some n.
It is proved in [START_REF] Hoyrup | Irreversible Computable Functions[END_REF] that there exists a co-infinite c.e. set that is generic from above.

Proposition III.1. If A is generic from above, then A is not semirecursive.

Proof. Let s be a computable selector, i.e. a computable function such that s(m, n) ∈ {m, n} for all n. Let P s be the class of subsets of N that are semirecursive with selector s. P s is an effective closed subset of the Cantor space as the complement of P s ,

P c s = {X ⊆ N : ∃x, y ∈ N, (x ∈ X or y ∈ Y ) and s(x, y) / ∈ X}
is an effective open set. If A belongs to P s and is coinfinite then one can add an arbitrarily large element to A to make it leave P s : take m, n arbitrarily large distinct elements outside A, if s(m, n) = m then add n to A otherwise add m to A. As a result, if A is co-infinite then the complement of P s is dense above A. If A is generic from above then A must belong to the complement of P s . As this is true for every computable selector s, A is not semirecursive.

b) Extensible sawtooth functions: The following result shows the existence of a sawtooth function f h that can be computably extended although A h (hence a h ) is not computable. By the previous discussion, such a set A h must be semirecursive. The existence of semirecursive non-computable c.e. sets is well-known. For instance, let (q i ) i∈N be a one-toone computable enumeration of the rational numbers in [0, 1], let a be a non-computable left-c.e. real and let A = {i ∈ N : q i < a}. A is a non-computable c.e. set and is an initial segment of the computable linear ordering defined by i j iff q i ≤ q j . However we not only need a c.e. set that is an initial segment of a linear ordering (equivalently a semirecursive c.e. set), but that this initial segment can be computably enumerated monotonically.

Proposition III.2. There exists a computable linear ordering of N of order type ω + ω * whose infinite left-cut is not computable but can be effectively enumerated monotonically.

Proof. Start from a non-computable c.e. set A and a computable one-to-one enumeration (n i ) i∈N of A (we assume that n i ≥ 1 for all i). That sequence converges to ∞ non-effectively. We now define the sought computable linear ordering on the natural numbers. Let N i = n 0 +. . .+n i-1 . We inductively define the ordering on the first N i natural numbers. At stage i we have defined the ordering on [0, N i -1]. We represent it by the finite sequence containing these numbers ordered according to . In addition at each stage we mark a position where subsequent numbers will be inserted. Formally, at each stage i we have two finite sequences u i , v i of natural numbers such that the concatenation u i v i lists [0, N i -1] increasingly w.r.t. . Let u 0 and v 0 be the empty sequences. If u i and v i are defined, then let w be the finite sequence listing the next fresh n i numbers (i.e., the interval [N i , N i + n i -1]) in the natural ordering. Form the finite sequence u i wv i and decompose it as

u i wv i = u i+1 v i+1 where the length of v i+1 is n i . For i ≥ 1, |v i+1 | = n i < n i + n i-1 = |wv i |, u i+1
properly extends u i , so u i converges to a computable sequence u. Let v i be the sequence v i in reversed order. As one of v i+1 and v i is prefix of the other and |v i | = n i converges to infinity, v i converges to some infinite sequence v. The ordering is defined as follows: m n if m and n appear in u in that order; m n if m appears in u and n in v; m n if m and n appear in v in reversed order. As u and v are infinite sequences, this ordering has order-type ω + ω * . Now the set of numbers that appear in u is c.e., but is not computable (it is even hypersimple). Assume for a contradiction that it is computable. It implies that n i converge effectively to infinity. Indeed, given k, find some number p that does not appear in u and has at least k elements above it in the ordering . Find i such that p appears in v i . As p will never be put into u, we know that for j > i, the length of v j is at least k, so n j is at least k.

Corollary III.2. There exists a non-computable c.e. set A and a computable enumeration h of A such that f h can be computably extended (where f h is the sawtooth function defined in Eq. ( 2)).

IV. RIGHT-GENERIC AND SIMPLE REALS

A. When is effective convergence necessary?

We saw that if a is left-c.e. and f : [0, a) → R is computable and converges effectively to 0 at a then f has a computable extension. However effective convergence is not a necessary condition in general. Example 1. Take a non-empty effective closed set A ⊆ [0, 1] such that a = min A is not computable (it must be left-c.e.) and A has empty interior. There exist famous examples of such sets: for instance, a non-empty effective closed set that avoids every computable real. More specifically one can take a level of Martin-Löf random reals, defined by {x ∈ [0, 1] : ∃n, K(x n ) ≤ n -1} where x n is the prefix of length n of the binary expansion of x (the one with infinitely many 0's) and K(u) is the prefix Kolmogorov complexity of u, see [START_REF] Li | An Introduction to Kolmogorov Complexity and Its Applications[END_REF] for details.

Then take a computable function f : [0, 1] → R which is null exactly on A as in Proposition I.2. Its restriction to [0, a) obviously has a computable extension and does not converge effectively to 0 at a. Indeed, otherwise it would have two essentially different extensions, the null extension and f itself, which is forbidden by Proposition II.4.

We now ask the question: for which left-c.e. reals a is effective convergence a necessary condition to admit a computable extension? We saw that this class contains the computable reals. What else? It happens that this class of reals coincides with a previously defined class of left-c.e. reals. We already saw in Definition III.2 how to adapt the notion of 1-genericity to c.e. subsets of N. It can also be adapted to left-c.e. reals as follows.

Definition IV. 1 ([3]). A real number a ∈ [0, 1) is generic from the right or right-generic if for each effective open set U , either a ∈ U or [a, a + δ] ∩ U = ∅ for some δ > 0.

This notion can be reformulated as follows: a is rightgeneric if a belongs to every effective open set that is dense on the right of a, i.e. that contains reals b > a arbitrarily close to a.

It was proved in [START_REF] Hoyrup | Irreversible Computable Functions[END_REF] that there exists a left-c.e. right-generic real a ∈ [0, 1).

Proposition IV.1. For a left-c.e. real number a, the following statements are equivalent:

1) a is computable or right-generic, 2) Every computable function f : [0, 1] → R such that f (a) = 0 converges effectively to 0 on the left of a.

Proof. Assume that a is right-generic. f -1 (R \ {0}) is an effective open set that does not contain a, so there exists δ > 0 such that f = 0 on [a, a + δ]. The null extension of f is then computable so f converges effectively to 0 by Proposition II.1. Conversely, assume that a is neither computable nor rightgeneric. Let U ⊆ [0, 1] be an effective open set that does not contain a and it dense on the right of a, i.e. intersects every interval (a, a + δ). Let f : [0, 1] → R be a computable function such that U = f -1 (R \ {0}) as in Proposition I.2. In particular, f (a) = 0 and f is not null on any interval (a, a+δ). By Proposition II.4 f does not converge effectively to 0 on the left of a.

B. When is a computable modulus of continuity sufficient?

Let a ∈ [0, 1] be left-c.e. and f : [0, a) → R be a computable function converging to 0 at a. As we saw previously,

• If f : [0, a) → R has a computable extension then f must have a computable modulus of continuity, • If f has a computable modulus of continuity then f does not necessarily admit a computable extension: take a sawtooth function f h constructed from a computable enumeration of a c.e. set that is not semirecursive and apply Corollary III.1. We now ask for which left-c.e. reals having a computable modulus of continuity is sufficient? It happens that this class again coincides with a previously defined class of left-c.e. real numbers, introduced by Downey and LaForte [START_REF] Downey | Presentations of computably enumerable reals[END_REF].

Definition IV.2 ([4]

). A presentation of a left-c.e. real number a ∈ [0, 1] is a prefix-free c.e. set A ⊆ {0, 1} * such that a = w∈A 2 -|w| . A left-c.e. real a is simple if every presentation of a is computable.

Noncomputable simple left-c.e. reals exist, as proved by Downey and LaForte [START_REF] Downey | Presentations of computably enumerable reals[END_REF]. We first give a reformulation of the definition in terms of converging sequences.

Proposition IV.2. A left-c.e. real a ∈ [0, 1] is simple iff for every computable nondecreasing sequence a i converging to a, the sequence a i+1 -a i converges effectively to 0.

Proof. Assume that a is simple. Let a i a be a computable sequence. There exist uniformly computable sets A i ⊆ {0, 1} * such that A i is a presentation of a i+1 -a i and no element of A i is a prefix of any element of any A j , and such that for each i there exists w ∈ A i such that 2 -|w| ≥ (a i+1 -a i )/2. The union i A i is a presentation of a so it is computable. Given > 0 one can compute the maximal i such that A i contains a string w such that 2 -|w| ≥ /2. For j > i, a j+1a j < .

Conversely, assume that a is not simple. Let A ⊆ 2 * be a non-computable presentation of a, let {w i } be a computable enumeration of A and a i = 2 -|w0| +. . .+2 -|wi-1| . As A is not computable, 2 -|wi| = a i+1 -a i does not converge effectively to 0.

We then prove our characterization.

Theorem IV.1. For a left-c.e. real number a, the following statements are equivalent:

1) a is simple, 2) Every computable function f : [0, a) → R converging to 0 at a and having a computable modulus converges effectively to 0 at a, 3) Every computable function f : [0, a) → R converging to 0 at a and having a computable modulus has a computable extension.

Proof. 1. ⇒ 2. Let a be simple and f : [0, a) → R be computable with a computable modulus. One can compute an increasing sequence a i converging to a such that |f (a i )| < 2 -i . As a is simple, Proposition IV.2 implies that a i+1 -a i converges effectively to 0. Given , the modulus of continuity provides some δ. To δ, the effective convergence of (a k+1a k ) k associates i such that a j+1 -a j < δ for all j ≥ i.

One can assume that 2 -i ≤ , otherwise increase i. We now show that |f | ≤ 2 on [a i , a). For x ∈ [a i , a), let j ≥ i be such that a). So f converges effectively to 0 at a. 2. ⇒ 3. This is obvious, as if f converges effectively to 0 then its null extension is computable.

a j ≤ x < a j+1 . As |x -a j | < a j+1 -a j ≤ δ, |f (x) -f (a j )| ≤ so |f (x)| ≤ + 2 -j ≤ 2 . As a result, |f | ≤ 2 on [a i ,
3. ⇒ 1. We need the following lemma.

Lemma IV.1. If a left-c.e. real number a is not simple then it has a non-computable presentation A that does not compute a.

Proof. By the Sacks splitting theorem, A can be split into A = A 0 ∪ A 1 where A 0 and A 1 are disjoint, c.e. and Turing incomparable. We build a presentation A of a that is Turing equivalent to A 0 . In particular, it is not computable and it does not compute a, otherwise A 0 would compute a which computes A which in turn computes A 1 .

A is defined as A = A 0 ∪ A 1 where A 1 is computable. Let u i be a computable enumeration of A 1 . At each stage i ∈ N, if |u i | ≥ i then put u i in A 1 , otherwise put all the extensions of u i of length i in A 1 . A 1 is computable as a string w belongs to A 1 if and only if w is enumerated into A 1 at a stage i ≤ |w|. By construction, A is still prefix-free, c.e. and its weight w∈A 2 -|w| is the weight of A which is a. As a result, A is indeed a presentation of a. As A 1 is computable, A is Turing equivalent to A 0 and the Lemma is proved. Now assume that a is not simple. Let A be a presentation of a which is not computable and does not compute a, as in Lemma IV.1. Fix some computable enumeration of A and build the corresponding sawtooth function f : [0, a) → R as usual: to a string w enumerated into A corresponds a pick of width 2 -|w| and height 2 -|w|-1 . The function f is computable, it is 1-Lipschitz hence has a computable modulus of continuity. As A is not computable, f does not converge effectively to 0. f converges to 0 effectively relative to A, so if f has a computable extension then by Proposition II.3 A computes a. This is a contradiction, so f does not admit a computable extension.

Observe that just taking a non-computable presentation of a one builds in the same way a computable function f : [0, a) → R which is 1-Lipschitz and does not converge effectively to 0, thus showing implication 2. ⇒ 1. directly. This result already appeared with a direct, simpler proof in [START_REF] Hoyrup | Irreversible Computable Functions[END_REF].

We now separate these two classes: there exists a leftc.e. real that is right-generic but not simple. We do so by introducing the notion of generalized binary representation.

1) Generalized binary representation: Let x ∈ [0, 1] and A ⊆ N. We say that A is a binary representation of x if x = n∈A 2 -n . It is straightforward to see that a simple left-c.e. real x cannot have a c.e. binary representation A: indeed, such an A would induce a non-computable presentation of x, in the sense of Definition IV.2 (take the prefix-free c.e. set {0 n-1 1 : n ∈ A}). It is also easy to see that left-c.e. right-generic reals do not have c.e. binary representations.

What happens if one replaces the sequence 2 -n with another sequence like 1/n 2 ? What are the left-c.e. real numbers x that can be expressed as x = n∈A 1/n 2 for some c.e. set A? One could say that such an A is a generalized binary representation of x. We will see that while simple reals do not admit a c.e. generalized binary representation, right-generic reals sometimes do. This will be our separation argument.

Lemma IV.2. Let u = (u n ) n∈N be a computable sequence of positive real numbers. If A ⊆ N is c.e. but not computable and x = n∈A u n is finite then x is not simple.

Proof. We use the characterization provided by Proposition IV.2. Let n i be a computable one-to-one enumeration of A. The sums of the sequence u ni converge to x and we show that u ni does not converge effectively to 0. Assume for a contradiction that u ni converges effectively to 0. It implies that n i converges effectively to ∞ so A is computable. Indeed, given k ∈ N let < min(u 0 , u 1 , . . . , u k ). If u ni ≤ for all i larger than some i 0 then n i > k for all i ≥ i 0 .

For some choices of the sequence u, there is no c.e. set A such that n∈A u n is right-generic. An example is u n = 2 -n . We now show that if u n converges to 0 slowly then such c.e. sets exist.

Theorem IV.2. Let u = (u n ) n∈N be a computable sequence of positive real numbers with a computable sum. If u n+1 /u n converges to 1 then there exists a c.e. set A ⊆ N such that n∈A u n is right-generic.

The rest of the section is devoted to the proof of the theorem, and contains results of independent interest.

Let u = (u n ) n∈N be a sequence of positive real numbers converging to 0. What are the real numbers that can be expressed as n∈A u n for some set A ⊆ N? This problem

C

  . Separating simple and right-generic left-c.e. realsWe have seen that the problem of extending a computable function involves two classes of left-c.e. reals: the right-generic reals and the simple reals. How do these classes relate to each other? Proposition IV.1 and Theorem IV.1 imply the following inclusion.Corollary IV.1. Every non-computable simple left-c.e. real is right-generic.

has been studied by Graham [START_REF] Graham | On finite sums of reciprocals of distinct nth powers[END_REF]. We use one of his results (Proposition IV.3 below) but include a proof, as we need to check that it is effective.

We define the function f u : 2 N → R by f u (A) = n∈A u n , for A ⊆ N.

Definition IV.3. Given a sequence (u n ) n∈N , we define its tails t n = p>n u p . A sequence (u n ) n∈N has large tails if for every n, u n ≤ t n .

Proposition IV.3. If a sequence (u n ) n∈N converges to 0 and has large tails, then the image of f u is the whole interval [0, s] where s = n u n = f u (N).

Proof. We consider a greedy algorithm that given x ∈ [0, s], computes A such that f u (A) = x. A is defined by enumerating its elements in increasing order n 0 < n 1 < n 2 < . . .. First define n 0 as the minimal n such that u n ≤ x. Once n 0 < . . . < n i have been defined, let n i+1 be the minimal n > n i such that f u ({n 0 , . . . , n i , n}) ≤ x.

We show that this algorithm indeed produces a set A such that f u (A) = x. First observe that if for some i, n i is not defined, then as u n → 0 one has f u ({n 0 , . . . , n i-1 }) = x, so the result is proved. Now assume that n i is defined for all i. By construction, f u (A) ≤ x. If f u (A) < x, then as the sequence converges to 0 there is some n such that for all p ≥ n,

)+u n as the sequence has large tails, so n should be added to A in place of n+1. As a result, such an n does not exist, which means that A = N and that x > f (N) = s, contradicting the assumption on x.

Conversely, if the sequence u is moreover non-increasing and does not have large tails, then u n > t n for some n and the image of f u is not an interval, as it is disjoint from (t n , u n ).

The algorithm also shows that if (u n ) n∈N is a computable sequence with large tails and x is computable, then there is a computable set A such that f u (A) = x: if at some stage there is n such that f ({n 0 , . . . , n i , n}) = x, then one can take A to be finite, otherwise the inequalities to be tested in the algorithm are always strict and can be decided. Of course, one cannot get rid of these two cases because A cannot depend continuously on x: it lives in a disconnected space while x lives in R.

If u is a summable sequence then f u is a continuous function from the Cantor space to R. If (u n ) n∈N is computable and effectively summable (i.e. its sum is a computable real number, or equivalently its tails converge effectively to 0), then f u is a computable function.

We now have to build a c.e. set A such that f u (A) is rightgeneric. Instead of building A by hand, we will use a suitable notion of genericity for c.e. sets and show that such generic c.e. sets are mapped to right-generic reals.

First, the notion of genericity given in Definition III.2 is inappropriate. Let us recall that a co-infinite c.e. set A ⊆ N is hypersimple if for every computable sequence of pairwise disjoint finite sets F i , A contains F i for some i. C.e. sets that are generic from above are easily hypersimple (see [START_REF] Hoyrup | Irreversible Computable Functions[END_REF]).

Proposition IV.4. Let (u n ) n∈N be computable with a computable sum. If A is hypersimple, then n∈A u n is not rightgeneric.

Proof. We show that this number a is not even Kurtz-random, i.e. that it belongs to an effective closed set of Lebesgue measure 0 (which therefore does not contain any interval [a, a+δ], so a is not right-generic). Let P be the class of supersets of A.

It is an effective closed subset of the Cantor space, hence it is effectively compact and so is its image f (P ). We show that f (P ) has Lebesgue measure 0, which proves the result as f (A) ∈ f (P ).

Proof of the claim. We define a computable sequence of pairwise disjoint finite sets F i . To do this, we define an increasing computable sequence n i and define

(such an n exists as t n converge to 0). As A is hypersimple, it contains infinitely many F i 's.

We now proceed with the proof of the proposition.

Hence, the Lebesgue measure of f (P ) is at most 2 m+1 t n < 2 -m+1 . As m can be arbitrarily large, the Lebesgue measure of P is 0.

The reason underlying Proposition IV.4 is that a hypersimple set is too dense. In order to make f u (A) right-generic, we must force A to be sparse. We will do this by changing the topology on the Cantor space. To do this, we will need some further assumption about the sequence u n .

Lemma IV.3. Every slow sequence has large tails.

Proof. One has

Having large tails implies that the set of binary combinations is the whole interval [0, s] where s = n u n . We now define the new topology τ E .

Definition IV.5. For each n, let E n ⊆ N be the set of multiples of 2 n . Let P k,n = {A ⊆ N : A\[0, k] ⊆ E n }. The topology τ E is generated by the cylinders and the sets P k,n , k, n ∈ N.

It is an effective Polish topology. The class of finite subsets of N is dense in this topology. We introduce the notation A ⊆ * B which means that A is contained in B up to a finite set. For each n, the class {A : A ⊆ * E n } = k P k,n is a dense effective open set in the topology τ E . Let ↑ A denote the class of supersets of A. Now we have the material to state and prove the main result of this section.

The construction of the sought c.e. set is an instantiation of Theorem 4.1.1 in [START_REF] Hoyrup | Genericity of weakly computable objects[END_REF].

Corollary IV.2. There exists a c.e. set A that is generic from above in the topology τ E : for every effective τ E -open set, either A ∈ U or there exists a τ E -neighborhood

Now we have to check that the choice of the topology τ E makes A satisfy the sought property.

Theorem IV.3. Let (u n ) n∈N be computable with a computable sum. Assume that it is a slow sequence. If A ⊆ * E n for all n and A is generic from above in τ E , then n∈A u n is rightgeneric.

Proof. We show that for every neighborhood

which implies the result. Let S ⊆ N be infinite. We denote by (u n ) n∈S the subsequence (u ni ) i∈N where n 0 < n 1 < . . . is the increasing list of elements of S. We say that a set S ⊆ N is good if S is infinite and co-infinite and the subsequence (u n ) n∈S is slow.

Claim. For each n there exists k such that

Proof. The elements of E n \ E n+1 are the numbers n i = 2 n (2i + 1), i ∈ N. As u p+1 /u p converge to 1 and n i+1 -n i = 2 n+1 is constant, the ratio u ni+1 /u ni converges to 1 so it exceeds 1/2 for i larger than some i 0 . Let k = n i0 .

Consider a basic τ

By assumption, A ⊆ * E n , i.e. there exists k > k such that A \ [0, k ] ⊆ E n . We can take k > p. According to the preceding claim, we can take k large enough so that the set S = (E n \ E n+1 ) \ [0, k ] is good. Therefore, the subsequence (u n ) n∈S is slow hence has large tails, so Proposition IV.3 implies that letting s = n∈S u n > 0, every x ∈ [0, s] can be obtained as the image by f u of a subset of S. So every number in [f (A), f (A) + s] can be obtained as the image of A union a subset of S. Such a set is in

The method used here illustrates the usefulness of notions of genericity for c.e. sets. Instead of building a c.e. set satisfying given requirements, we find a suitable topology such that a c.e. set that is generic in that topology automatically satisfies these properties.

V. OUTSIDE THE LEFT-C.E. REALS

We have only considered the case when a is left-c.e. This choice might seem somewhat arbitrary.

Here we briefly investigate what happens for other classes of real numbers. It turns out that for most real numbers a the problem has a trivial solution: every computable function f : [0, a) → R has a computable extension over [0, 1]. One can think of it this way: given an increasing converging sequence a i , one can easily imagine plenty of ways to define a function on [0, a) where a is the limit of the sequence, by defining it separately on each [a i , a i+1 ] for instance. However if obtaining lower approximations of a is difficult or impossible, how could one possibly define a function on [0, a) converging at a otherwise than defining it on [0, 1] first and then restricting it to [0, a)?

In the first case, a still has some effectiveness.

Observe that in the statement we do not assume that f converges at a. The theorem implies in particular that every computable function over [0, a) must converge at a.

Proof. We first prove that f has a computable extension over [0, a]. There is a machine computing f on [0, a) whose domain is an effective G δ -set, i.e. it is n U n for a sequence of uniformly effective open sets U n [START_REF] Weihrauch | Computable Analysis: An Introduction[END_REF], [START_REF] Hemmerling | Effective metric spaces and representations of the reals[END_REF]. For each n, U n contains [0, a). If for some n, U n does not contain a then a = sup{q ∈ Q ∩ [0, 1] : [0, q] ⊆ U n } is left-c.e., contradicting the assumption. As a result, a belongs to the domain of the machine, which then computes a function over [0, a], obviously extending f .

We then apply the computable Tietze extension theorem [START_REF] Weihrauch | On computable metric spaces Tietze-Urysohn extension is computable[END_REF]: as [0, a] is an effective closed set and f : [0, a] → R is computable, it has a computable extension over [0, 1].

In a sense this result looks favorable, as it is a case where computable extension is always possible. It can also be interpreted negatively: there is no other way of defining a computable function over [0, a) than defining a computable function over [0, 1] and restricting it to [0, a).

The same result holds at the opposite side of the range of a, when it is sufficiently non-effective. Proposition V.2. Assume that a ∈ [0, 1] is not right-c.e. relative to the halting set. Every computable function f : [0, a) → R has a computable extension.

Proof. Let again U n be uniformly effective open sets such that the domain of the machine computing

to the halting set and c ≥ a so c > a. As a result, the machine computes an extension g of f on [0, c). Let q ∈ (a, c) be a rational number. Define h(x) = g(x) for x ≤ q and h(x) = g(q) for x ≥ q. h is a computable extension of f . We now show that this result does not hold in between, when a is effective but not too much. Theorem V.1. There exists a ∈ (0, 1) right-c.e. relative to the halting set and neither left-c.e. nor right-c.e., and a computable function f : [0, a] → R that admits no computable extension on [0, 1]. Lemma V.1. Let S be the class of sawtooth functions from Section III-B. Let φ : S N → C [0, 1] map a sequence (f n ) n∈N to n 4 -n f n . φ is one-to-one.

Proof. We prove that if φ maps two sequences f = (f n ) n∈N and g = (g n ) n∈N to the same function, then f 0 = g 0 . Let us first show that it implies the lemma. Let σ be the shiftoperator mapping a sequence to the same sequence without its first term. One has φ(f ) = f 0 + 4 -1 φ(σf ) and φ(g) = g 0 + 4 -1 φ(σg), so if φ(f ) = φ(g) and f 0 = g 0 then φ(σf ) = φ(σg) so one inductively has

The function on the right-hand side is 2/3-Lipschitz. The function f 0 -g 0 is Lipschitz hence it is differentiable almost everywhere with derivative h and f 0 (x) -g 0 (x) = x 0 h(t) dt as f 0 (0)-g 0 (0) = 0. Now, for almost every x, h(x) = f 0 (x)g 0 (x) ∈ {-2, -1, 0, 1, 2} as f 0 and g 0 are sawtooth functions. We saw that f 0 -g 0 is 2/3-Lipschitz, so |h(x)| ≤ 2/3 almost everywhere. As a result, h(x) = 0 almost everywhere, so f 0 -g 0 = 0.

The function φ is computable and the space S N is effectively compact, so K := φ(S N ) is effectively compact and φ -1 : K → S N is computable.

Let Tot = {n ∈ N : ϕ n is total}, where (ϕ n ) n∈N is some Gödel numbering of the partial computable functions. Let a = n∈Tot 2 -n . Tot is co-c.e. relative to the halting set and is not computable relative to the halting set, so a is right-c.e. relative to the halting set and not right-c.e. For each i, let A i = {n ∈ N : ϕ n (0), . . . , ϕ n (i) all halt}. The sets A i are uniformly c.e. and their intersection is Tot. Let h i be uniformly computable one-to-one enumerations of A i , a i = n∈Ai 2 -n and f i : [0, a i ) → R be the sawtooth function derived from h i as in Section III-A.

We define f : [0, a] → R by f = i∈N 4 -i f i . f is computable. It has an extension in K: for each i consider a linear ordering extending h i , take the associated sawtooth function g i extending f i , and take the sum i∈N 4 -i g i extending f . Applying Theorem II.1, if f has a computable extension g then g is essentially in K, i.e. there exists a rational number b > a such that g [0,b] has an extension in K. Let i be such that a i < b. The function φ remains computable and oneto-one when considering functions on [0, b] instead of [0, 1], hence its inverse is also computable. As a result on [0, b], g = i 4 -i g i for some computable sequence g i : [0, b] → R having extensions in S. As S has the computable extension property, g i has a computable extension in S. As a result, A i is an initial segment of a computable linear ordering which is not possible as A i is m-complete.

VI. OPEN QUESTIONS

We have investigated the computable extension problem in a restricted setting. Studying more general situations would be an interesting task. Let us list a few possible problems that could be studied in the future.

Is it true that for every c.e. set A there exists a one-toone computable enumeration h : N → N of A that cannot be extended to a computable linear ordering over N? It looks reasonable but we were not able to prove it.

When does f : [0, a) → R have a computable extension on [0, a]?

What happens when f is not assumed to converge to 0 at a? In particular when does a computable non-increasing function f : [0, a) → R admit a computable extension over [0, 1]?

It would also be interesting to investigate more thoroughly the case when a is right-c.e. relative to the halting set, but neither left-c.e. nor right-c.e.