1–LABEL:LastPageFeb. 15, 2018Aug. 31, 2018

# A Galois connection between Turing jumps and limits

Vasco Brattka  Faculty of Computer Science, Universität der Bundeswehr
München, Germany and Department of Mathematics and Applied Mathematics,
University of Cape Town, South Africa<EMAIL_ADDRESS>
###### Abstract.

Limit computable functions can be characterized by Turing jumps on the input
side or limits on the output side. As a monad of this pair of adjoint
operations we obtain a problem that characterizes the low functions and dually
to this another problem that characterizes the functions that are computable
relative to the halting problem. Correspondingly, these two classes are the
largest classes of functions that can be pre or post composed to limit
computable functions without leaving the class of limit computable functions.
We transfer these observations to the lattice of represented spaces where it
leads to a formal Galois connection. We also formulate a version of this
result for computable metric spaces. Limit computability and computability
relative to the halting problem are notions that coincide for points and
sequences, but even restricted to continuous functions the former class is
strictly larger than the latter. On computable metric spaces we can
characterize the functions that are computable relative to the halting problem
as those functions that are limit computable with a modulus of continuity that
is computable relative to the halting problem. As a consequence of this result
we obtain, for instance, that Lipschitz continuous functions that are limit
computable are automatically computable relative to the halting problem. We
also discuss 1–generic points as the canonical points of continuity of limit
computable functions, and we prove that restricted to these points limit
computable functions are computable relative to the halting problem. Finally,
we demonstrate how these results can be applied in computable analysis.

###### Key words and phrases:

Computable analysis, limit computability, computability relative to the
halting problem, lowness, 1–genericity, represented spaces, Galois
connections.

###### 1991 Mathematics Subject Classification:

[Theory of computation]: Logic; [Mathematics of computing]: Continuous
mathematics.

##  1\. Introduction

Limit computable functions have been studied for a long time. In computability
theory limits appear, for instance, in the form of Shoenfield’s limit lemma
[46]. In algorithmic learning theory they have been introduced by Gold [22].
Later, limit computable functions have been studied by Wagner [50, 51], who
calls them _Turing operators of the first kind_ (and he attributes this class
to Freĭvald [18]). Wagner discusses composition and also normal form theorems.
In computable analysis limit computations were studied by Freund [19] who
introduced Turing machines that can revise their output as well as non-
deterministic Turing machines. Later, similar machines were systematically
studied by Ziegler [56, 55]. Limit computable real numbers were analyzed by
Freund and Staiger [20] and by Zheng and Weihrauch [53] and others. On the
other hand, Ho [25, 26] studied functions in analysis that are computable
relative to the halting problem.

Many of these results are scattered in the literature, and it remains somewhat
unclear how all these results are related. Some clarity can be brought into
the picture if one starts with the notion of a limit computable function and
develops it systematically. It turns out that at the heart of such a
development there is an adjoint situation that is related to the fact that
limit computations can either be described with limits on the output side or
with Turing jumps on the input side. Shoenfield’s limit lemma is the non-
uniform correlate of this observation. From this perspective functions
computable relative to the halting problem and low functions are natural
notions that should be studied alongside with limit computable functions,
since they constitute the largest classes of functions that can be post or pre
composed with limit computable functions without leaving the class of limit
computable functions. We will develop these notions systematically in sections
2 and 3.111We note that an unpublished draft of some of the material presented
here was circulated since 2007 and it has influenced some of the references,
such as joint work by the author with de Brecht and Pauly [7]. The material
presented in section 3 and everything based on it has only been developed
recently. Together with these notions we also study $1$–generic points, as
these are the canonical points of continuity of limit computable functions.

In section 4 we transfer these results to the setting of represented spaces
and hence to other data types. The crucial notion here is the notion of a jump
of a representation that was introduced by Ziegler [56, 55] and further
generalized by de Brecht [15]. On the level of represented spaces the adjoint
situation between limits and Turing jumps can formally be expressed as a
Galois connection. We also study how the jump of a represented space interacts
with other constructions on represented spaces such as building products and
exponentials.

In section 5 we transfer our results to the setting of computable metric
spaces. The limit normal form for limit computable functions can easily be
expressed using limits in computable metric spaces and for the jump normal
form one can use a general jump operation on computable metric spaces. We also
transfer a characterization of $1$–generic points to the level of computable
metric spaces.

In section 6 we continue to study mostly computable metric spaces and
specifically the relation between limit computable functions and functions
computable relative to the halting problem. One characterization shows that
functions that are computable relative to the halting problem are exactly
those continuous limit computable functions that admit a global modulus of
continuity that is computable relative to the halting problem. We also provide
several examples of functions of different type that show that not all
continuous limit computable functions are computable relative to the halting
problem. However, we can provide oracle classes that are sufficient to compute
limit computable functions that are continuous, uniformly continuous and
Lipschitz continuous, respectively. In particular for Lipschitz continuous
functions limit computability and computability with respect to the halting
problem coincide.

We close this article with section 7 in which we demonstrate how some known
results can easily be derived using the techniques provided in this article.
We also include some simple new applications. The discussed examples also
highlight connections between results that are seemingly unrelated or
scattered in other sources.

##  2\. Limit computability

In this section we are going to characterize limit computable functions in
different ways. We start with recalling the definition. Limit computable
functions are defined on Turing machines that have a two-way output tape, and
these machines are allowed to revise their output.

######  Definition  (Limit computable functions).

A function $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
is called _limit computable_ , if there exists a Turing machine $M$ that upon
any input $p\in{\mathrm{dom}}(F)$ computes $F(p)$ on its two-way output tape
in the long run such that on any output position $n\in{\mathbb{N}}$ after a
finite number of steps the output is $F(p)(n)$ and will not be changed
anymore.

If the Turing machine does only change the entire output (over all
$n\in{\mathbb{N}}$) finitely many times for each fixed input $p$, then $F$ is
called _computable with finitely many mind changes_. This is a strengthening
of the notion of limit computability.

It is clear that all computable maps are limit computable and limit computable
maps are obviously closed under restriction. The additional flexibility to
revise the output tape gives additional power to limit machines that ordinary
Turing machines do not have. As examples we mention some discontinuous
functions that are not computable, but limit computable. For the definition we
use tupling functions. We define $\langle
n,k\rangle:=\frac{1}{2}(n+k)(n+k+1)+k$, $\langle p,q\rangle(2n):=p(n)$ and
$\langle p,q\rangle(2n+1):=q(n)$, $\langle
p_{0},p_{1},p_{2},....\rangle\langle n,k\rangle:=p_{n}(k)$, and $\langle
n,p\rangle:=np$ for all $p,q,p_{i}\in{\mathbb{N}}^{\mathbb{N}}$ and
$n,k\in{\mathbb{N}}$. By $\widehat{n}=nnn...\in{\mathbb{N}}^{\mathbb{N}}$ we
denote the constant sequence with value $n\in{\mathbb{N}}$.

######  Example  (Limit computable maps).

The following maps are limit computable but not continuous and hence not
computable:

  1. (1)

The _equality test for zero_

${\mathsf{{E}}}:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}},p\mapsto\left\\{\begin{array}[]{ll}\widehat{1}&\mbox{if
$p=\widehat{0}$}\\\ \widehat{0}&\mbox{otherwise}\end{array}\right.$

  2. (2)

The _limit map_

$\lim:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}},\langle
p_{0},p_{1},p_{2},...\rangle\mapsto\lim_{i\to\infty}p_{i}.$

  3. (3)

The _Turing jump_
${\mathsf{{J}}}:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ by

${\mathsf{{J}}}(p)(i):=\left\\{\begin{array}[]{ll}1&\mbox{if Turing machine
$i$ halts upon input $p$}\\\ 0&\mbox{otherwise}\end{array}\right.$

for all $p\in{\mathbb{N}}^{\mathbb{N}}$ and $i\in{\mathbb{N}}$.

The function ${\mathsf{{E}}}$ is even computable with finitely many mind
changes.

By $\lim_{\Delta}$ we denote the restriction of $\lim$ to convergent sequences
with respect to the discrete topology on ${\mathbb{N}}^{\mathbb{N}}$. In some
sense one can say that the limit map and ${\mathsf{{J}}}$ are not only some
limit computable maps, but prototypes of limit computable maps. Before we can
prove a formal version of this statement, we first discuss compositions of
computable and limit computable maps that turn out to be limit computable.

######  Proposition  (Composition).

If $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ is limit
computable and
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ is
computable, then $F\circ G$ and $G\circ F$ are both limit computable.

###### Proof.

Let $M_{F}$ be a limit machine computing $F$ and $M_{G}$ an ordinary Turing
machine computing $G$. Then a limit machine $M$ computing $F\circ G$ can just
be obtained by composing the two machines $M_{F}$ and $M_{G}$ in the
straightforward way.

A limit machine $M^{\prime}$ for $G\circ F$ can also be constructed by
composing the machines $M_{F}$ and $M_{G}$. However, the composition has to be
done such that if $M_{F}$ changes the content of some output cell $n$, then
the computation of $M_{G}$ has to be restarted at time step $n$ of its program
(which is sufficient to guarantee that $M_{G}$ has not yet seen the content of
cell $n$). Since the output of $M_{F}$ of any finite length eventually
stabilizes and $M_{G}$ uses a one-way output tape, it follows that
$M^{\prime}$ produces a converging output in this way for any input
$p\in{\mathrm{dom}}(G\circ F)$. ∎

It is easy to see that the first statement of the proposition can even be
strengthened in the following way.

######  Proposition  (Composition with finitely many mind changes).

If $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ is limit
computable and
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ is
computable with finitely many mind changes, then $F\circ G$ is limit
computable.

For the composition $G\circ F$ of functions as in Proposition 2 the strategy
of the corresponding proof of Proposition 2 does not work in general. In fact,
it is not too difficult to construct a counterexample.

######  Example  (Composition).

The equality test ${\mathsf{{E}}}$ is computable with finitely many mind
changes, and the limit map $\lim$ is limit computable, but
${\mathsf{{E}}}\circ\lim$ is not limit computable.

We leave the proof to the reader. Now we provide a very useful
characterization of limit computable functions. This result is also implicit
in the work of Wagner [50].

######  Theorem  (Limit normal form).

A function $G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
is limit computable if and only if there exists a computable function
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$, such that
$G=\lim\circ\;F$.

###### Proof.

By Example 2 $\lim$ is limit computable. It follows from Proposition 2 that if
$F$ is computable, then $\lim\circ\;F$ is limit computable.

Conversely, if $G$ is limit computable, then we construct a one-way output
Turing machine $M_{F}$ that computes a function
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$. This
machine $M_{F}$ internally simulates a limit machine $M_{G}$ for $G$ on input
$p$. The machine $M_{F}$ successively produces an output $\langle
q_{0},q_{1},...\rangle$ in steps $\langle i,j\rangle=0,1,2,...$. In step
$\langle i,j\rangle$ machine $M_{F}$ simulates $M_{G}$ for $i$ time steps
beyond the point where $M_{G}$ has filled its $j$–th output position for the
first time. Machine $M_{F}$ writes the resulting content of the simulated
output of $M_{G}$ in the $j$–th position into its own output $q_{i}(j)$. If
the simulated $j$–th position eventually stabilizes, then
$\lim_{i\to\infty}q_{i}(j)$ exists and coincides with the final value of the
$j$–th position $G(p)(j)$. Thus the machine $M_{F}$ computes a function
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with
$G=\lim\circ\;F$. Here $F$ is restricted to ${\mathrm{dom}}(G)$. ∎

We note that the limit normal form theorem allows us to study limit computable
functions in terms of ordinary computable functions and without considering
limit machines. The particular output behavior of limit machines can be
expressed directly using the limit map. We also obtain the following
characterization of limit computable functions as pointwise limits of a
sequence of computable functions.

######  Corollary  (Pointwise limit).

A function $G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
is limit computable if and only if there is a computable sequence
$(F_{n})_{n\in{\mathbb{N}}}$ of computable functions
$F_{n}:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with
${\mathrm{dom}}(G)\subseteq{\mathrm{dom}}(F_{n})$ and such that
$\lim_{n\to\infty}F_{n}(p)=G(p)$ for all $p\in{\mathrm{dom}}(G)$.

Theorem 2 together with Proposition 2 yield the following corollary.

######  Corollary .

For any computable function
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ there
exists a computable function
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$\lim\circ\,G=F\circ\lim$.

Corollary 2 also holds with continuity instead of computability in both
occurrences. We note that the computable functions $F$ do not constitute the
largest class of functions for which there is a computable $G$ with $\lim\circ
G=F\circ\lim$. In Corollary 3 we extend this result to functions that are
computable relative to the halting problem. Maps that satisfy the same
property as the limit map in Corollary 2 have been called _jump operators_ [7,
15] or _transparent_ [9].

######  Definition  (Transparency).

A function $T:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
is called _transparent_ if for every computable
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ there
exists a computable function
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$T\circ G=F\circ T$.

It is easy to see that not all functions are transparent, but the class of
transparent functions is reasonably large.

######  Proposition  (Transparency).

The class of transparent functions
$T:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ forms a
monoid with respect to composition, i.e., the identity is transparent, and
transparent functions are closed under composition.

It is clear that limit computable maps do not necessarily map computable
inputs to computable outputs. However, they map computable inputs to limit
computable outputs.

######  Definition  (Limit computable points).

A point $p\in{\mathbb{N}}^{\mathbb{N}}$ is called _limit computable_ , if
there exists a computable sequence $(p_{i})_{i\in{\mathbb{N}}}$ in
${\mathbb{N}}^{\mathbb{N}}$ such that $p=\lim_{i\to\infty}p_{i}$.

It follows directly from the limit normal form theorem (Theorem 2) and the
fact that computable maps map computable inputs to computable outputs that
limit computable maps map computable inputs to limit computable outputs.

######  Corollary .

If $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ is limit
computable and $p\in{\mathrm{dom}}(F)$ is computable, then $F(p)$ is limit
computable.

It also follows from the limit normal form theorem (Theorem 2) that a point
$p\in{\mathbb{N}}^{\mathbb{N}}$ is limit computable if and only if it is the
value of a constant limit computable map
$c:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$.

We now study the Turing jump ${\mathsf{{J}}}$, and we first prove that its
inverse is computable. Even though ${\mathsf{{J}}}$ is not continuous, it is
injective and has a computable inverse.

######  Proposition  (Jump inversion).

The Turing jump operator ${\mathsf{{J}}}$ is injective, and its partial
inverse
${\mathsf{{J}}}^{-1}:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
is computable.

###### Proof.

There exists a computable function $r:{\mathbb{N}}\to{\mathbb{N}}$ such that
the Turing machine with code $r\langle n,k\rangle$ halts upon input
$p\in{\mathbb{N}}^{\mathbb{N}}$ if and only if $p(n)=k$. The function
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ defined by

$F(q)(n):=\min\\{k\in{\mathbb{N}}:qr\langle n,k\rangle=1\\}$

for all $q\in{\mathbb{N}}^{\mathbb{N}}$, $n\in{\mathbb{N}}$ and
${\mathrm{dom}}(F):=\\{q\in{\mathbb{N}}^{\mathbb{N}}:(\forall n)(\exists
k)\;qr\langle n,k\rangle=1\\}$ is computable. We obtain

$F\circ{\mathsf{{J}}}(p)(n)=\min\\{k\in{\mathbb{N}}:{\mathsf{{J}}}(p)(r\langle
n,k\rangle)=1\\}=\min\\{k\in{\mathbb{N}}:p(n)=k\\}=p(n)$

for all $p\in{\mathbb{N}}^{\mathbb{N}}$ and $n\in{\mathbb{N}}$, i.e.,
$F\circ{\mathsf{{J}}}={\mathrm{id}}$. This implies that ${\mathsf{{J}}}$ is
injective and ${\mathsf{{J}}}^{-1}=F|_{{\mathrm{range}}({\mathsf{{J}}})}$ is
computable. ∎

We also write $p^{\prime}:={\mathsf{{J}}}(p)$, and we call $p^{\prime}$ the
_Turing jump_ of $p$, and we call $0^{\prime}:={\mathsf{{J}}}(\widehat{0})$
the _halting problem_. We note that the Turing jump operator considered as a
map on Turing degrees is not injective.222There are
$p\mathop{\not\equiv_{\mathrm{T}}}q$ such that
$p^{\prime}\mathop{\equiv_{\mathrm{T}}}q^{\prime}$. We mention that
Proposition 2 also implies that any point can be reduced to its Turing jump,
i.e., $p\mathop{\leq_{\mathrm{T}}}p^{\prime}$ (of course, this reduction is
known to be strict, which can be proved by an easy diagonalization argument).

It is perhaps surprising that there is a dual version of the limit normal form
theorem that characterizes limit computation by an input modification with the
help of Turing jumps instead of an output modification with limits. This shows
that in some sense Turing jumps and topological limits are adjoint to each
other. An analogous result can be found in the work of Wagner [50].

######  Theorem  (Jump normal form).

A function $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
is limit computable, if and only if there exists a computable function
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$F=G\circ{\mathsf{{J}}}$.

###### Proof.

By Example 2 the Turing jump operator
${\mathsf{{J}}}:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ is
limit computable. Hence for any computable
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ the
composition $G\circ{\mathsf{{J}}}$ is limit computable by Proposition 2.

Let now $M_{F}$ be a limit Turing machine that computes
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$. We
describe a Turing machine $M_{G}$ that computes a function
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with
$F(p)=G\circ{\mathsf{{J}}}(p)$ for all $p\in{\mathrm{dom}}(F)$. There exists a
computable function $r:{\mathbb{N}}\to{\mathbb{N}}$ such that the Turing
machine with code $r\langle n,t\rangle$ halts upon input $p$ if and only if
$M_{F}$ on input $p$ changes the output cell $n$ after more than $t$ steps.
Now $M_{G}$ on input $q$ works as follows: it simulates the machine $M_{F}$ on
input $p={\mathsf{{J}}}^{-1}(q)$, where ${\mathsf{{J}}}^{-1}$ is the partial
inverse of the Turing jump operator that is computable by Proposition 2, and
writes the output to some working tape. After simulating $M_{F}$ for $t$ steps
at most the first $k$ cells on this working tape have been used for some
$k\in{\mathbb{N}}$. In this situation $M_{G}$ checks $qr\langle n,t\rangle$
for all $n=0,...,k$ and when the result is $0$ for some initial segment
$n=0,...,j$, then $M_{G}$ copies the content of those cells $n=0,...,j$ to the
output tape that have not yet been written to the output. This algorithm
ensures that only those output cells which have already stabilized are copied
to the output. Thus, $M_{G}$ operates with a one-way output tape and computes
a function $G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
with $F(p)=G\circ{\mathsf{{J}}}(p)$ for all $p\in{\mathrm{dom}}(F)$. Since
${\mathsf{{J}}}$ is injective, one can restrict $G$ such that one obtains
$F=G\circ{\mathsf{{J}}}$. ∎

We obtain the following corollary, which is somehow dual to the statement of
Corollary 2.

######  Corollary .

For any computable function
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ there
exists a computable function
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
${\mathsf{{J}}}\circ F=G\circ{\mathsf{{J}}}$.

It is clear that ${\mathsf{{J}}}$ and $\lim$ cannot be swapped in Corollaries
2 and 2. In particular, ${\mathsf{{J}}}$ is not transparent, since it has no
computable values in its range. However, it is not too difficult to see that
${\mathsf{{J}}}^{-1}$ is transparent.

It is a consequence of Corollary 2 that the Turing jump operator is monotone
with respect to Turing reducibility.

######  Corollary  (Monotonicity of Turing jumps).

$q\mathop{\leq_{\mathrm{T}}}p\Longrightarrow
q^{\prime}\mathop{\leq_{\mathrm{T}}}p^{\prime}$ for all
$p,q\in{\mathbb{N}}^{\mathbb{N}}$.

We also mention that the jump normal form theorem (Theorem 2) yields as a non-
uniform corollary a version of Shoenfield’s limit lemma [46].

######  Corollary  (Shoenfield’s limit lemma 1959).

A point $p\in{\mathbb{N}}^{\mathbb{N}}$ is limit computable if and only if
$p\mathop{\leq_{\mathrm{T}}}0^{\prime}$.

One can prove relativized forms of the jump normal form theorem (Theorem 2)
and the limit normal form theorem (Theorem 2). However, the exact
relativization needs some care. For every $q\in{\mathbb{N}}^{\mathbb{N}}$ we
define the _relativized jump operator_
${\mathsf{{J}}}_{q}:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ by
${\mathsf{{J}}}_{q}(p):={\mathsf{{J}}}\langle q,p\rangle$. We say that
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ is _limit
computable relative to_ $q\in{\mathbb{N}}^{\mathbb{N}}$ if there exists a
limit computable
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$F(p)=G\langle q,p\rangle$ for all $p\in{\mathrm{dom}}(F)$. Now the following
theorem can be proved along the lines of the above results.

######  Theorem  (Relativized limit computability).

The following are equivalent for $q\in{\mathbb{N}}^{\mathbb{N}}$:

  1. (1)

$F$ is limit computable relative to $q$,

  2. (2)

$F=\lim\circ\,G$ for some $G$ that is computable relative to $q$,

  3. (3)

$F=G\circ{\mathsf{{J}}}_{q}$ for some $G$ that is computable.

The symmetry between the two normal forms does not fully extend to the
relativized case since oracles act on the input side, and hence we need to use
either functions that are computable relative to $q$ or the relativized jump
${\mathsf{{J}}}_{q}$. Related to this observation the equivalence expressed in
the two normal form theorems is not fully uniform and, in fact,
${\mathsf{{J}}}^{-1}$ is not transparent in a topological sense (see [7,
Proposition 9.13]).

It is rarely mentioned that $1$–generic points as they are used in
computability theory [47] can be characterized as points of continuity of the
Turing jump ${\mathsf{{J}}}$. This was noticed in [7, Lemma 9.3].

######  Definition  ($1$–generic).

A point $p\in{\mathbb{N}}^{\mathbb{N}}$ is called _$1$ –generic_ if and only
if ${\mathsf{{J}}}$ is continuous at $p$.

It is easy to see that $1$–generic points cannot be computable. The following
characterization of $1$–generic points is a consequence of Theorem 2. The
$1$–generic points are exactly those at which every limit computable function
is continuous.

######  Corollary  ($1$–generic points).

A point $p\in{\mathbb{N}}^{\mathbb{N}}$ is $1$–generic if and only if every
limit computable function
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with
$p\in{\mathrm{dom}}(F)$ is continuous at $p$.

While the “only if” direction is a consequence of Theorem 2, one obtains the
“if” direction by applying the statement to $F={\mathsf{{J}}}$. We note that
there are limit computable functions (such as the limit map $\lim$) that do
not have any $1$–generics in their domain, simply because they are not
continuous at any point.

It is easy to see that restricted to $1$–generics the Turing jump operator is
continuous and computable relative to the halting problem.

######  Proposition  (Jump on $1$–generics).

The Turing jump operator
${\mathsf{{J}}}:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}},p\mapsto
p^{\prime}$ restricted to the set of $1$–generics is computable relative to
the halting problem.

###### Proof.

The sets

  1. (1)

$A:=\\{(w,i)\in{\mathbb{N}}^{*}\times{\mathbb{N}}:$ the $i$–th Turing machine
halts on all extensions of $w\\}$,

  2. (2)

$B:=\\{(w,i)\in{\mathbb{N}}^{*}\times{\mathbb{N}}:$ the $i$–th Turing machine
halts on no extension of $w\\}$

are both computable relative to $0^{\prime}$. Given a $1$–generic
$p\in{\mathbb{N}}^{\mathbb{N}}$ it is clear that for each $i\in{\mathbb{N}}$
there is a $w\sqsubseteq p$ such that $(w,i)\in A$ or $(w,i)\in B$. Depending
on the answer we know that ${\mathsf{{J}}}(p)(i)=1$ or
${\mathsf{{J}}}(p)(i)=0$. Hence, ${\mathsf{{J}}}$ restricted to $1$–generics
is computable relative to the halting problem. ∎

As a consequence of the jump normal form (Theorem 2) we obtain that every
limit computable function is computable relative to the halting problem, when
restricted to the $1$–generic inputs.

######  Corollary  (Limit computability on $1$–generics).

Restricted to $1$–generics every limit computable
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ is
computable relative to the halting problem.

As a non-uniform corollary of Proposition 2 we obtain that all $1$–generics
are _generalized low_ , a property that is made more precise in the next well-
known corollary [28, Lemma 2].

######  Corollary  (Jockusch 1977).

$p^{\prime}\mathop{\equiv_{\mathrm{T}}}\langle p,0^{\prime}\rangle$ for all
$1$–generics $p\in{\mathbb{N}}^{\mathbb{N}}$.

Here the reduction $p^{\prime}\mathop{\leq_{\mathrm{T}}}\langle
p,0^{\prime}\rangle$ follows directly from Proposition 2, and the inverse
reduction even holds for arbitrary $p\in{\mathbb{N}}^{\mathbb{N}}$.

The points whose jump is below $0^{\prime}$ also have a special name, they are
called _low_.

######  Definition  (Low points).

A point $p\in{\mathbb{N}}^{\mathbb{N}}$ is called _low_ , if its Turing jump
$p^{\prime}$ is limit computable.

It is clear that all computable points are low, and all limit computable
$1$–generics are low by Corollary 2. One can use this observation to show that
the class of low points also contains non-computable points. Using the _low
map_ ${\mathsf{{L}}}:={\mathsf{{J}}}^{-1}\circ\lim$ we obtain the following
characterization of low points [7, Lemma 8.2].

######  Corollary  (Low points).

A point $p\in{\mathbb{N}}^{\mathbb{N}}$ is low if and only if there is a
computable $q\in{\mathbb{N}}^{\mathbb{N}}$ such that ${\mathsf{{L}}}(q)=p$.

It follows from Corollaries 2 and 2 that computable functions map low inputs
to low outputs. In [7] low functions were introduced that were further studied
in [9, 11].

######  Definition  (Low functions).

A function $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
is called _low_ if there is a computable
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$F={\mathsf{{L}}}\circ G$.

This definition captures the idea that the result of $F$ is computed as a low
point. It is clear that low functions map computable inputs to low outputs. We
obtain the following closure properties under composition.

######  Proposition  (Composition with low functions).

Let $F,G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ be
functions. If $F$ and $G$ are low then so is $G\circ F$. If $G$ is limit
computable and $F$ is low, then $G\circ F$ is limit computable.

###### Proof.

Both observations are based on the jump normal form theorem (Theorem 2) that
yields a computable
$R:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with
$\lim=R\circ{\mathsf{{J}}}$. By Corollary 2 we also have a computable
$S:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with
$R\circ\lim=\lim\circ S$. This implies
${\mathsf{{L}}}\circ{\mathsf{{L}}}={\mathsf{{J}}}^{-1}\circ\lim\circ{\mathsf{{J}}}^{-1}\circ\lim={\mathsf{{J}}}^{-1}\circ
R\circ{\mathsf{{J}}}\circ{\mathsf{{J}}}^{-1}\circ\lim={\mathsf{{L}}}\circ S$
and
$\lim\circ{\mathsf{{L}}}=R\circ{\mathsf{{J}}}\circ{\mathsf{{J}}}^{-1}\circ\lim=R\circ\lim$.
The cases of the composition of general low and limit computable functions can
easily be derived from these observations. ∎

In fact, the low functions form the largest class of functions that can be
composed with limit computable functions from the left without leaving the
class of limit computable functions (see also [11, Proposition 14.16] for a
related result).

######  Corollary  (Low functions).

A function $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
is low if and only if $G\circ F$ is limit computable for every limit
computable $G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$.

The “only if” direction is a direct consequence of Proposition 2. The “if”
direction follows from the limit normal form theorem if one applies the
assumption to $G={\mathsf{{J}}}$. As a consequence of Proposition 2 we get the
following corollary.

######  Corollary  (Finite mind changes are low).

Every function
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ that is
computable with finitely many mind changes is low.

Hence, in contrast to low points $p\in{\mathbb{N}}^{\mathbb{N}}$, we have a
lot of natural examples of low functions, such as the equality test
${\mathsf{{E}}}$.

We close this section by mentioning briefly that there is a characterization
of functions that are computable with finitely many mind changes that is
analogous to Theorem 2.

######  Theorem  (Discrete limit normal form).

A function $G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
is computable with finitely many mind changes if and only if there exists a
computable function
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$, such that
$G=\lim\nolimits_{\Delta}\circ\;F$.

We leave the simple proof to the reader (see [7]).

##  3\. Computability Relative to the Halting Problem

Now we consider functions that are computable relative to the halting problem
$0^{\prime}$. It turns out that they play a dual rôle to the low functions
that are characterized in terms of
${\mathsf{{L}}}={\mathsf{{J}}}^{-1}\circ\lim$. The functions that are
computable relative to the halting problem can be characterized in terms of
${\mathsf{{H}}}:={\mathsf{{J}}}\circ\lim^{-1}:{\mathbb{N}}^{\mathbb{N}}\rightrightarrows{\mathbb{N}}^{\mathbb{N}}$.

The first result shows that ${\mathsf{{H}}}$ is computable relative to the
halting problem. In order to prove this we need to invert limits such that we
obtain control on the jump of the resulting converging sequence. Roughly
speaking, this is possible since there are many sequences converging to a
given point, and this gives us enough freedom to choose a suitable one. We
recall that the _composition_ of two multi-valued functions $f:\subseteq
X\rightrightarrows Y$ and $g:\subseteq Y\rightrightarrows Z$ is defined by
$(g\circ f)(x):=\\{z\in Z:(\exists y\in f(x))\;z\in g(y)\\}$ with
${\mathrm{dom}}(g\circ f):=\\{x\in X:x\in{\mathrm{dom}}(f)$ and
$f(x)\subseteq{\mathrm{dom}}(g)\\}$. A multi-valued
$f:\subseteq{\mathbb{N}}^{\mathbb{N}}\rightrightarrows{\mathbb{N}}^{\mathbb{N}}$
is called _computable (relative to some oracle $q$)_ if there is a single-
valued $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with
the corresponding property and such that $F(p)\subseteq f(p)$ for all
$p\in{\mathrm{dom}}(f)$ and ${\mathrm{dom}}(f)\subseteq{\mathrm{dom}}(F)$. We
recall that a function
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ is called
_computable relative to some oracle $q\in{\mathbb{N}}^{\mathbb{N}}$_ if there
is some computable function
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$F(p)=G\langle q,p\rangle$ for all $p\in{\mathrm{dom}}(F)$. In terms of
computability theory, the next proof uses the _finite extension method_.

######  Theorem  (Limit inversion).

${\mathsf{{H}}}={\mathsf{{J}}}\circ\lim^{-1}$ is computable relative to the
halting problem.

###### Proof.

We need to show that there exists a function
$I:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with $\lim\circ
I={\mathrm{id}}$ and such that ${\mathsf{{J}}}\circ I$ is computable relative
to $0^{\prime}$. Given $p\in{\mathbb{N}}^{\mathbb{N}}$ we describe the
computation of $I$ relative to $0^{\prime}$ by an inductive construction in
$i\in{\mathbb{N}}$. We start with $w_{0}:=\varepsilon\in{\mathbb{N}}^{*}$ and
$t_{0}:=0\in{\mathbb{N}}$. Given a finite sequence of words
$w_{0},...,w_{t_{i}}\in{\mathbb{N}}^{*}$ together with numbers
$t_{0}<t_{1}<...<t_{i}$ and bits $b_{0},...,b_{i-1}\in\\{0,1\\}$ we describe
how we determine $t_{i+1}\in{\mathbb{N}}$,
$w_{t_{\underline{i}}+1},...,w_{t_{\underline{i+1}}}\in{\mathbb{N}}^{*}$ and
$b_{i}\in\\{0,1\\}$ in stage $i$ of the construction.333For notational
clarity, we have underlined the indexes of $t$; the line has no mathematical
meaning. We let $r_{0}:=p|_{0}w_{0}\widehat{0}=\widehat{0}$ and
$r_{n+1}:=(p|_{n+1}w_{t_{\underline{n}}+1}\widehat{0},...,p|_{n+1}w_{t_{\underline{n+1}}}\widehat{0})$
for all $n<i$. Now we consider the question whether the $i$–th Turing machine
halts on

$\langle
r_{0},...,r_{i},p|_{i+1}q_{t_{i}+1},p|_{i+1}q_{t_{i}+2},p|_{i+1}q_{t_{i}+3},...\rangle$

for some $q_{t_{i}+n}\in{\mathbb{N}}^{\mathbb{N}}$ with $n\in{\mathbb{N}}$.
Whether or not this is the case can be decided with the help of $0^{\prime}$
since the answer depends only on the finite portion $p|_{i+1}$ of $p$ read so
far. If the outcome of the decision is positive, then already a finite number
$q_{t_{\underline{i}}+1},...,q_{t_{\underline{i+1}}}\in{\mathbb{N}}^{\mathbb{N}}$
for some $t_{i+1}>t_{i}$ and, in fact, finite prefixes of these are sufficient
for the machine $i$ to halt. In this case we can compute such a $t_{i+1}$ and
corresponding words $w_{t_{i}+n}\in{\mathbb{N}}^{*}$ such that
$q_{j}:=w_{j}\widehat{0}$ for $j\in\\{t_{i}+1,...,t_{i+1}\\}$ satisfy the
condition, and we set $b_{i}:=1$. Otherwise, if the outcome of the decision is
negative, then we choose $w_{t_{i}+1}:=\varepsilon$, $t_{i+1}:=t_{i}+1$ and
$b_{i}:=0$. If we continue inductively in this way, then we can compute
$I(p):=\langle r_{0},r_{1},r_{2},...\rangle$ with the help of $0^{\prime}$
uniformly in $p$. Since we have used longer and longer prefixes $p|_{n}$ of
$p$ in the construction of the $r_{n}$, the value $I(p)$ satisfies $\lim\circ
I(p)=p$. Moreover, the construction guarantees that we can compute
${\mathsf{{J}}}\circ I$ with the help of $0^{\prime}$, namely
${\mathsf{{J}}}\circ I(p)=(b_{0},b_{1},b_{2},...)$. ∎

We note that ${\mathsf{{H}}}$ is, in particular, continuous, and
${\mathsf{{H}}}^{-1}=\lim\circ{\mathsf{{J}}}^{-1}$ is computable by Theorem 2.
Theorem 3 yields the following characterization of functions computable
relative to the halting problem. The interesting point of the following
theorem is not that there is an object ${\mathsf{{H}}}$ that characterizes
functions that are computable relative to the halting problem (the problem
$\langle{\mathrm{id}}\times\chi_{0^{\prime}}\rangle$ with the characteristic
function $\chi_{0^{\prime}}$ of the halting problem would be a simpler such
example), but the point is that our particular ${\mathsf{{H}}}$ has this
property.

######  Theorem  (Computability relative to the halting problem).

A function $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
is computable relative to the halting problem if and only if there is a
computable function
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$F=G\circ{\mathsf{{H}}}$.

###### Proof.

By Theorem 3 ${\mathsf{{H}}}$ is computable relative to $0^{\prime}$. Hence
$G\circ{\mathsf{{H}}}$ is computable relative to the halting problem for every
computable $G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$.
Let now $F$ be computable relative to the halting problem $0^{\prime}$. Then
there is a computable
$S:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$, such that
$F(p)=S\langle 0^{\prime},p\rangle$ for all $p\in{\mathrm{dom}}(F)$. By
Theorem 2 we know that there is a computable function
$T:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$T\circ{\mathsf{{J}}}=\lim$, i.e., $T\circ{\mathsf{{H}}}={\mathrm{id}}$. On
the other hand, there is a computable function $r:{\mathbb{N}}\to{\mathbb{N}}$
such that Turing machine $r(i)$ halts on all inputs if and only if machine $i$
halts on input $\widehat{0}$. Hence
${\mathsf{{J}}}(\widehat{0})(i)={\mathsf{{J}}}(p)(r(i))$ for all
$p\in{\mathbb{N}}^{\mathbb{N}}$ and $i\in{\mathbb{N}}$. Then
$R:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with
$R(q)(i):=qr(i)$ is computable and so is $G:=S\circ\langle R,T\rangle$. We
obtain

$F(p)=S\langle{\mathsf{{J}}}(\widehat{0}),p\rangle=S\langle
R\circ{\mathsf{{H}}}(p),T\circ{\mathsf{{H}}}(p)\rangle=G\circ{\mathsf{{H}}}(p)$

for all $p\in{\mathrm{dom}}(F)$, hence $F=G\circ{\mathsf{{H}}}$ if $G$ is
restricted suitably (which is possible since
${\mathsf{{H}}}(p)\cap{\mathsf{{H}}}(q)=\emptyset$ for $p\not=q$.) ∎

We note that this result implies that ${\mathsf{{H}}}$ is not computable
(hence it is an interesting example of a natural problem that is continuous
and not computable). Another interesting consequence of our results is that
the functions that are computable relative to the halting problem form the
largest class of functions that, when composed with a limit computable
function from the right, yield a limit computable function.

######  Corollary  (Computability relative to the halting problem).

A function $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
is computable relative to the halting problem if and only if $F\circ G$ is
limit computable for every limit computable
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$.

The “if” direction follows from Theorems 3 and 2, when one chooses $G=\lim$.
The “only if” direction is a consequence of Theorems 3 and 2. A comparison of
Corollaries 3 and 2 shows that the notions of a low function is dual to the
notion of a function that is computable relative to the halting problem. Both
classes should be naturally studied alongside the limit computable functions.

As another non-uniform side result of the limit inversion theorem (Theorem 3)
we obtain a classical result from computability theory, the Friedberg jump
inversion theorem [21].

######  Corollary  (Friedberg jump inversion theorem 1957).

For every $q\in{\mathbb{N}}^{\mathbb{N}}$ with
$0^{\prime}\mathop{\leq_{\mathrm{T}}}q$ there exists a
$p\in{\mathbb{N}}^{\mathbb{N}}$ with
$p^{\prime}\mathop{\equiv_{\mathrm{T}}}q$.

###### Proof.

Given a fixed $q\in{\mathbb{N}}^{\mathbb{N}}$ with
$0^{\prime}\mathop{\leq_{\mathrm{T}}}q$ we can compute $p:=I(q)$ and
$p^{\prime}={\mathsf{{J}}}\circ I(q)$ with $I$ from the proof of Theorem 3. In
particular, $p^{\prime}\mathop{\leq_{\mathrm{T}}}q$. On the other hand, by the
same theorem and Theorem 2 we obtain
$q=\lim(p)\mathop{\leq_{\mathrm{T}}}p^{\prime}$. ∎

As another corollary we obtain the announced extension of Corollary 2.

######  Corollary .

For every function
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ that is
computable relative to the halting problem there exists a computable function
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$\lim\circ\,G=F\circ\lim$.

${\mathbb{N}}^{\mathbb{N}}$${\mathbb{N}}^{\mathbb{N}}$${\mathbb{N}}^{\mathbb{N}}$${\mathbb{N}}^{\mathbb{N}}$$G$$F$$\lim$$\lim$
Figure 1. Limit diagram.

This result can be interpreted as a statement about the diagram in Figure 1.
Vice versa, if $G$ is an arbitrary computable function that transfers
converging sequences into converging sequences (not necessarily in an
extensional way), then we can mimic the behavior of $G$ on the limits by a
function that is computable relative to the halting problem. This follows from
Theorems 3 and 2 and was proved directly with a somewhat more involved proof
that does not exploit the Galois connection between Turing jumps and limits in
[11, Theorem 14.11].

######  Corollary  (B., Hendtlass and Kreuzer 2017).

For all computable
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ the multi-
valued function $\lim\circ G\circ\lim^{-1}$ is computable relative to the
halting problem.

We close this section with a uniform version of Corollary 3. For the
formulation we need a total representations $\Phi$ of all continuous functions
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with
computable $G_{\delta}$–domain that satisfies a utm- and smn-theorem [52,
Theorem 2.3.5]. The result is tailor-made to yield a proof of Theorem 4 (3).

######  Theorem  (Uniform limit control theorem).

There exists a computable
$R:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$\Phi_{\lim\circ R(q)}(p)\in\lim\circ\Phi_{q}\circ\lim^{-1}(p)$ for all
$p,q\in{\mathbb{N}}^{\mathbb{N}}$ with
$p\in{\mathrm{dom}}(\lim\circ\Phi_{q}\circ\lim^{-1})$.

###### Proof.

By a relativized version of Theorem 3 there exist computable
$I,S:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$\lim\circ I_{q^{\prime}}={\mathrm{id}}$ and
$S_{q^{\prime}}={\mathsf{{J}}}_{q}\circ I_{q^{\prime}}$ for every
$q\in{\mathbb{N}}^{\mathbb{N}}$. This can be proved exactly as in the proof of
Theorem 3 except that we check whether the $i$–th Turing machine halts upon
input of

$\langle q,\langle
r_{0},...,r_{i},p|_{i+1}q_{t_{i}+1},p|_{i+1}q_{t_{i}+2},p|_{i+1}q_{t_{i}+3},...\rangle\rangle,$

which can be decided using $q^{\prime}$. Now, by applying the jump normal form
theorem (Theorem 2) to $\Phi$ we obtain a computable function $H$ with
$\lim\circ\Phi_{q}=H\circ{\mathsf{{J}}}_{q}$. Then $H\circ S$ is computable,
and by the smn-theorem for $\Phi$ there exists a total computable function $P$
such that $\Phi_{P(r)}(p)=H\circ S\langle r,p\rangle$ for all
$r,p\in{\mathbb{N}}^{\mathbb{N}}$. Finally, by the limit normal form theorem
(Theorem 2) there exists a computable function $R$ such that $\lim\circ
R=P\circ{\mathsf{{J}}}$. Such an $R$ is necessarily total. Altogether, we
obtain

$\Phi_{\lim R(q)}(p)=\Phi_{P{\mathsf{{J}}}(q)}(p)=HS\langle
q^{\prime},p\rangle=H{\mathsf{{J}}}_{q}I_{q^{\prime}}(p)=\lim\Phi_{q}I_{q^{\prime}}(p)\in\lim\circ\Phi_{q}(\lim\nolimits^{-1}(p))$

for all $p,q\in{\mathbb{N}}^{\mathbb{N}}$ with
$\lim^{-1}(p)\subseteq{\mathrm{dom}}(\lim\circ\Phi_{q})$. ∎

We note that the basic problems $\lim,{\mathsf{{J}}}^{-1}$ are generators of a
monoid which can be used to characterize all sorts of other computability
theoretic properties. For instance
${\mathsf{{J}}}^{-1}{\mathsf{{J}}}^{-1}\lim\lim$ characterizes the property of
being _low 2_ and ${\mathsf{{J}}}^{-1}\lim\lim$ the property of being _low
relative to the halting problem_ (see also [9]).

##  4\. Limit computability on represented spaces

The purpose of this section is to transfer our results on limit computable
maps to represented spaces. We recall that a _representation_ of a set $X$ is
a surjective function $\delta:\subseteq{\mathbb{N}}^{\mathbb{N}}\to X$. In
this situation we say that $(X,\delta)$ is a _represented space_. Any point
$p\in{\mathbb{N}}^{\mathbb{N}}$ with $\delta(p)=x$ is called a _name_ of $x$,
and the word “representation” is reserved for the map $\delta$ as such. A
_problem_ is a multi-valued partial function $f:\subseteq X\rightrightarrows
Y$ on represented spaces $X$ and $Y$. If $(X,\delta_{X})$ and $(Y,\delta_{Y})$
are represented spaces and $f:\subseteq X\rightrightarrows Y$ is a problem,
then $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$
_realizes_ $f$, in symbols $F\vdash f$, if $\delta_{Y}F(p)\in f\delta_{X}(p)$
holds for all $p\in{\mathrm{dom}}(f\delta_{X})$.

######  Definition  (Computable functions).

A problem $f$ is called _continuous_ , _computable_ , _limit computable_ ,
_low_ or _computable with respect to the halting problem_ , if it has a
realizer with the corresponding property.

Likewise, other properties can be transferred from realizers to problems. By
${\mathcal{C}}(X,Y)$ we denote the _set of total continuous functions_ $f:X\to
Y$. It is clear that all properties related to closure under composition that
have been discussed in the previous section can be transferred to problems.
This is because $F\vdash f$ and $G\vdash g$ implies $F\circ G\vdash f\circ g$.
We can also transfer properties of points to represented spaces using
representations.

######  Definition  (Computable points).

A point $x\in X$ in a represented space $X$ is called _computable_ , _limit
computable_ or _low_ if it has a name with the corresponding property.

We note that the notion of $1$–genericity is an example of a property that
should not be defined via names since it is not invariant under equivalent
representations (see Proposition 5 and the discussion afterwards).

Our main goal here is to transfer the limit normal form theorem and the jump
normal form theorem (Theorems 2 and 2) to problems on represented spaces.
Since we can incorporate limits and jumps into the represented spaces, these
normal forms can be expressed very neatly. For this purpose we need the
following concepts of jumps on represented spaces.

######  Definition  (Jumps).

Let $(X,\delta_{X})$ be a represented space and $\delta:=\delta_{X}$, let
$T:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ be
surjective, and let
$S:\subseteq{\mathbb{N}}^{\mathbb{N}}\rightrightarrows{\mathbb{N}}^{\mathbb{N}}$
be such that
$S^{-1}:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ is
single-valued and surjective. We define the following representations of $X$:

  1. (1)

$\delta^{T}:=\delta_{X^{T}}:=\delta_{X}\circ T$ (_$T$ –jump_)

  2. (2)

$\delta_{S}:=\delta_{X_{S}}:=\delta_{X}\circ S^{-1}$ (_$S^{-1}$ –jump_)

We denote the represented spaces $(X,\delta_{X^{T}})$ and $(X,\delta_{X_{S}})$
for short by $X^{T}$ and $X_{S}$, respectively. In the special case of
$T=\lim$ and $T=\lim_{\Delta}$, we define

  1. (3)

$\delta^{\prime}:=\delta_{X^{\prime}}:=\delta_{X}\circ\lim$ (jump)

  2. (4)

$\delta^{\Delta}:=\delta_{X^{\Delta}}:=\delta_{X}\circ\lim_{\Delta}$ (discrete
jump)

We denote the represented spaces $(X,\delta_{X^{\prime}})$ and
$(X,\delta_{X^{\Delta}})$ also by $X^{\prime}$ and $X^{\Delta}$, respectively.

We will apply this concept of a jump in the case of $T=\lim$,
$T={\mathsf{{L}}}$, $S={\mathsf{{H}}}$ and $S={\mathsf{{J}}}$. The special
jumps for $T=\lim$ and $T=\lim_{\Delta}$ (the limit on Baire space with
respect to the discrete metric) were originally defined by Ziegler [56] and
later also studied by the author, de Brecht and Pauly [7]. More general
concepts of jumps were also studied in the context of effective descriptive
set theory by de Brecht [15] and de Brecht and Pauly [38, 39, 40].

A common feature of the maps
$\lim,\lim_{\Delta},{\mathsf{{J}}}^{-1},{\mathsf{{L}}}$ and
${\mathsf{{H}}}^{-1}$ is that they are surjective and transparent. It was
noted by de Brecht [15] that the functor $X\mapsto X^{T}$ for surjective and
transparent $T$ can be seen as an endofunctor on the class of represented
spaces (that leaves the maps unchanged). This is made precise by the following
result.

######  Proposition  (The jump as endofunctor).

If $f:\subseteq X\rightrightarrows Y$ is a computable problem and
$T:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ is
transparent and surjective then it follows that $f$ considered as a problem of
type $f:\subseteq X^{T}\rightrightarrows Y^{T}$ is computable too.

###### Proof.

If $f:\subseteq X\rightrightarrows Y$ is computable, then it has a computable
realizer $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$.
Since $T$ is transparent, there is a computable
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with
$F\circ T=T\circ G$. Hence $G$ is a computable realizer of $f:\subseteq
X^{T}\rightrightarrows Y^{T}$. ∎

Through some results presented in this section we will get a better
understanding of the types of problems mentioned in Proposition 4 for the
specific maps $T$ that we are interested in.

We start with a result that characterizes limit computable problems and shows
that the jump $Y^{\prime}$ on the output side can be balanced by
$X_{\mathsf{{J}}}$ on the input side.

######  Theorem  (Limit computability).

Let $f:\subseteq X\rightrightarrows Y$ be a problem. Then the following are
equivalent:

  1. (1)

$f:\subseteq X\rightrightarrows Y$ is limit computable,

  2. (2)

$f:\subseteq X\rightrightarrows Y^{\prime}$ is computable,

  3. (3)

$f:\subseteq X_{\mathsf{{J}}}\rightrightarrows Y$ is computable.

###### Proof.

The equivalences are consequences of the limit normal form theorem (Theorem 2)
and the jump normal form theorem (Theorem 2). ∎

We note that this result can be interpreted such that jumps $X^{\prime}$ and
$X_{\mathsf{{J}}}$ are adjoint to each other. However, this is a pure
computability theoretic adjointness that does not relativize to a topological
adjointness. The proof of the direction (3)$\Longrightarrow$(2) can be
extended to a uniform proof, but this is not so for the direction
(2)$\Longrightarrow$(3). In fact,
${\mathcal{C}}(({\mathbb{N}}^{\mathbb{N}})_{\mathsf{{J}}},{\mathbb{N}}^{\mathbb{N}})\subsetneqq{\mathcal{C}}({\mathbb{N}}^{\mathbb{N}},{({\mathbb{N}}^{\mathbb{N}})}^{\prime})$,
since ${\mathsf{{J}}}^{-1}$ is not topologically transparent. However, we can
derive the following relativized version of Theorem 4 from Theorem 2.

######  Corollary  (Relativized limit computability).

Let $f:\subseteq X\rightrightarrows Y$ be a problem and
$q\in{\mathbb{N}}^{\mathbb{N}}$. Then the following are equivalent:

  1. (1)

$f:\subseteq X\rightrightarrows Y$ is limit computable relative to $q$,

  2. (2)

$f:\subseteq X\rightrightarrows Y^{\prime}$ is computable relative to $q$,

  3. (3)

$f:\subseteq X_{{\mathsf{{J}}}_{q}}\rightrightarrows Y$ is computable.

We can transfer our characterization of low problems.

######  Theorem  (Low computability).

Let $f:\subseteq X\rightrightarrows Y$ be a problem. Then the following are
equivalent:

  1. (1)

$f:\subseteq X\rightrightarrows Y$ is low,

  2. (2)

$f:\subseteq X\rightrightarrows Y^{\mathsf{{L}}}$ is computable,

  3. (3)

$f:\subseteq X^{\mathsf{{L}}}\rightrightarrows Y^{\mathsf{{L}}}$ is
computable,

  4. (4)

$f:\subseteq X_{\mathsf{{J}}}\rightrightarrows Y_{\mathsf{{J}}}$ is
computable,

  5. (5)

$f:\subseteq X_{\mathsf{{J}}}\rightrightarrows Y_{\mathsf{{J}}}$ is computable
relative to the halting problem $0^{\prime}$.

###### Proof.

The equivalence of (1) and (2) is a direct consequence of the definition of
low maps on Baire space. Since low maps are closed under composition by
Proposition 2, it follows that (2) implies (3). Since ${\mathrm{id}}:X\to
X^{\mathsf{{L}}}$ is computable, it follows that (3) implies (2). By Theorem 4
(2) and (4) are equivalent since
$X^{\mathsf{{L}}}=(X_{\mathsf{{J}}})^{\prime}$. By the statement
“(1)$\iff$(4)” of Theorem 4 (which independently follows from Corollaries 3
and 3) we obtain that (3) and (5) are equivalent. ∎

Finally, we obtain a dual characterization of the problems that are computable
relative to the halting problem.444We note that the equivalence of (1) and (4)
shows that [55, Theorem 23 (c)] is not correct.

######  Theorem  (Computability relative to the halting problem).

Let $f:\subseteq X\rightrightarrows Y$ be a problem. Then the following are
equivalent:

  1. (1)

$f:\subseteq X\rightrightarrows Y$ is computable relative to the halting
problem $0^{\prime}$,

  2. (2)

$f:\subseteq X_{\mathsf{{H}}}\rightrightarrows Y$ is computable,

  3. (3)

$f:\subseteq X_{\mathsf{{H}}}\rightrightarrows Y_{\mathsf{{H}}}$ is
computable,

  4. (4)

$f:\subseteq X^{\prime}\rightrightarrows Y^{\prime}$ is computable,

  5. (5)

$f:\subseteq X^{\prime}\rightrightarrows Y^{\prime}$ is low.

###### Proof.

The equivalence of (1) and (2) is a consequence of Theorem 3. Since functions
computable relative to $0^{\prime}$ are closed under composition, it follows
again by Theorem 3 that (2) implies (3). Since
${\mathrm{id}}:Y_{\mathsf{{H}}}\to Y$ is computable, it is clear that (3)
implies (2). The equivalence of (2) and (4) follows from Theorem 4 since
$X_{\mathsf{{H}}}=(X^{\prime})_{{\mathsf{{J}}}}$. The equivalence of (3) and
(5) follows from Theorem 4. ∎

The equivalence of (1) and (4) can also be directly derived from Corollaries 3
and 3. Likewise we obtain the following relativized version.

######  Theorem  (Computability relative to an oracle).

Let $f:\subseteq X\rightrightarrows Y$ be a problem and
$q\in{\mathbb{N}}^{\mathbb{N}}$. Then the following are equivalent:

  1. (1)

$f:\subseteq X\rightrightarrows Y$ is computable relative to $q^{\prime}$,

  2. (2)

$f:\subseteq X^{\prime}\rightrightarrows Y^{\prime}$ is computable relative to
$q$.

###### Proof.

The implication from (2) to (1) is a consequence of Theorem 3. For the
implication from (1) to (2) we need a relativized version of Corollary 3 that
can actually be derived from this corollary. Let ${\mathsf{{U}}}\langle
q,p\rangle:=\Phi_{q}(p)$ be the universal computable function. Then by
Corollary 3 there exists a computable $G$ such that $\lim\circ
G={\mathsf{{U}}}\circ\lim$. There is also a computable
$R:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with $\lim\circ
R\langle q,p\rangle=\langle\lim q,\lim p\rangle$. If we denote by $R_{q}$ the
function with $R_{q}(p):=R\langle q,p\rangle$ then we obtain $\lim\circ G\circ
R_{q}=\Phi_{\lim q}\circ\lim$. Hence, $G\circ R_{q}$ is a realizer for
$f:\subseteq X^{\prime}\rightrightarrows Y^{\prime}$ if $\Phi_{\lim q}$ is a
realizer for $f:\subseteq X\rightrightarrows Y$. This proves the claim. ∎

We immediately obtain the following corollary, where $q^{(n)}$ denotes the
$n$–th Turing jump of $q\in{\mathbb{N}}^{\mathbb{N}}$ and $X^{(n)}$ denotes
the $n$–th jump of the represented space $X$.

######  Corollary  (Computability relative to higher jumps).

Let $f:\subseteq X\rightrightarrows Y$ be a problem and $n\in{\mathbb{N}}$.
Then the following are equivalent:

  1. (1)

$f:\subseteq X\rightrightarrows Y$ is computable relative to $0^{(n)}$,

  2. (2)

$f:\subseteq X^{(n)}\rightrightarrows Y^{(n)}$ is computable.

Other characterizations can be derived as conclusions of the results provided
in this section. Now we want to show that jumps interact nicely with products
and function space constructions. We recall that for two represented spaces
$(X,\delta_{X})$ and $(Y,\delta_{Y})$ we can define a representation of
$X\times Y$, of $X^{\mathbb{N}}$ and of ${\mathcal{C}}(X,Y)$ as follows:

  1. (1)

$\delta_{X\times Y}:\subseteq{\mathbb{N}}^{\mathbb{N}}\to X\times Y,\langle
p,q\rangle\mapsto(\delta_{X}(p),\delta_{Y}(q))$.

  2. (2)

$\delta_{X^{\mathbb{N}}}:\subseteq{\mathbb{N}}^{\mathbb{N}}\to
X^{\mathbb{N}},\langle
p_{0},p_{1},p_{2},...\rangle\mapsto(\delta_{X}(p_{n}))_{n\in{\mathbb{N}}}$.

  3. (3)

$\delta_{{\mathcal{C}}(X,Y)}:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathcal{C}}(X,Y)$
by $\delta_{{\mathcal{C}}(X,Y)}(p)=f:\iff\Phi_{p}\vdash f$.

It is known that these representations make evaluation and currying computable
[52, Lemmas 3.3.14, 3.3.16 and Theorem 3.3.15] and that sequences can be
identified with continuous functions.

######  Fact  (Function space).

The following are computable for all represented spaces $X,Y$:

  1. (1)

${\mathrm{ev}}:{\mathcal{C}}(X,Y)\times X\to Y,(f,x)\mapsto f(x)$,

  2. (2)

$\mathrm{cur}:{\mathcal{C}}(X\times
Y,Z)\to{\mathcal{C}}(X,{\mathcal{C}}(Y,Z)),f\mapsto(x\mapsto(y\mapsto
f(x,y)))$,

  3. (3)

${\mathrm{id}}:{\mathcal{C}}({\mathbb{N}},X)\to X^{\mathbb{N}}$ and its
inverse.

We obtain the following result that shows how jumps interact with products and
function space constructions. We call a problem $f:X\to Y$ a _computable
isomorphism_ if $f$ is computable and bijective and its inverse $f^{-1}$ is
computable too.

######  Theorem  (Jumps with products and exponentials).

Let $X$ and $Y$ be represented spaces. Then the following are computable
isomorphisms:

  1. (1)

${\mathrm{id}}:(X\times Y)^{\prime}\to X^{\prime}\times Y^{\prime}$,

  2. (2)

${\mathrm{id}}:(X^{\mathbb{N}})^{\prime}\to(X^{\prime})^{\mathbb{N}}$,

  3. (3)

${\mathrm{id}}:{\mathcal{C}}(X,Y)^{\prime}\to{\mathcal{C}}(X^{\prime},Y^{\prime})$.

In particular, ${\mathcal{C}}(X^{\prime},Y^{\prime})$ is exactly the set of
continuous functions $f:X\to Y$.

###### Proof.

The first two statements follow from the fact that the tupling functions are
continuous:

$\lim_{i\to\infty}\langle
p_{i},q_{i}\rangle=\langle\lim_{i\to\infty}p_{i},\lim_{i\to\infty}q_{i}\rangle\mbox{
and }\lim_{i\to\infty}\langle
p_{0i},p_{1i},...\rangle=\langle\lim_{i\to\infty}p_{0i},\lim_{i\to\infty}p_{1i},...\rangle.$

Now we consider the evaluation map ${\mathrm{ev}}:{\mathcal{C}}(X,Y)\times
X\to Y$, which is computable. By Proposition 4 it follows that also
${\mathrm{ev}}:({\mathcal{C}}(X,Y)\times X)^{\prime}\to Y^{\prime}$ is
computable, and hence by (1) we obtain that
${\mathrm{ev}}:{\mathcal{C}}(X,Y)^{\prime}\times X^{\prime}\to Y^{\prime}$ is
computable. Since currying is computable, it follows that
${\mathrm{id}}:{\mathcal{C}}(X,Y)^{\prime}\to{\mathcal{C}}(X^{\prime},Y^{\prime})$
is computable. We still need to prove that
${\mathrm{id}}:{\mathcal{C}}(X^{\prime},Y^{\prime})\to{\mathcal{C}}(X,Y)^{\prime}$
is computable. But this follows from the uniform version of the uniform limit
control theorem (Theorem 3). ∎

We should warn the reader that we have an ambiguity in the terminology that
one has to keep in mind and that is expressed in the following corollary.

######  Corollary  (Limit computable points in function spaces).

Let $X,Y$ be represented spaces and $f\in{\mathcal{C}}(X,Y)$. Then $f$ is
limit computable as a point in ${\mathcal{C}}(X,Y)$ if and only if $f:X\to Y$
is computable relative to the halting problem as a function.

However, one can also see this as fit in terminology since for points in Baire
space being limit computability is equivalent to being computable relative to
the halting problem by Shoenfield’s limit lemma (Corollary 2). Hence $f$ being
computable relative to the halting problem as a point in ${\mathcal{C}}(X,Y)$
is equivalent to $f:X\to Y$ being computable relative to the halting problem
as a function. The equivalence between computability relative to the halting
problem and limit computability for points extends to sequences. Theorem 4
together with the fact that ${\mathrm{id}}:{\mathcal{C}}({\mathbb{N}},X)\to
X^{\mathbb{N}}$ is a computable isomorphism imply the following.

######  Corollary  (Limit computable sequences).

The identity
${\mathrm{id}}:{\mathcal{C}}({\mathbb{N}},X)^{\prime}\to{\mathcal{C}}({\mathbb{N}},X^{\prime})$
is a computable isomorphism. In particular, the limit computable functions
$f:{\mathbb{N}}\to X$ are exactly the functions $f:{\mathbb{N}}\to X$ that are
computable relative to the halting problem.

The jump $X\mapsto X_{\mathsf{{J}}}$ does not preserve products and function
spaces in the way $X\mapsto X^{\prime}$ does according to Theorem 4.
Basically, all our negative results in this direction can be derived from
Spector’s jump inversion theorem (see [48] or [36, Proposition V.2.26]). In
particular, it implies that the notion of a low function is incomparable with
the notion of a function that is computable relative to a low oracle.555A
referee provided an interesting alternative proof of this result, using
Chaitin’s $\Omega=\langle\Omega_{0},\Omega_{1}\rangle$. The even and odd parts
$\Omega_{0}$ and $\Omega_{1}$, respectively, are low according to [16, Theorem
15.2.3] and hence $F:p\mapsto\langle\Omega_{0},p\rangle$ and
$f:i\mapsto\Omega_{i}$ are alternative concrete examples that satisfy
Proposition 4.

######  Proposition  (Low functions).

There is a Lipschitz continuous function
$F:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ that is computable
relative to a low oracle, but that is not low as a function. There is also a
low function $f:\\{0,1\\}\to{\mathbb{N}}^{\mathbb{N}}$ that is not computable
relative to a low oracle.

###### Proof.

By Spector’s jump inversion theorem there are low
$p,q\in{\mathbb{N}}^{\mathbb{N}}$ such that $\langle p,q\rangle$ is not low.
Hence the function
$F:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}},r\mapsto\langle
q,r\rangle$ does not map the low $p\in{\mathbb{N}}^{\mathbb{N}}$ to a low
value $F(p)=\langle q,p\rangle$. That is, $F$ is not low, but computable
relative to the low point $q$. It is easy to see that $F$ is Lipschitz
continuous with Lipschitz constant $1$.

There are also computable $r,s\in{\mathbb{N}}^{\mathbb{N}}$ such that
${\mathsf{{L}}}(r)=p$ and ${\mathsf{{L}}}(s)=q$. We consider the functions
$f,g:\\{0,1\\}\to{\mathbb{N}}^{\mathbb{N}}$ defined by

$f(i):=\left\\{\begin{array}[]{ll}p&\mbox{if $i=0$}\\\
q&\mbox{otherwise}\end{array}\right.\mbox{ and
}g(i):=\left\\{\begin{array}[]{ll}r&\mbox{if $i=0$}\\\
s&\mbox{otherwise}\end{array}\right..$

Then $g$ is computable and $f={\mathsf{{L}}}\circ g$. Hence $f$ is low. Let us
assume that $f$ is computable with respect to a low oracle
$t\in{\mathbb{N}}^{\mathbb{N}}$. Then $p=f(0)\mathop{\leq_{\mathrm{T}}}t$ and
$q=f(1)\mathop{\leq_{\mathrm{T}}}t$ follows and hence $\langle
p,q\rangle\mathop{\leq_{\mathrm{T}}}t$, which is a contradiction since
$\langle p,q\rangle$ is not low. ∎

We will see several further low functions that are not computable relative to
a low oracle in section 6.

As a preparation for the following results we show that relative computability
can also be characterized via function spaces if the corresponding oracle
class is closed downwards by Turing reducibility.

######  Lemma  (Relative computability).

Let $F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ be a
function and $q\in{\mathbb{N}}^{\mathbb{N}}$. Then the following are
equivalent:

  1. (1)

$F$ is computable relative to $q$,

  2. (2)

$(\exists r\mathop{\leq_{\mathrm{T}}}q)(\forall
p\in{\mathrm{dom}}(F))\;F(p)=\Phi_{r}(p)$.

###### Proof.

(1) implies (2) by the smn-theorem and (2) implies (1) by the utm-theorem. ∎

We can apply this in particular to the class of functions that are computable
with respect to a low oracle.

######  Corollary  (Computability relative to a low oracle).

Let $X,Y$ be represented spaces. Then ${\mathcal{C}}(X,Y)^{\mathsf{{L}}}$ is
the class of functions that are computable relative to a low oracle.

Now we get the following negative result on how ${\mathsf{{L}}}$ and
${\mathsf{{J}}}$ behave on function spaces. We note that the given identities
are not surjective, since the spaces
${\mathcal{C}}(X^{\mathsf{{L}}},Y^{\mathsf{{L}}})$ and
${\mathcal{C}}(X_{\mathsf{{J}}},Y_{\mathsf{{J}}})$ contain discontinuous
functions.

######  Proposition  (Function spaces for low functions).

For instance for $X=Y={\mathbb{N}}^{\mathbb{N}}$ the embeddings
${\mathrm{id}}:{\mathcal{C}}(X,Y)^{\mathsf{{L}}}\to{\mathcal{C}}(X^{\mathsf{{L}}},Y^{\mathsf{{L}}})$
and
${\mathrm{id}}:{\mathcal{C}}(X,Y)_{\mathsf{{J}}}\to{\mathcal{C}}(X_{\mathsf{{J}}},Y_{\mathsf{{J}}})$
are not computable. The partial inverses of these maps are also not
computable.

###### Proof.

The function $F$ from Proposition 4 is not a computable point in
${\mathcal{C}}(X^{\mathsf{{L}}},Y^{\mathsf{{L}}})$, but by Corollary 4 it is a
computable point in ${\mathcal{C}}(X,Y)^{\mathsf{{L}}}$. This means that the
embedding
${\mathrm{id}}:{\mathcal{C}}(X,Y)^{\mathsf{{L}}}\to{\mathcal{C}}(X^{\mathsf{{L}}},Y^{\mathsf{{L}}})$
is not computable. With Theorem 4 it follows that also the embedding
${\mathrm{id}}:{\mathcal{C}}(X,Y)_{\mathsf{{J}}}\to{\mathcal{C}}(X_{\mathsf{{J}}},Y_{\mathsf{{J}}})$
is not computable since $Z^{\mathsf{{L}}}=(Z_{\mathsf{{J}}})^{\prime}$. The
function $f$ from Proposition 4 can easily be converted into a function
$f:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ with corresponding
properties, and hence ${\mathcal{C}}(X^{\mathsf{{L}}},Y^{\mathsf{{L}}})$
contains computable points which are not computable in
${\mathcal{C}}(X,Y)^{\mathsf{{L}}}$. The space
${\mathcal{C}}(X,Y)_{\mathsf{{J}}}$ does not even contain any computable
points whatsoever. Altogether, this shows that the partial inverses of the
given maps are not computable. ∎

The positive properties that apply to Turing jumps and products are captured
in the following result.

######  Proposition  (Turing jumps and products).

Let $X$ and $Y$ be represented spaces. Then the following maps are computable:

  1. (1)

${\mathrm{id}}:(X\times Y)_{\mathsf{{J}}}\to X_{\mathsf{{J}}}\times
Y_{\mathsf{{J}}}$,

  2. (2)

${\mathrm{id}}:(X^{\mathbb{N}})_{\mathsf{{J}}}\to(X_{\mathsf{{J}}})^{\mathbb{N}}$.

In general, these maps are not computable isomorphisms.

###### Proof.

It is easy to see that $\langle{\mathsf{{J}}}\times{\mathsf{{J}}}\rangle$ is
limit computable since ${\mathsf{{J}}}$ is limit computable. Hence, by the
jump normal form theorem (Theorem 2) there exists a computable $F$ such that
$F{\mathsf{{J}}}\langle
p,q\rangle=\langle{\mathsf{{J}}}(p),{\mathsf{{J}}}(q)\rangle$. This function
$F$ is a realizer of ${\mathrm{id}}:(X\times Y)_{\mathsf{{J}}}\to
X_{\mathsf{{J}}}\times Y_{\mathsf{{J}}}$. Likewise, limit computability of
$\langle\widehat{{\mathsf{{J}}}}\rangle$ implies that
${\mathrm{id}}:(X^{\mathbb{N}})_{\mathsf{{J}}}\to(X_{\mathsf{{J}}})^{\mathbb{N}}$
is computable. Let us assume that the inverse of ${\mathrm{id}}:(X\times
Y)_{\mathsf{{J}}}\to X_{\mathsf{{J}}}\times Y_{\mathsf{{J}}}$ is computable.
Then by Proposition 4 and Fact 4 the evaluation
${\mathrm{ev}}:{\mathcal{C}}(X,Y)_{\mathsf{{J}}}\times X_{\mathsf{{J}}}\to
Y_{\mathsf{{J}}}$ would be computable, and hence
${\mathrm{id}}:{\mathcal{C}}(X,Y)_{\mathsf{{J}}}\to{\mathcal{C}}(X_{\mathsf{{J}}},Y_{\mathsf{{J}}})$
would be computable, which is not the case in general by Proposition 4, for
instance for $X=Y={\mathbb{N}}^{\mathbb{N}}$. If the inverse of
${\mathrm{id}}:(X\times Y)_{\mathsf{{J}}}\to X_{\mathsf{{J}}}\times
Y_{\mathsf{{J}}}$ for binary products of $X=Y={\mathbb{N}}^{\mathbb{N}}$ is
not computable, it follows that the inverse of
${\mathrm{id}}:(X^{\mathbb{N}})_{\mathsf{{J}}}\to(X_{\mathsf{{J}}})^{\mathbb{N}}$
for countable products of $X={\mathbb{N}}^{\mathbb{N}}$ is not computable
either. ∎

We mention that the jump $X\mapsto X_{\mathsf{{J}}}$ commutes with coproducts
while the jump $X\mapsto X^{\prime}$ does not. However, we do not needs these
facts here. Hence, we leave the details to the reader. Here we just formulate
a corollary for $X\mapsto X^{\mathsf{{L}}}$ that we obtain from Proposition 4
and Theorem 4.

######  Corollary  (Lowness and products).

Let $X$ and $Y$ be represented spaces. Then the following maps are computable:

  1. (1)

${\mathrm{id}}:(X\times Y)^{\mathsf{{L}}}\to X^{\mathsf{{L}}}\times
Y^{\mathsf{{L}}}$,

  2. (2)

${\mathrm{id}}:(X^{\mathbb{N}})^{\mathsf{{L}}}\to(X^{\mathsf{{L}}})^{\mathbb{N}}$.

In general, these maps are not computable isomorphisms.

That the maps are not computable isomorphisms follows again from Spector’s
jump inversion theorem. As a consequence of Corollary 4 and Fact 4 we obtain
at least one positive implication for sequences that are computable relative
to a low oracle. The inverse implication is not correct in general by
Proposition 4.

######  Corollary  (Low sequences).

The identity
${\mathrm{id}}:{\mathcal{C}}({\mathbb{N}},X)^{\mathsf{{L}}}\to{\mathcal{C}}({\mathbb{N}},X^{\mathsf{{L}}})$
is computable. In particular, every function $f:{\mathbb{N}}\to X$ that is
computable relative to a low oracle is also low as a function.

In the remainder of this section we briefly want to discuss some
interpretations of our results in the lattice of representations. We recall
that given two represented spaces $(X,\delta_{X})$ and $(Y,\delta_{Y})$ with
$X\subseteq Y$ we say that $\delta_{X}$ is _reducible_ to $\delta_{Y}$, in
symbols $\delta_{X}\leq\delta_{Y}$, if
${\mathrm{id}}:(X,\delta_{X})\to(Y,\delta_{Y})$ is computable. The
corresponding equivalence is denoted by $\equiv$.

As an immediate corollary of Proposition 4 we obtain the following.

######  Corollary  (Monotonicity of jumps).

Let $(X,\delta_{X})$ and $(Y,\delta_{Y})$ be represented spaces and let
$T:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ be
transparent and surjective. Then $\delta_{X}\leq\delta_{Y}$ implies
$\delta_{X}^{T}\leq\delta_{Y}^{T}$.

We now consider the jump operations that we have introduced on represented
spaces. Firstly, they are all ordered in the following way.

######  Corollary  (Order of jumps).

For every representation $\delta$ each of the following reductions holds:
$\delta_{\mathsf{{J}}}\leq\delta_{\mathsf{{H}}}\leq\delta\leq\delta^{\Delta}\leq\delta^{\mathsf{{L}}}\leq\delta^{\prime}$.

Here the first reduction holds since $\lim$ has a computable right inverse
$F:{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$, and hence
$F:({\mathbb{N}}^{\mathbb{N}})_{\mathsf{{J}}}\to({\mathbb{N}}^{\mathbb{N}})_{\mathsf{{J}}}$
is computable by Proposition 4; the second reduction holds since
${\mathsf{{H}}}^{-1}$ is computable; the third reduction holds since
$\lim_{\Delta}$ has a computable right inverse; the fourth reduction holds in
$\lim_{\Delta}$ is low by Corollary 2 and Theorem 2, and the last reduction
holds since ${\mathsf{{L}}}$ is limit computable by Proposition 2. In fact,
some of the discussed operations on represented spaces have further
properties. In particular the pair
$(\delta\mapsto\delta_{\mathsf{{J}}},\delta\mapsto\delta^{\prime})$ forms a
_Galois connection_ in the lattice of representations of a fixed set. This is
a consequence of Theorem 4 applied to the injection ${\mathrm{id}}:X\to Y$.

######  Corollary  (Galois connection between Turing jumps and limits).

Let $(X,\delta_{X})$ and $(Y,\delta_{Y})$ be represented spaces with
$X\subseteq Y$. Then
$\delta_{X_{\mathsf{{J}}}}\leq\delta_{Y}\iff\delta_{X}\leq\delta_{Y^{\prime}}$.

The operation
$\delta\mapsto\delta^{\mathsf{{L}}}=(\delta_{\mathsf{{J}}})^{\prime}$ is the
_monad_ of this Galois connection, which implies that it is a closure
operator. Likewise,
$\delta\mapsto\delta_{\mathsf{{H}}}=(\delta^{\prime})_{\mathsf{{J}}}$ is an
interior operator [17, Proposition 3(4)].

######  Proposition  (Closure and interior operators).

$\delta\mapsto\delta^{\mathsf{{L}}}$ and $\delta\mapsto\delta^{\Delta}$ are
closure operators and $\delta\mapsto\delta_{\mathsf{{H}}}$ is an interior
operator on the lattice of representations of a fixed set $X$.

The fact that $\delta\mapsto\delta^{\Delta}$ is also a closure operator can
easily be proved directly. Another consequence of Corollary 4 which can also
easily be proved directly, is that $\delta\mapsto\delta_{\mathsf{{J}}}$
preserves suprema and $\delta\mapsto\delta^{\prime}$ preserves infima [17,
Proposition 3(8)]. We recall for represented spaces $(X,\delta_{X})$ and
$(Y,\delta_{Y})$ the _meet_ or _infimum_ $\delta_{X}\wedge\delta_{Y}$, which
is a representation of $X\cap Y$, can be defined by
$(\delta_{X}\wedge\delta_{Y})\langle
p,q\rangle=z:\iff\delta_{X}(p)=\delta_{Y}(q)=z$. If $X=Y$, then
$\delta_{X}\wedge\delta_{Y}$ is actually known to the the infimum in the
lattice of representations of $X$ [52, Lemma 3.3.8]. Hence we obtain the
following.

######  Proposition  (Infimum and jumps).

Let $(X,\delta_{X})$ and $(Y,\delta_{Y})$ be represented spaces. Then
$(\delta_{X}\wedge\delta_{Y})^{\prime}\equiv\delta_{X}^{\prime}\wedge\delta_{Y}^{\prime}$.

Analogously, $\delta\mapsto\delta^{\prime}$ commutes with products (see
Theorem 4), which also implies Proposition 4 since
$\delta_{X}\wedge\delta_{Y}=\Delta_{X\cap Y}^{-1}\circ\delta_{X\times Y}$,
where $\Delta_{X\cap Y}$ denotes the _diagonal_ $\Delta_{X\cap Y}:X\cap
Y\to(X\cap Y)\times(X\cap Y),x\mapsto(x,x)$. Likewise,
$\delta\mapsto\delta_{\mathsf{{J}}}$ commutes with coproducts and suprema, but
we do not formulate these results here.

##  5\. Limit computability on metric spaces

In this section we want to transfer some of our results to computable metric
spaces. We recall that $(X,d,\alpha)$ is called a _computable metric space_ ,
if $(X,d)$ is a metric space with metric $d:X\times X\to{\mathbb{R}}$ and
$\alpha:{\mathbb{N}}\to X$ is a sequence that is dense in $X$ such that
$d\circ(\alpha\times\alpha):{\mathbb{N}}^{2}\to{\mathbb{R}}$ is a computable
sequence of real numbers. Each computable metric space is equipped with its
_Cauchy representation_ $\delta_{X}:\subseteq{\mathbb{N}}^{\mathbb{N}}\to X$
that is defined by $\delta_{X}(p):=\lim_{n\to\infty}\alpha p(n)$ with
${\mathrm{dom}}(\delta_{X}):=\\{p\in{\mathbb{N}}^{\mathbb{N}}:(\forall
k)(\forall n\geq k)\;d(\alpha p(n),\alpha p(k))<2^{-k}$ and $(\alpha
p(n))_{n\in{\mathbb{N}}}$ converges$\\}$. The real numbers ${\mathbb{R}}$ are
also equipped with a Cauchy representation that is induced by a standard
numbering $\alpha$ of all rational numbers. Besides the usual Cauchy
representation there is also the so-called _naive Cauchy representation_
$\delta_{X}^{\mathrm{n}}$ that is defined exactly as $\delta_{X}$ but with
${\mathrm{dom}}(\delta_{X}^{\mathrm{n}}):=\\{p\in{\mathbb{N}}^{\mathbb{N}}:(\alpha
p(n))_{n\in{\mathbb{N}}}$ converges$\\}$.

Given a computable metric space $(X,d,\alpha)$ we define the _open ball_
$B_{\langle c,r\rangle}:=B(\alpha(c),\overline{r}):=\\{x\in
X:d(x,\alpha(c))<\overline{r}\\}$ for every $c,r\in{\mathbb{N}}$, where
$\overline{\langle i,j,k\rangle}:=\frac{i-j}{k+1}$ denotes the rational number
encoded by $i,j,k\in{\mathbb{N}}$. By $W_{i}:=\\{n\in{\mathbb{N}}:$ Turing
machine $i$ halts on input $n\\}$ we denote the usual numbering of c.e.
subsets of ${\mathbb{N}}$, and by $U_{i}:=\bigcup_{n\in W_{i}}B_{n}$ we denote
a numbering of all _c.e. open_ subsets of $X$. We can consider the set
${\mathcal{O}}(X)$ of open subsets as a represented space with representation
$\delta_{{\mathcal{O}}(X)}(p)=\bigcup_{i\in{\mathbb{N}}}B_{p(i)}$. The c.e.
open subsets are exactly the computable points in ${\mathcal{O}}(X)$ with this
representation.

We can now generalize the limit map and the Turing jump as defined in Example
2 to arbitrary computable metric spaces.

######  Definition  (Limit and Turing jump).

Let $X$ be a computable metric space. We define:

  1. (1)

The _limit map_ of $X$ by $\lim\nolimits_{X}:\subseteq X^{\mathbb{N}}\to
X,(x_{n})_{n\in{\mathbb{N}}}\mapsto\lim_{n\to\infty}x_{n}$.

  2. (2)

The _Turing jump_ ${\mathsf{{J}}}_{X}:X\to{\mathbb{N}}^{\mathbb{N}}$ of $X$ by

${\mathsf{{J}}}_{X}(x)(i):=\left\\{\begin{array}[]{ll}1&\mbox{if $x\in
U_{i}$}\\\ 0&\mbox{otherwise}\end{array}\right.$

for all $x\in X$ and $i\in{\mathbb{N}}$.

It is easy to see that both functions defined here are always limit
computable.

######  Proposition .

$\lim_{X}$ and ${\mathsf{{J}}}_{X}$ are limit computable for every computable
metric space $X$.

###### Proof.

Let $\delta_{X}$ be the Cauchy representation of the computable metric space
$(X,d,\alpha)$. Given a $p=\langle
p_{0},p_{1},p_{2},...\rangle\in{\mathbb{N}}^{\mathbb{N}}$ with a sequence
$(p_{n})_{n\in{\mathbb{N}}}$ of names of points $x_{n}:=\delta_{X}(p_{n})$
such that $x:=\lim_{n\to\infty}x_{n}$ exists, we need to devise a limit
computation that yields a $q\in{\mathrm{dom}}(\delta_{X})$ with
$\delta_{X}(q)=x$. For every $i,k\in{\mathbb{N}}$ the property

$(\exists n>i)\;d(\delta_{X}(p_{n}),\delta_{X}(p_{i}))>2^{-k-2}$

is c.e. in $p$ and $k,i$. Hence, with the help of ${\mathsf{{J}}}(p)$ we can
decide this property, and hence for each $k\in{\mathbb{N}}$ we can
systematically search for a $i=i_{k}\in{\mathbb{N}}$ such that it fails. Such
an $i_{k}$ must exists since $x_{n}$ converges to $x$. We can assume that the
sequence $(i_{k})_{k\in{\mathbb{N}}}$ is strictly monotone increasing. For
each $k\in{\mathbb{N}}$ we let $q(k):=p_{i_{k}}(k+2)$. Then for $n>k$

$\displaystyle d(\alpha q(n),\alpha q(k))$ $\displaystyle\leq$ $\displaystyle
d(\alpha
p_{i_{n}}(n+2),\delta_{X}(p_{i_{n}}))+d(\delta_{X}(p_{i_{n}}),\delta_{X}(p_{i_{k}}))+d(\delta_{X}(p_{i_{k}}),\alpha
p_{i_{k}}(k+2))$ $\displaystyle\leq$ $\displaystyle
2^{-n-2}+2^{-k-2}+2^{-k-2}<2^{-k}$

and $\delta_{X}(q)=\lim_{k\to\infty}\alpha
p_{i_{k}}(k+2)=\lim_{k\to\infty}x_{k}=x$. By Theorem 2 it follows that
$\lim_{X}$ is limit computable.

${\mathsf{{J}}}_{X}$ can easily be computed on a limit Turing machine. Given a
name of an input $x\in X$ one produces for each output position
${\mathsf{{J}}}_{X}(x)(i)$ the default value $0$ and simultaneously one tries
to verify $x\in U_{i}$. As soon as $x\in U_{i}$ can be confirmed, the $i$–th
output value has to be changed to $1$, which happens at most once for each
position $i$. ∎

This allows us to transfer the limit normal form theorem (Theorem 2) to
computable metric spaces. For $f,s:\subseteq X\rightrightarrows Y$ we write
$s\sqsubseteq f$ if $s(x)\subseteq f(x)$ for all $x\in{\mathrm{dom}}(f)$ and
${\mathrm{dom}}(f)\subseteq{\mathrm{dom}}(s)$. In this situation we call $s$ a
_solution_ or _selector_ of $f$.

######  Theorem  (Limit normal form).

Let $X$ be a represented space, $Y$ a computable metric space and $f:\subseteq
X\rightrightarrows Y$ a problem. Then the following are equivalent:

  1. (1)

$f:\subseteq X\rightrightarrows Y$ is limit computable,

  2. (2)

$\lim_{Y}\circ g\sqsubseteq f$ for some computable $g:\subseteq
X\rightrightarrows Y^{\mathbb{N}}$.

###### Proof.

That (2) implies (1) follows since $\lim_{Y}$ is limit computable by
Proposition 5. We need to prove that (1) implies (2). Let $f:\subseteq
X\rightrightarrows Y$ be limit computable. We use the Cauchy representation
$\delta_{Y}$ of $Y$. Then $f$ has a limit computable realizer
$F:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$. By the
limit normal form theorem (Theorem 2) there exists a computable
$G:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ such that
$F=\lim\circ G$. Now we define a function
$H:\subseteq{\mathbb{N}}^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ by
$H(p)=\langle r_{0},r_{1},r_{2},...\rangle$, provided that $G(p)=\langle
q_{0},q_{1},q_{2},...\rangle$, where each $r_{i}$ is determined as follows. We
choose $r_{1}:=r_{0}:=(q_{0}(0),q_{0}(0),...)$ and if $i>1$ then for each
$k\in\\{2,...,i\\}$ we check, which of the following two conditions is
recognized first:

  1. (1)

$(\forall j\in\\{1,...,k-1\\})\;d(\alpha q_{i}(k),\alpha q_{i}(j))<2^{-j+1}$,

  2. (2)

$(\exists j\in\\{1,...,k-1\\})\;d(\alpha q_{i}(k),\alpha q_{i}(j))>2^{-j}$.

Depending on which condition is recognized first, we choose

  1. (1)

$r_{i}:=(q_{i}(1),q_{i}(2),...,q_{i}(i),q_{i}(i),....)$, if for all $k\leq i$
the first condition is recognized first,

  2. (2)

$r_{i}:=(q_{i}(1),q_{i}(2),...,q_{i}(k-1),q_{i}(k-1),...)$, if $k\leq i$ is
minimal such that the second condition is recognized first.

We note that $r_{i}\in{\mathrm{dom}}(\delta_{Y})$ for all $i$ and if $q_{i}$
has a prefix of length $k\leq i$ that is a valid prefix of a name in
$q\in{\mathrm{dom}}(\delta_{Y})$, then $d(\delta_{Y}(r_{i}),\delta_{Y}(q))\leq
2^{-k+1}$. Altogether, $H$ is computable, and the definition ensures that
${\mathrm{range}}(H)\subseteq{\mathrm{dom}}(\delta_{Y}^{\mathbb{N}})$ and
$\lim_{Y}\circ\delta_{Y}^{\mathbb{N}}\circ H=\delta_{Y}\circ\lim\circ
G=\delta_{Y}\circ F$. This proves that $H$ is a realizer of a computable
multi-valued function $g:\subseteq X\rightrightarrows Y^{\mathbb{N}}$ with
$\lim_{Y}\circ g\sqsubseteq f$. ∎

For completeness we formulate the result also for single-valued $f$. We note
that the problem $g$ still needs to be multi-valued in general.

######  Corollary  (Limit normal form).

Let $X$ be a represented space, $Y$ a computable metric space and $f:\subseteq
X\to Y$ a map. Then the following are equivalent:

  1. (1)

$f:\subseteq X\to Y$ is limit computable,

  2. (2)

$f=\lim_{Y}\circ g$ for some computable $g:\subseteq X\rightrightarrows
Y^{\mathbb{N}}$.

As a corollary we obtain the following conclusion on pointwise limits of
computable sequences of functions.

######  Corollary  (Pointwise limit).

Let $X$ be a represented space and $Y$ a computable metric space. Let
$(g_{n})_{n\in{\mathbb{N}}}$ be a computable sequence in ${\mathcal{C}}(X,Y)$,
i.e., a computable sequence of computable functions $g_{n}:X\to Y$. Then
$f:X\to Y$, defined by $f(x):=\lim_{n\to\infty}g_{n}(x)$ for all $x\in X$, is
limit computable.

We note that in general one cannot expect that all limit computable $f$ can be
obtained as the pointwise limit of a computable sequence of single-valued $g$
(as in the case of Baire space, see Corollary 2). We obtain, however, a
characterization of limit computable points in computable metric spaces.

######  Corollary  (Limit computable points).

Let $X$ be a computable metric space. Then $x\in X$ is limit computable (in
the sense that it has a limit computable name) if and only if there is a
computable sequence $(x_{n})_{n\in{\mathbb{N}}}$ such that
$x=\lim_{n\to\infty}x_{n}$.

We recall that a computable metric space $(X,d)$ is called _computably
compact_ if $\\{X\\}$ is c.e. open in ${\mathcal{O}}(X)$. We note that for
computably compact metric spaces $(X,d)$ the function space
${\mathcal{C}}(X)={\mathcal{C}}(X,{\mathbb{R}})$ with the metric induced by
the _uniform norm_ $||f||:=\sup_{x\in X}|f(x)|$ is a computable metric space
again. As a dense subset one can use, for instance, the set of rational
polynomials in the _distance functions_ $d_{x}:X\to{\mathbb{R}},y\mapsto
d(x,y)$. This space ${\mathcal{C}}(X)$ is then computably isomorphic to the
space obtained by using the function space representation
$\delta_{{\mathcal{C}}(X,{\mathbb{R}})}$, see [3]. If we apply Corollaries 4
and 5 to the space ${\mathcal{C}}(X)$, then we obtain the following result.

######  Corollary  (Uniform limit).

Let $X$ be a computably compact computable metric space. Then
$f:X\to{\mathbb{R}}$ is computable relative to the halting problem if and only
if there is a computable sequence $(f_{n})_{n\in{\mathbb{N}}}$ of computable
functions $f_{n}:X\to{\mathbb{R}}$ that converges uniformly to $f$, i.e., such
that $\lim_{n\to\infty}||f-f_{n}||=0$.

A characterization similar to Corollary 5 was obtained for effectively
${{\mathbf{\Sigma}}^{0}_{2}}$–measurable functions in [6, Theorem 9.5] (we
refer the reader to [6] for the definition of measurability, as we are not
going to use these notions here any further). This yields the following
conclusion.

######  Corollary  (Borel measurability).

Let $X,Y$ be computable metric spaces. Then a function $f:X\to Y$ is limit
computable if and only if it is effectively
${{\mathbf{\Sigma}}^{0}_{2}}$–measurable.

Corollary 5 can also be applied to the naive Cauchy representation since
$\delta_{X}^{\mathrm{n}}=\lim_{X}\circ\widehat{\alpha}$, where
$\widehat{\alpha}:{\mathbb{N}}^{\mathbb{N}}\to X^{\mathbb{N}},p\mapsto(\alpha
p(0),\alpha p(1),\alpha p(2),...)$ is the parallelization of $\alpha$ that is
computable with respect to the Cauchy representation $\delta_{X}$. We obtain
the following result that generalizes corresponding results for the spaces
$X={\mathbb{R}}$ and $X={\mathcal{C}}([0,1]^{n})$ by Ziegler [56, Propositions
2.5 and 2.7].

######  Corollary  (Naive Cauchy representation as jump).

$\delta_{X}^{\mathrm{n}}\equiv\lim_{X}\circ\delta_{X}^{\mathbb{N}}\equiv\delta_{X}^{\prime}$
for every computable metric space $X$.

###### Proof.

With the help of Theorem 4 and Corollary 5 one obtains
$\delta_{X}^{\mathrm{n}}\leq\delta_{X}^{\prime}$. The reduction
$\delta_{X}^{\prime}\leq\lim_{X}\circ\delta_{X}^{\mathbb{N}}$ follows from the
same theorems applied to the identity ${\mathrm{id}}:X^{\prime}\to X$. The
remaining reduction
$\lim_{X}\circ\delta_{X}^{\mathbb{N}}\leq\lim_{X}\circ\widehat{\alpha}$ is
easy to prove directly, by choosing a diagonal sequence. ∎

Together with Theorem 4 we obtain a proof of the following result from [12,
Theorem 22].

######  Corollary  (B. and Hertling 2002).

Let $X,Y$ be computable metric spaces. The functions $f:\subseteq X\to Y$ that
are continuous with respect to the naive Cauchy representations on $X$ and $Y$
are the usual continuous functions.

Now we study the jump ${\mathsf{{J}}}_{X}$. We first prove that
${\mathsf{{J}}}_{X}^{-1}$ is computable in general.

######  Proposition  (Inverse jump).

${\mathsf{{J}}}_{X}^{-1}:\subseteq{\mathbb{N}}^{\mathbb{N}}\to X$ is
computable for every computable metric space $X$.

###### Proof.

We recall that a standard representation of $X$ can be defined by
$\delta(p)=x:\iff{\mathrm{range}}(p)=\\{n\in{\mathbb{N}}:x\in B_{n}\\}$. It is
easy to see that $\delta\leq\delta_{X}$, where $\delta_{X}$ denotes the Cauchy
representation of $X$ [52, Theorem 8.1.4]. Hence, it suffices to compute
${\mathsf{{J}}}_{X}^{-1}$ with respect to $\delta$. Since
${\mathsf{{J}}}_{X}(x)$ is the characteristic function of
$\\{n\in{\mathbb{N}}:x\in U_{n}\\}$, it is straightforward to generate a list
of all $n\in{\mathbb{N}}$ with $x\in B_{n}$, given ${\mathsf{{J}}}_{X}(x)$. ∎

Using this result we obtain the following form of the jump normal form
theorem. Surprisingly we need a variant of Schröder’s representation [43] of
computable metric spaces that has compact fibers, which can be computed with
respect to positive information. Such a representation was studied in [6].

######  Theorem  (Jump normal form).

Let $X,Y$ be computable metric spaces and $f:\subseteq X\rightrightarrows Y$ a
problem. Then the following are equivalent:

  1. (1)

$f:\subseteq X\rightrightarrows Y$ is limit computable,

  2. (2)

$g\circ{\mathsf{{J}}}_{X}\sqsubseteq f$ for some computable
$g:\subseteq{\mathbb{N}}^{\mathbb{N}}\to Y$.

###### Proof.

By Proposition 5 it is clear that $g\circ{\mathsf{{J}}}_{X}$ is limit
computable for every computable $g:\subseteq{\mathbb{N}}^{\mathbb{N}}\to Y$.
Let now $f:\subseteq X\rightrightarrows Y$ be limit computable. By Theorem 5
there is a computable $h:\subseteq X\rightrightarrows Y^{\mathbb{N}}$ such
that $\lim_{Y}\circ h\sqsubseteq f$. Let $\delta\equiv\delta_{X}$ be a
representation of $X$ that is equivalent to the Cauchy representation
$\delta_{X}$ and that makes
$\kappa_{X}:X\to{\mathcal{K}}_{+}({\mathbb{N}}^{\mathbb{N}}),x\mapsto\delta^{-1}\\{x\\}$
computable, where ${\mathcal{K}}_{+}({\mathbb{N}}^{\mathbb{N}})$ denotes the
space of compact subsets of ${\mathbb{N}}^{\mathbb{N}}$ endowed with the
representation
$\delta_{{\mathcal{K}}_{+}({\mathbb{N}}^{\mathbb{N}})}(p)=K:\iff{\mathrm{range}}(p)=\\{n\in{\mathbb{N}}:K\cap
B_{n}\not=\emptyset\\}$. Such a representation $\delta$ with compact fibers
$\delta^{-1}\\{x\\}$ exists for every computable metric space [6, Lemma 6.3
(5)]. Let $F$ be a computable realizer of $h$, i.e.,
$\lim_{Y}\delta_{Y^{\mathbb{N}}}F\sqsubseteq f\delta$. That $\kappa_{X}$ is
computable implies that the set

$U:=\\{(x,n,k)\in X\times{\mathbb{N}}^{2}:(\exists
p\in\delta^{-1}\\{x\\})(\exists
i>n)\;d_{Y}(\delta_{Y}(F(p)(i)),\delta_{Y}(F(p)(n)))>2^{-k}\\}$

is c.e. open relative to ${\mathrm{dom}}(f)\times{\mathbb{N}}^{2}$, and hence
there is a computable function $r:{\mathbb{N}}\to{\mathbb{N}}$ such that
$U_{r\langle n,k\rangle}\cap{\mathrm{dom}}(f)=\\{x\in X:(x,n,k)\in
U\\}\cap{\mathrm{dom}}(f)$. Let $x\in{\mathrm{dom}}(f)$ and
$k\in{\mathbb{N}}$. Then for all $p\in\delta^{-1}\\{x\\}$ there is some
$n\in{\mathbb{N}}$ such that for all $i>n$ we have
$d_{Y}(\delta_{Y}(F(p)(i)),\delta_{Y}(F(p)(n)))\leq 2^{-k}$, because
$(\delta_{Y}F(p)(n))_{n\in{\mathbb{N}}}$ is convergent. Since
$\delta^{-1}\\{x\\}$ is compact, the number $n\in{\mathbb{N}}$ even exists
uniformly for all $p\in\delta^{-1}\\{x\\}$. That is, for every
$x\in{\mathrm{dom}}(f)$ and $k\in{\mathbb{N}}$ there is some
$n\in{\mathbb{N}}$ with $x\not\in U_{r\langle n,k\rangle}$. With the help of
${\mathsf{{J}}}_{X}(x)(r\langle n,k\rangle)$ we can actually check this
condition, and hence we can compute an $s:{\mathbb{N}}\to{\mathbb{N}}$ such
that for each $k\in{\mathbb{N}}$ we obtain $x\not\in U_{r\langle
s(k),k\rangle}$. By Proposition 5 we can also obtain a
$p\in{\mathbb{N}}^{\mathbb{N}}$ with $\delta(p)=x$ from
${\mathsf{{J}}}_{X}(x)$. Hence there is a computable
$g:\subseteq{\mathbb{N}}^{\mathbb{N}}\to Y$ with
$g\circ{\mathsf{{J}}}_{X}(x)=\lim_{k\to\infty}\delta_{Y}(F(p)(s(k)))=\lim_{Y}\delta_{Y^{\mathbb{N}}}F(p)\sqsubseteq
f(x)$ for all $x\in{\mathrm{dom}}(f)$, where the first limit is computable
since it is effective (with speed of convergence $2^{-k}$, see the proof of
Proposition 5 for a detailed calculation). ∎

Since ${\mathsf{{J}}}_{X}$ is injective, we can assume that
${\mathrm{dom}}(g)$ is such that
${\mathrm{dom}}(g\circ{\mathsf{{J}}}_{X})={\mathrm{dom}}(f)$. We formulate the
characterization for single-valued functions as a corollary.

######  Corollary  (Jump normal form).

Let $X,Y$ be computable metric spaces and $f:\subseteq X\to Y$ a function.
Then the following are equivalent:

  1. (1)

$f:\subseteq X\to Y$ is limit computable,

  2. (2)

$f=g\circ{\mathsf{{J}}}_{X}$ for some computable
$g:\subseteq{\mathbb{N}}^{\mathbb{N}}\to Y$.

Another consequence of Theorem 5 is that every multi-valued limit computable
problem has a single-valued limit computable selector.

######  Corollary  (Selection).

Let $X,Y$ be computable metric spaces. For every limit computable $f:\subseteq
X\rightrightarrows Y$ there is a limit computable single-valued $g:\subseteq
X\to Y$ with $g\sqsubseteq f$.

Now we define $1$–genericity for computable metric spaces.

######  Definition  ($1$–genericity).

Let $X$ be a computable metric space. Then we call $x\in X$ _$1$ –generic_ if
it is a point of continuity of ${\mathsf{{J}}}_{X}$.

It is easy to see that $1$–generic points can be characterized as those points
that avoid the boundaries of all c.e. open sets. By $\partial U$ we denote the
_boundary_ of $U$.

######  Lemma  ($1$–genericity).

Let $X$ be a computable metric space. Then $x\in X$ is $1$–generic if and only
if $x\in X\setminus\bigcup_{i=0}^{\infty}\partial U_{i}$.

This characterization is equivalent to the definition of $1$–genericity as it
is used in computability theory and as it has been used in computable metric
spaces before (see [30, Corollary 2.3], [10, Lemma 9.2] or [27, Definition
2.1]). By the Baire category theorem every complete metric space is comeager
and since the set $\bigcup_{i=0}^{\infty}\partial U_{i}$ is meager, it follows
that the $1$–generics form a comeager $G_{\delta}$–set in any complete
computable metric space. In particular, in a complete computable metric space,
there are many $1$–generic points. We obtain the following characterization of
$1$–genericity.

######  Theorem  ($1$–genericity).

Let $X$ be a computable metric space. Then $x\in X$ is $1$–generic if and only
if for every computable metric space $Y$, every limit computable $f:\subseteq
X\to Y$ with $x\in{\mathrm{dom}}(f)$ is continuous at $x$.

###### Proof.

For the “if” direction it is sufficient to consider
$Y={\mathbb{N}}^{\mathbb{N}}$ and
$f={\mathsf{{J}}}_{X}:X\to{\mathbb{N}}^{\mathbb{N}}$. For the “only if”
direction we assume that $f:\subseteq X\to Y$ is limit computable and
$x\in{\mathrm{dom}}(f)$. Then by Corollary 5 there is a computable
$g:\subseteq{\mathbb{N}}^{\mathbb{N}}\to X$ such that
$f=g\circ{\mathsf{{J}}}_{X}$. Hence, it follows that $f$ is continuous at $x$.
∎

The “if” direction of this theorem can be seen as a computability theoretic
version of a well-known theorem of Baire that states that every Baire class
$1$ function has a comeager $G_{\delta}$–set of continuity points [29, Theorem
24.14]. We note that the “only if” direction of Theorem 5 for the special case
of $X=[0,1]$ was also proved by Kuyper and Terwijn [30, Theorem 4.2].

Since $\lim_{X}$ is not continuous at any point for computable metric spaces
$X$ with at least two points, it follows that no $1$–generic sequence in such
a space is convergent.

######  Corollary  ($1$–generic sequences).

Let $X$ be a computable metric space with at least two points. Then every
sequence $(x_{n})_{n\in{\mathbb{N}}}$ that is a $1$–generic point in
$X^{\mathbb{N}}$ is not convergent.

The following result generalizes Proposition 2 to computable metric spaces.

######  Proposition  (Jump on $1$–generics).

The Turing jump operator ${\mathsf{{J}}}_{X}:X\to{\mathbb{N}}^{\mathbb{N}}$
restricted to the set of $1$–generic points $x\in X$ is computable relative to
the halting problem for all computable metric spaces $X$.

###### Proof.

We consider the metric space $(X,d)$ and we define the relations of _formal
inclusion_ and _formal disjointness_ by

  1. (1)

$B_{\langle c_{1},r_{1}\rangle}\lhd B_{\langle c_{2},r_{2}\rangle}:\iff
d(\alpha(c_{1}),\alpha(c_{2}))+\overline{r_{1}}<\overline{r_{2}}$,

  2. (2)

$B_{\langle c_{1},r_{1}\rangle}\bowtie B_{\langle c_{2},r_{2}\rangle}:\iff
d(\alpha(c_{1}),\alpha(c_{2}))>\overline{r_{1}}+\overline{r_{2}}$.

These are rather relations between the numbers $c_{1},r_{1}\in{\mathbb{N}}$
and $c_{2},r_{2}\in{\mathbb{N}}$ than between the corresponding balls, but
they are denoted for convenience in the given way. It is clear that both
relations are c.e. and that $B_{j}\lhd B_{i}$ implies $B_{j}\subseteq B_{i}$
and $B_{j}\bowtie B_{i}$ implies $B_{j}\cap B_{i}=\emptyset$. The sets

  1. (1)

$A:=\\{(n,j)\in{\mathbb{N}}^{2}:(\exists i\in W_{n})\;B_{j}\lhd B_{i}\\}$,

  2. (2)

$B:=\\{(n,j)\in{\mathbb{N}}^{2}:(\forall i\in W_{n})\;B_{j}\bowtie B_{i}\\}$

are both computable relative to $0^{\prime}$. A $1$–generic $x\in X$ satisfies
$x\in X\setminus\bigcup_{n=0}^{\infty}\partial U_{n}$ and hence

  1. (1)

$x\in U_{n}\iff(\exists j\in{\mathbb{N}})(x\in B_{j}$ and $(n,j)\in A)$,

  2. (2)

$x\not\in U_{n}\iff(\exists j\in{\mathbb{N}})(x\in B_{j}$ and $(n,j)\in B)$.

Thus, for each $1$–generic $x$ we can systematically search for some
$j\in{\mathbb{N}}$ such that $x\in B_{j}$ and either $(n,j)\in A$ or $(n,j)\in
B$ and the condition that holds tells us how to compute
${\mathsf{{J}}}_{X}(x)(n)$. Hence, ${\mathsf{{J}}}_{X}$ restricted to
$1$–generics is computable relative to $0^{\prime}$. ∎

Another consequence of the jump normal form (Theorem 5) together with
Proposition 5 is the following result that generalizes Corollary 2.

######  Corollary  (Limit computability on $1$–generics).

Restricted to $1$–generics every limit computable $F:\subseteq X\to Y$ on
computable metric spaces $X,Y$ is computable relative to the halting problem.

Now the question appears how the property of being $1$–generic relates to the
property of having a $1$–generic name. What we can prove in general is that
atypical points have atypical names. As a preparation we need to show that
admissible representations are hereditarily quotient maps. We recall that a
representation $\delta$ of a topological space $X$ is called _admissible_
(with respect to this space) if and only if it is maximal with respect to the
topological version $\mathop{\leq_{\mathrm{t}}}$ of the reducibility $\leq$
among all continuous representations [44]. The Cauchy representation
$\delta_{X}$ is an example of an admissible representation [52, Theorem
8.1.4], and hence any representation $\delta\equiv\delta_{X}$ is also
admissible. It follows from the second half of the proof of [44, Theorem 4]
that admissible representations are hereditary quotient maps in the following
sense.

######  Lemma  (Hereditary quotients).

Let $\delta$ be an admissible representation of a topological space $X$, and
let $Y$ be another topological space. Let $f:\subseteq X\to Y$ be a function
and $x\in{\mathrm{dom}}(f)$. If $f\delta$ is continuous at all
$p\in\delta^{-1}\\{x\\}$, then $f$ is sequentially continuous at $x$.

Since every metric space $X$ is sequential, we can replace sequential
continuity by ordinary continuity in this case. Then the property expresses
what is usually called a hereditary quotient map or a pseudo-open map [2].

######  Corollary  (Hereditary quotients).

Every admissible representation of a sequential topological space is a
hereditary quotient map (or equivalently, is pseudo-open).

Using Lemma 5 we can now prove the following result, which shows that atypical
points have atypical names with respect to every representation in the
equivalence class of the Cauchy representation.

######  Proposition  (Non-generic names).

Let $X$ be a computable metric space with Cauchy representation $\delta_{X}$
and $x\in X$. Let $\delta\equiv\delta_{X}$ be another representation of $X$.
If $x$ is not $1$–generic, then there is a $p\in{\mathbb{N}}^{\mathbb{N}}$
with $\delta(p)=x$ that is not $1$–generic.

###### Proof.

By Propositions 5 and 2 there is some computable $F$ such that
${\mathsf{{J}}}_{X}\delta=F{\mathsf{{J}}}$. Let $x$ be such that all names
$p\in\delta^{-1}\\{x\\}$ are $1$–generic. Then $F{\mathsf{{J}}}$ is continuous
at all these $p$ and hence so is ${\mathsf{{J}}}_{X}\delta$. By Lemma 5 this
implies that ${\mathsf{{J}}}_{X}$ is continuous at $x$, hence $x$ is
$1$–generic. ∎

This result captures as much as can be said about the relation of arbitrary
points and their names with respect to genericity in arbitrary computable
metric spaces. It is easy to see that in the equivalence class of the Cauchy
representation $\delta_{X}$ there are always representations without
$1$–generic names: one can for instance define $\delta\equiv\delta_{X}$ such
that names are always zero in every second component and hence not
$1$–generic. But even if we restrict ourselves to total
$\delta\equiv\delta_{X}$ for complete metric spaces $X$, then there are spaces
such as $X={\mathbb{N}}$ in which all points are $1$–generic. Hence having a
non $1$–generic name does not imply being not $1$–generic in general. If we
consider the case of the reals $X={\mathbb{R}}$ and reasonable total variants
of the Cauchy representation (such as the one from [10, Lemma 6.1]), then
there are syntactic properties of names such as: every component of the name
encodes a rational number with even denominator. This property constitutes a
co-c.e. closed set $A\subseteq{\mathbb{N}}^{\mathbb{N}}$ that is nowhere
dense, i.e., $\partial A=A$, which means that all points in $A$ are not
$1$–generic. On the other hand, every real $x$, in particular every
$1$–generic real, has a name $p\in A$. Thus having a non $1$–generic name does
not imply being not $1$–generic for such a representation. For special types
of spaces and special representations one can provide further results along
these lines. For instance Kuyper and Terwijn proved that an irrational number
$x\in[0,1]$ is $1$–generic if and only if its unique binary expansion is
$1$–generic [30, Proposition 2.5].

##  6\. Limit computability and computability relative to the halting problem

It is clear that every function that is computable relative to the halting
problem is also limit computable. This observation even holds uniformly in the
sense specified in the following corollary. The corollary is a consequence of
Theorem 4 (3) since ${\mathrm{id}}:X\to X^{\prime}$ is computable.

######  Corollary  (Limit computability of functions computable relative to
the halting problem).

${\mathrm{id}}:{\mathcal{C}}(X,Y)^{\prime}\to{\mathcal{C}}(X,Y^{\prime})$ is
computable for all represented spaces $X,Y$.

For some spaces, such as $X={\mathbb{N}}$, this identity is even a computable
isomorphism (see Corollary 4). However, it is clear that this does not happen
for many other spaces $X,Y$ since often
${\mathcal{C}}(X,Y)^{\prime}\subsetneqq{\mathcal{C}}(X,Y^{\prime})$. The
former set contains only continuous functions, the latter can contain
discontinuous ones. Even restricted to continuous functions the identity in
Corollary 6 is not a computable isomorphism in general.

We can, however, characterize the functions that are computable relative to
the halting problems in terms of limit computable functions. For this purpose
we need the notion of a modulus of continuity. Let $(X,d_{X})$ and $(Y,d_{Y})$
be metric spaces and $f:X\to Y$ a function. Then
$m:{\mathbb{N}}\to{\mathbb{N}}$ is called a _modulus of continuity_ of $f$ at
$x\in X$ if

$d_{X}(x,y)<2^{-m(n)}\Longrightarrow d_{Y}(f(x),f(y))<2^{-n}$

holds for all $y\in X$ and $n\in{\mathbb{N}}$. The following result is well-
known (see, for instance, [3, Lemma 4.4.25]).

######  Proposition  (Modulus of continuity).

Let $X,Y$ be computable metric spaces. Then

$\mathsf{Mod}:{\mathcal{C}}(X,Y)\times
X\rightrightarrows{\mathbb{N}}^{\mathbb{N}},(f,x)\mapsto\\{m\in{\mathbb{N}}^{\mathbb{N}}:m\mbox{
is a modulus of continuity of $f$ at $x$}\\}$

is computable.

We call
$M:X\rightrightarrows{\mathbb{N}}^{\mathbb{N}},x\mapsto\\{m\in{\mathbb{N}}^{\mathbb{N}}:m$
is a modulus of continuity of $f$ at $x\\}$ the _global modulus of continuity_
of $f$. Using the previous proposition we can prove the following
characterization.

######  Theorem  (Computability relative to the halting problem).

Let $X,Y$ be computable metric spaces and let $f:X\to Y$ be a function. Then
the following are equivalent:

  1. (1)

$f$ is computable relative to the halting problem,

  2. (2)

$f$ is limit computable and continuous and its global modulus of continuity is
computable relative to the halting problem.

###### Proof.

Let $f:X\to Y$ be computable relative to the halting problem. Then
$f:X^{\prime}\to Y^{\prime}$ is computable by Theorem 4, and hence $f$ is
computable as a point in ${\mathcal{C}}(X,Y)^{\prime}$ by Theorem 4. In
particular, $f$ is also limit computable (see Corollary 6). By Theorem 4 and
Proposition 4 the problem $\mathsf{Mod}$ from Proposition 6 is computable with
type $\mathsf{Mod}:{\mathcal{C}}(X,Y)^{\prime}\times
X^{\prime}\rightrightarrows({\mathbb{N}}^{\mathbb{N}})^{\prime}$, and hence
the global modulus of $f$ is computable with type
$M:X^{\prime}\rightrightarrows({\mathbb{N}}^{\mathbb{N}})^{\prime},x\mapsto\mathsf{Mod}(f,x)$.
By Theorem 4 this means that $M$ is computable relative to the halting
problem.

Let now $f$ be limit computable and continuous with a global modulus of
continuity $M$ that is computable relative to the halting problem. We consider
the computable metric spaces $(X,d_{X},\alpha)$ and $(Y,d_{Y})$. If $f$ is
limit computable, then also $f\circ\alpha:{\mathbb{N}}\to Y$ is limit
computable and hence computable relative to the halting problem by Corollary
4. Given $x\in X$ and $k\in{\mathbb{N}}$, we can compute with the help of the
halting problem a modulus of continuity $m:{\mathbb{N}}\to{\mathbb{N}}$ of $f$
at $x$, and we can compute an $n\in{\mathbb{N}}$ with
$d_{X}(\alpha(n),x)<2^{-m(k)}$, which implies $d_{Y}(f\alpha(n),f(x))<2^{-k}$.
Since $f\alpha(n)$ can be computed with the help of the halting problem, we
have found an approximation of $f(x)$ with precision $2^{-k}$ with the help of
the halting problem. This means that $f$ is computable relative to the halting
problem. ∎

This result tells us exactly which additional condition beyond continuity a
limit computable function $f:X\to Y$ must satisfy in order to be computable
relative to the halting problem. If a function is limit computable and just
continuous on metric spaces, then a hyperarithmetical oracle is sufficient to
compute it. In fact, we can prove an even stronger result.666This stronger
result and its proof have been kindly suggested by an anonymous referee.

######  Theorem  (Effective Borel measurability and continuity).

Let $X,Y$ be computable metric spaces and let $X$ be complete. Let $A\subseteq
X$ be an effective $\Sigma^{1}_{1}$–subset and let $f:A\to Y$ be a function.
If $f$ is effectively Borel measurable and continuous, then $f$ is computable
relative to some hyperarithmetical oracle (i.e., an oracle in
$\Delta^{1}_{1}$).

###### Proof.

We use a standard numbering $(U_{n}^{p})_{n\in{\mathbb{N}}}$ of the sets
$U_{n}^{p}\subseteq Y$ that are c.e. relative to
$p\in{\mathbb{N}}^{\mathbb{N}}$. We omit the upper index in order to denote
the unrelativized c.e. open subsets. For any c.e. open set $U_{n}\subseteq Y$
we have that $f^{-1}(U_{n})$ is effectively $\Delta^{1}_{1}$ and open in $A$,
i.e., we can effectively find some $\Delta_{1}^{1}$–set $D_{n}$ in $X$ and
there is an open set $V\subseteq X$ such that $f^{-1}(U_{n})=V\cap A=D_{n}\cap
A$. In particular, $f^{-1}(U_{n})$ and $A\setminus f^{-1}(U_{n})$ are
effectively $\Sigma^{1}_{1}$ in $X$ and separated by the open set $V$. Then by
the Louveau separation theorem [32, Theorem B, page 369] the sets
$f^{-1}(U_{n})$ and $A\setminus f^{-1}(U_{n})$ are also separated by a
$\Sigma^{0,p}_{1}$–set for some hyperarithmetical
$p\in{\mathbb{N}}^{\mathbb{N}}$ (i.e., by a c.e. open set relative to $p$).
Hence $f^{-1}(U_{n})=U_{k}^{p}\cap A$ for some $k\in{\mathbb{N}}$ and some
hyperarithmetical $p\in{\mathbb{N}}^{\mathbb{N}}$. Now we consider the
function $g:{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}},n\mapsto\langle
k,p\rangle$. The property $B:=\\{\langle
n,k,p\rangle\in{\mathbb{N}}^{\mathbb{N}}:f^{-1}(U_{n})=U_{k}^{p}\cap A\\}$ is
an effective $\Pi^{1}_{1}$–property, since

$\langle n,k,p\rangle\in B\iff(\forall x\in X)((x\not\in U_{k}^{p}\cap A\vee
x\in D_{n})\wedge(x\not\in f^{-1}(U_{n})\vee x\in U_{k}^{p})).$

Hence, by the effective $\Pi^{1}_{1}$–uniformization theorem [33, Theorem
4E.4] the function $g$ is a total $\Pi^{1}_{1}$–function, hence in
$\Delta^{1}_{1}$. Clearly, $f$ is computable relative to $g$. ∎

As an immediate corollary we obtain the following result.

######  Corollary  (Limit computability and continuity).

Let $X,Y$ be computable metric spaces and let $X$ be complete. If $f:X\to Y$
is limit computable and continuous, then $f$ is computable relative to some
hyperarithmetical oracle (i.e., an oracle in ${{\Delta}^{1}_{1}}$).

For uniformly continuous functions we can improve this result. In this case
even the jump of the halting problem suffices to compute the function.

######  Theorem  (Limit computability and uniform continuity).

Let $X,Y$ be computable metric spaces. If $f:X\to Y$ is limit computable and
uniformly continuous, then $f$ is computable relative to $0^{\prime\prime}$.

###### Proof.

We consider the computable metric spaces $(X,d_{X},\alpha)$ and $(Y,d_{Y})$.
As in the proof of Theorem 6 we obtain that $f\circ\alpha:{\mathbb{N}}\to Y$
is computable relative to $0^{\prime}$. Additionally, the set

$A:=\\{(n,k)\in{\mathbb{N}}^{2}:(\exists
i,j\in{\mathbb{N}})(d_{X}(\alpha(i),\alpha(j))<2^{-n}\mbox{ and
}d_{Y}(f\alpha(i),f\alpha(j))>2^{-k})\\}$

is c.e. relative to $0^{\prime}$ and hence computable relative to
$0^{\prime\prime}$. Since $f$ is uniformly continuous, it follows that for
each $k\in{\mathbb{N}}$ there are only finitely many $n\in{\mathbb{N}}$ with
$(n,k)\in A$. Hence, for each $k\in{\mathbb{N}}$ we can compute some $m(k)$
with $(m(k),k+1)\not\in A$ with the help of $0^{\prime\prime}$ and
$m:{\mathbb{N}}\to{\mathbb{N}}$ is a uniform modulus of continuity of $f$
(i.e., at every $x\in X$). We can proceed as in the proof of Theorem 6 to show
that $f$ is computable relative to $0^{\prime\prime}$. ∎

It is clear that this theorem also holds for compact computable metric spaces
$X$ and continuous and limit computable $f$, since any such $f$ is
automatically uniformly continuous.

######  Corollary  (Limit computability and uniform continuity).

Let $X,Y$ be computable metric spaces and let $X$ be compact. If $f:X\to Y$ is
limit computable and continuous, then $f$ is computable relative to
$0^{\prime\prime}$.

We could also prove such a result for effectively locally compact $X$ and
continuous and limit computable $f$, since it is sufficient to obtain the
modulus of continuity for a suitable neighborhood of the input.

We will show that Theorem 6 gives the best possible condition and
$0^{\prime\prime}$ cannot be improved to $0^{\prime}$. In the following we
will see some examples of continuous functions that are limit computable but
not computable relatively to the halting problem. For these examples we use
the set ${\mathsf{{Fin}}}:=\\{n\in{\mathbb{N}}:W_{n}$ finite$\\}$, which is
known to be ${\Sigma^{0}_{2}}$–complete in the arithmetical hierarchy [47,
Theorem 4.3.2], and hence it is not computable relative to the halting
problem. Its complement
${\mathsf{{Inf}}}:={\mathbb{N}}\setminus{\mathsf{{Fin}}}$ is
${\Pi^{0}_{2}}$–complete and hence not even c.e. relative to the halting
problem. By $|A|$ we denote the _cardinality_ of a set $A$.

######  Proposition .

There exists a uniformly continuous function $f:2^{\mathbb{N}}\to{\mathbb{R}}$
that is computable with finitely many mind changes and hence low and limit
computable, but that is not computable relative to the halting problem.

###### Proof.

We define $f:2^{\mathbb{N}}\to{\mathbb{R}}$ by

$f(p):=\left\\{\begin{array}[]{ll}2^{-n}&\mbox{if
$0^{n}1^{|W_{n}|+1}0\sqsubseteq p$ for some $n\in{\mathsf{{Fin}}}$}\\\
0&\mbox{otherwise}\end{array}\right..$

Then $f$ is continuous and hence uniformly continuous, since $2^{\mathbb{N}}$
is compact. We use a fixed computable enumeration
$e_{n}:{\mathbb{N}}\to{\mathbb{N}}$ of $W_{n}$, i.e.,
${\mathrm{range}}(e_{n})=W_{n}$. The following algorithm shows that $f$ is
computable with finitely many mind changes:

  1. (1)

We start producing the default output $0$ as long as no other value is
determined in the next step.

  2. (2)

As soon as a prefix of the input $p$ of form $0^{n}1^{k+1}0w$ with
$w\in\\{0,1\\}^{m}$ is known, we check if there are exactly $k$ different
values among the numbers $e_{n}(0),...,e_{n}(m)$. If so, then the output is
replaced by $2^{-n}$, otherwise by $0$.

This algorithm describes a computation with finitely many mind changes, since
for any fixed input $p$, the output value changes at most two times. In
particular, $f$ is low and limit computable. Let us assume that $f$ is
computable relative to the halting problem. Then by Corollary 5 there exists a
computable sequence $(f_{k})_{k\in{\mathbb{N}}}$ of computable functions
$f_{k}:2^{\mathbb{N}}\to{\mathbb{R}}$ such that
$\lim_{k\to\infty}||f_{k}-f||=0$. Since the sequence
$(K_{n})_{n\in{\mathbb{N}}}$ with $K_{n}:=0^{n}12^{\mathbb{N}}$ is a
computable sequence of computably compact sets, it follows that
$(f_{k}(K_{n}))_{\langle k,n\rangle\in{\mathbb{N}}}$ is a computable sequence
of computably compact sets too [37]. Since the maximum is computable on
computably compact sets by [52, Lemma 5.2.6], it follows that $(\max
f_{k}(K_{n}))_{k\in{\mathbb{N}}}$ is a computable sequence, and it converges
for each $n\in{\mathbb{N}}$ to $\max f(K_{n})$. Hence, by

$s_{n}:=\lim_{k\to\infty}\max f_{k}(K_{n})=\max
f(0^{n}12^{\mathbb{N}})=\left\\{\begin{array}[]{ll}2^{-n}&\mbox{if
$n\in{\mathsf{{Fin}}}$}\\\ 0&\mbox{otherwise}\end{array}\right.$

we define a sequence of numbers $(s_{n})_{n\in{\mathbb{N}}}$ that is limit
computable and hence computable relative to the halting problem by Corollary
4. But this would imply that ${\mathsf{{Fin}}}$ is computable relative to the
halting problem. Contradiction! ∎

We can transfer this construction from Cantor space to the unit interval
$[0,1]$.

######  Proposition .

There exists a uniformly continuous function $f:[0,1]\to{\mathbb{R}}$ that is
computable with finitely many mind changes and hence low and limit computable,
but that is not computable relative to the halting problem.

###### Proof.

We use the computable “triangle” function

$\Delta:{\mathbb{R}}\to{\mathbb{R}},x\mapsto\left\\{\begin{array}[]{ll}1-|x|&\mbox{if
$-1\leq x\leq 1$}\\\ 0&\mbox{otherwise}\end{array}\right.$

This function has the extreme values $f(-1)=f(1)=0$ and $f(0)=1$ and
interpolates linearly between them otherwise. Outside of the interval $(-1,1)$
the function $f$ is identically zero. We define a computable double sequence
$(\Delta_{n,k})_{n,k\in{\mathbb{N}}}$ of triangle functions
$\Delta_{n,k}:[0,1]\to{\mathbb{R}}$ scaled to the interval
$I_{n,k}:=(2^{-n-1},2^{-n-1}+2^{-n-k-1})$ by

$\Delta_{n,k}(x):=\Delta(2^{n+k+2}(x-2^{-n-1})-1)$

The function $\Delta_{n,k}$ is zero outside of $K_{n}:=[2^{-n-1},2^{-n}]$, in
fact even outside of the interval $I_{n,k}$. With growing $k$ the triangle of
$\Delta_{n,k}$ is compressed further on the left hand side of $K_{n}$. We
define a continuous function $f:[0,1]\to{\mathbb{R}}$ by

$f(x):=\sum_{n\in{\mathsf{{Fin}}}}2^{-n}\Delta_{n,|W_{n}|}(x).$

Similarly as in the proof of Proposition 6 one can show that $f$ is computable
with finitely many mind changes and not computable relative to the halting
problem. For the latter part one considers the values $s_{n}:=\max f(K_{n})$.
For the former part we proceed as follows with a given input $x\in[0,1]$:

  1. (1)

As long as we cannot exclude that $x=2^{-n}$ for some $n\in{\mathbb{N}}$ we
produce the value $0$ as output.

  2. (2)

As soon as we detect that $x\in(2^{-n-1},2^{-n})$ we consider the enumeration
$e_{n}(0),e_{n}(1),...$ of $W_{n}$.

  3. (3)

Whenever we find a new number $k$ of distinct values in this enumeration, then
we produce the value $2^{-n}\Delta_{n,k}(x)$ as output.

At any point $x$ at most a finite number of mind changes is required since
either the value $k$ stabilizes or $\Delta_{n,k}(x)=0$ for all sufficiently
large $k$. ∎

We note that Proposition 6 cannot be strengthened such that the function $f$
is additionally continuously differentiable (see Corollary 6). However, this
can be achieved by using smooth versions of the triangle function $\Delta$
that are distributed all over the entire real line.

######  Proposition .

There exists a function $f:{\mathbb{R}}\to{\mathbb{R}}$ that is infinitely
often differentiable, computable with finitely many mind changes and hence low
and limit computable, but that is not computable relative to the halting
problem.

###### Proof.

We use the computable “bump” function $\Delta:{\mathbb{R}}\to{\mathbb{R}}$

$\Delta(x):=\left\\{\begin{array}[]{ll}e^{\frac{1}{1-x^{2}}}&\mbox{if
$|x|<1$}\\\ 0&\mbox{otherwise}\end{array}\right.,$

which is infinitely often continuously differentiable, computable and zero
outside of $(-1,1)$. We define a computable double sequence
$(\Delta_{n,k})_{n,k\in{\mathbb{N}}}$ of bump functions
$\Delta_{n,k}:{\mathbb{R}}\to{\mathbb{R}}$ scaled to the interval
$I_{n,k}:=(n,n+2^{-k-1})$ by

$\Delta_{n,k}(x):=\Delta(2^{k+2}(x-n)-1)$

The function $\Delta_{n,k}$ is zero outside of $K_{n}:=[n,n+1]$, in fact even
outside of the interval $I_{n,k}$. With growing $k$ the triangle of
$\Delta_{n,k}$ is compressed further on the left hand side of $K_{n}$. We
define $f:{\mathbb{R}}\to{\mathbb{R}}$ by

$f(x):=\sum_{n\in{\mathsf{{Fin}}}}\Delta_{n,|W_{n}|}(x).$

Similarly as in the proof of Proposition 6 one can show that $f$ is computable
with finitely many mind changes and not computable relative to the halting
problem. Additionally, $f$ is infinitely often differentiable, since the
$\Delta_{n,k}$ are so. ∎

We can also produce a similar counterexample of type
$f:2^{\mathbb{N}}\to{\mathbb{S}}$, where ${\mathbb{S}}$ denotes _Sierpiński
space_ ${\mathbb{S}}=\\{0,1\\}$ that is represented by
$\delta_{\mathbb{S}}(p)=0:\iff p=\widehat{0}$.

######  Proposition .

There exists a continuous function $f:2^{\mathbb{N}}\to{\mathbb{S}}$ that is
computable with finitely many mind changes and hence low and limit computable,
but that is not computable relative to the halting problem.

###### Proof.

We define $f:2^{\mathbb{N}}\to{\mathbb{S}}$ by

$f(p):=\left\\{\begin{array}[]{ll}0&\mbox{if $p=\widehat{0}$}\\\ 0&\mbox{if
$0^{n}1^{|W_{n}|+1}0\sqsubseteq p$ for some $n\in{\mathsf{{Fin}}}$}\\\
1&\mbox{otherwise}\end{array}\right..$

The sets $A_{n}:=0^{n}1^{|W_{n}|+1}02^{\mathbb{N}}$ are clopen for every
$n\in{\mathsf{{Fin}}}$ and the set
$A:=\\{\widehat{0}\\}\cup\bigcup_{n\in{\mathsf{{Fin}}}}A_{n}$ is closed. Hence
$f$ is the characteristic function $\chi_{U}$ of the open set
$U=2^{\mathbb{N}}\setminus A$ and hence continuous. The following algorithm
shows that $f$ is computable with finitely many mind changes:

  1. (1)

We start producing the default output $0$ as long as no other value is
determined in the next step.

  2. (2)

As soon as a prefix of the input $p$ of form $0^{n}1^{k+1}0^{m+1}$ is known,
we check if there are exactly $k$ different values among the numbers
$e_{n}(0),...,e_{n}(m)$. If so, then the output is replaced by $0$, otherwise
by $1$.

This algorithm describes a computation with finitely many mind changes, since
for any fixed input $p$, the output value changes at most three times. In
particular, $f$ is limit computable.

Let us assume that $f=\chi_{U}$ is also computable relative to the halting
problem. We note that the map
${\mathcal{O}}(2^{\mathbb{N}})\to{\mathcal{C}}(2^{\mathbb{N}},{\mathbb{S}}),V\mapsto\chi_{V}$
is a computable isomorphism, and hence $U$ is a computable point in
${\mathcal{O}}(2^{\mathbb{N}})^{\prime}$. The map
$\forall_{K}:{\mathcal{O}}(2^{\mathbb{N}})\to{\mathbb{S}}$ with
$\forall_{K}(V)=1\iff K\subseteq V$ is computable for every computably compact
set $K\subseteq 2^{\mathbb{N}}$, and the map $K\mapsto\forall_{K}$ is a
computable isomorphism between the space of compact subsets of
$2^{\mathbb{N}}$ and
${\mathcal{C}}({\mathcal{O}}(2^{\mathbb{N}}),{\mathbb{S}})$ [37]. Since
$(K_{n})_{n\in{\mathbb{N}}}$ with $K_{n}:=0^{n}12^{\mathbb{N}}$ is a
computable sequence of computably compact sets, we obtain that
$\forall_{K_{n}}$ is computable uniformly in $n$. Hence
$n\mapsto\forall_{K_{n}}(U)$ is computable relatively to the halting problem
by Corollary 4. This is a contradiction since

$\forall_{K_{n}}(U)=1\iff 0^{n}12^{\mathbb{N}}\subseteq U\iff
n\in{\mathsf{{Inf}}}$

and ${\mathsf{{Inf}}}$ is not c.e. relative to the halting problem. ∎

Since a set $U\subseteq 2^{\mathbb{N}}$ is c.e. open (relative to some oracle
$q$) if and only if $\chi_{U}:2^{\mathbb{N}}\to{\mathbb{S}}$ is computable
(relative to $q$) and $F\subseteq 2^{\mathbb{N}}$ is a _computable
${\Sigma^{0}_{2}}$–set_ in the Borel hierarchy (or, equivalently, a
_computable $F_{\sigma}$–set_) if and only if
$\chi_{F}:2^{\mathbb{N}}\to{\mathbb{S}}^{\prime}$ is computable [38,
Proposition 26], the previous proposition can also be rephrased in the
following way.

######  Corollary .

There is a computable ${\Sigma^{0}_{2}}$–set $U\subseteq 2^{\mathbb{N}}$ in
the Borel hierarchy that is open, but not c.e. open relative to the halting
problem.

A similar result for ${\mathbb{R}}^{n}$ was proved by Ziegler [54, Theorem
4.4. a)]. There is even a much stronger counter example for $2^{\mathbb{N}}$.
There is a ${\Pi^{0}_{2}}$–set $A\subseteq 2^{\mathbb{N}}$ that is a singleton
(its only member being the $\omega$–jump of the empty set) such that this set
is closed but not a ${\Pi^{0}_{1}}$–set relative to $0^{(n)}$ for any
$n\in{\mathbb{N}}$ (see [35, Proposition 1.8.62 and Exercise 1.8.67], [42, §
15.1 Theorem XII] and [31]).

######  Proposition  (Kuznécov and Trahténbrot 1955).

There is a ${\Sigma^{0}_{2}}$–set $A\subseteq 2^{\mathbb{N}}$ with a singleton
complement that is not c.e. open relative to $0^{(n)}$ for any
$n\in{\mathbb{N}}$.

Further results along these lines can be found in [14]. If we re-translate
this back to functions, then we obtain the following corollary.

######  Corollary .

There is a continuous and limit computable $f:2^{\mathbb{N}}\to{\mathbb{S}}$
that is not computable relative to $0^{(n)}$ for any $n\in{\mathbb{N}}$.

This also shows that Corollary 6 cannot be generalized to arbitrary spaces $Y$
and that the function $f$ in Corollary 6 cannot have a realizer
$F:2^{\mathbb{N}}\to{\mathbb{N}}^{\mathbb{N}}$ that is simultaneously
continuous and limit computable, even though it has separate realizers with
each of these properties individually.

There are some classes of functions for which the condition on the modulus of
continuity in Theorem 6 is automatically satisfied. The first example is the
class of Hölder continuous functions. Let $(X,d_{X})$ and $(Y,d_{Y})$ be
metric spaces. Then $f:X\to Y$ is called _Hölder continuous_ with constant
$L>0$ and exponent $\alpha\in(0,1]$ if

$d_{Y}(f(x),f(y))\leq Ld_{X}(x,y)^{\alpha}$

holds for all $x,y\in X$. A function is called _Lipschitz continuous_ with
constant $L>0$ if it is Hölder continuous with constant $L$ and exponent
$\alpha=1$. Since every Hölder continuous function automatically has a
computable constant $L$ (perhaps slightly larger than necessary) and a
computable exponent $\alpha$ (perhaps slightly smaller than necessary and
correct at least for small distances $d_{X}(x,y)<1$), it follows that it
automatically has a computable global modulus of continuity. Hence we obtain
the following corollary of Theorem 6.

######  Corollary  (Hölder continuity).

Let $X$ and $Y$ be computable metric spaces, and let $f:X\to Y$ be Hölder
continuous. Then $f$ is limit computable if and only if $f$ is computable
relative to the halting problem.

Restricted to the set of Hölder continuous functions with a fixed Lipschitz
constant $L$ and a fixed exponent $\alpha$ the map in Corollary 6 is even a
computable isomorphism, as the proof of “(2)$\Longrightarrow$(1)” of Theorem 6
is uniform. We note that even restricted to Lipschitz continuous functions the
notions of a low function and a function that is computable relative to a low
oracle are incomparable by Proposition 4.

In the table in Figure 2 we summarize which oracle classes are sufficient to
compute a limit computable function $f:X\to Y$ on complete computable metric
spaces that satisfies extra continuity assumptions.

$f$ limit computable and | oracle class
---|---
continuous | ${{\Delta}^{1}_{1}}$
uniformly continuous | ${\Sigma^{0}_{2}}$
Lipschitz or Hölder continuous | ${\Sigma^{0}_{1}}$
Figure 2. Oracle classes sufficient to compute $f:X\to Y$.

Since every continuously differentiable function $f:[0,1]\to{\mathbb{R}}$ is
Lipschitz continuous with Lipschitz constant $\max f^{\prime}[0,1]$, we obtain
the following conclusion (here it is important that $[0,1]$ is compact, and
the conclusion does not hold for functions of type
$f:{\mathbb{R}}\to{\mathbb{R}}$ by Proposition 6).

######  Corollary  (Continuously differentiable functions).

Let $f:[0,1]\to{\mathbb{R}}$ be continuously differentiable. Then $f$ is limit
computable if and only if $f$ is computable relative to the halting problem.

We can also draw some conclusions on linear operators. We recall that a
computable normed space is just a separable normed space such that the induced
metric space is computable and makes the algebraic operations computable. By
the Borel graph theorem of Schwartz [45] (see also [1, Corollary II.10.4])
every Borel measurable linear operator $T:X\to Y$ from a Banach space $X$ to a
normed space $Y$ is continuous, i.e., bounded. Using Theorem 6 we obtain the
following conclusion on effectively Borel measurable operators.

######  Corollary  (Borel measurable linear functions).

Let $X$ be a computable Banach space, let $Y$ be computable normed spaces, and
let $T:X\to Y$ be linear. Then $T$ is effectively Borel measurable if and only
if it is computable relative to a hyperarithmetical oracle (i.e., a
$\Delta^{1}_{1}$ oracle).

Every linear bounded operator is automatically Lipschitz continuous. In the
special case of limit computability Corollary 6 yields the following.

######  Corollary  (Limit computable linear functions).

Let $X$ be a computable Banach space, $Y$ be computable normed spaces, and let
$T:X\to Y$ be linear. Then $T$ is limit computable if and only if $T$ is
computable relative to the halting problem.

##  7\. Applications

In this section we discuss a number of simple applications of the tools that
we have developed in the previous sections. Some of the results that we derive
are known, but our techniques provide very simple proofs. Other results are
new.

We start with considering distance functions. For every subset $A\subseteq X$
of a metric space $(X,d)$ we define the _distance function_
$d_{A}:X\to{\mathbb{R}},x\mapsto\inf_{y\in A}d(x,y)$. Every distance function
$d_{A}$ satisfies $|d_{A}(x)-d_{A}(y)|\leq d(x,y)$ for all $x,y\in X$, which
means that every distance function is Lipschitz continuous with Lipschitz
constant $1$.

######  Corollary  (Distance functions).

Let $X$ be a computable metric space and $A\subseteq X$. The distance function
$d_{A}:X\to{\mathbb{R}}$ is limit computable if and only if it is computable
relative to the halting problem.

We recall that a problem $f:X\to{\mathbb{R}}$ is called _lower semi-
computable_ if it is computable as a function $f:X\to{\mathbb{R}}_{<}$ with
the real numbers ${\mathbb{R}}_{<}$ equipped with the lower Dedekind cut
representation, and likewise $f$ is called _upper semi-computable_ if it is
computable as a function $f:X\to{\mathbb{R}}_{>}$, where the real numbers
${\mathbb{R}}_{>}$ are equipped with the upper Dedekind cut representation.
Since it is clear that ${\mathrm{id}}:{\mathbb{R}}_{<}\to{\mathbb{R}}$ and
${\mathrm{id}}:{\mathbb{R}}_{>}\to{\mathbb{R}}$ are limit computable [8,
Proposition 3.7], we obtain the following conclusion.

######  Corollary  (Semi-computable functions).

Every lower or upper semi-computable function $f:X\to{\mathbb{R}}$ is limit
computable.

By $f^{\circ n}$ we denote the $n$–fold composition of $f$ with itself, i.e.,
$f^{\circ 0}={\mathrm{id}}$, $f^{\circ 1}=f$, $f^{\circ 2}=f\circ f$, etc. It
is easy to see that the _Mandelbrot set_ $M:=\\{c\in{\mathbb{C}}:(\forall
n\in{\mathbb{N}})\;|f^{\circ n}_{c}(0)|\leq 2\\}$, which is defined using the
iteration function $f_{c}:{\mathbb{C}}\to{\mathbb{C}},z\mapsto z^{2}+c$, is