nLab computable function (analysis)

Idea

A computable function is often taken to be one that acts on the natural numbers (a partial recursive function) but for purposes of analysis (computable analysis, exact analysis) and related fields (notably physics, see at computable physics) one considers computation on real numbers to finite but arbitrary precision. This means that in this context of analysis a computable function should be an algorithm that successively reads in natural numbers from a possibly infinite list (specifying an input to ever higher accuracy) and accordingly outputs a result as incrementally as an infinite list.

Mathematically this is captured by continuous functions on quotient spaces of Baire space (computability) and goes by the name Type Two Theory of Effectivity or similar. In implementations this is essentially what is known as exact real computer arithmetic.

Definition

In Type Two Theory of Effectivity for computable analysis (see Weihrauch 00) one considers the following definition:

A representation of a $T_0$-topological space $X$ is a presentation of it as a quotient space of a subspace $B$ of Baire space (the underlying space of Kleene's second algebra). See also at effective topological space.

Such a representation is called admissible if the quotient map $B \to X$ has the right lifting property against continuous functions out of other subspaces $B'$ of Baire space.

Given representations of $X$ and $X'$ in this way, then a function $f \colon X \to X'$ is called continuously realizable if there exists a continuous function $\phi \colon B \to B'$ between the corresponding subspaces of Baire space such that the evident diagram commutes.

For admissible representations a function $X\to X'$ is continuously realizable precisely if it is already continuous.

Write $AdmRep$ for the category of admissible representations in this sense, and continuously realizable (and hence continuous) functions between these.

Properties

General

The category $AmdRep$ is cartesian closed and has all countable limits and colimits (BSS 07 (4.10))

Relation to function realizability

The category $AdmRep$ above is a reflective subcategory of the function realizability topos $RT(\mathcal{K}_2)$ (see vanOosten 08).

Relation to topology

$AdmRep$ is equivalent to the full subcategory of that of topological spaces on the $T_0$-quotient spaces of countably based $T_0$ spaces (BSS 07).

Examples

Under the above inclusion, all complete separable metric spaces are in $AdmRep$.

Some standard classes of examples (with an eye towards applications in computable physics) are discussed in Weihrauch-Zhong 02, def. 2.6

Since the Sierpinski space is in $AdmRep$, and due to cartesian clossure above, for any $X \in AdmRep$ also its lattice of closed subspaces is in $AdmRep$.

Related concepts

computability

	type I computability	type II computability
typical domain	natural numbers $\mathbb{N}$	Baire space of infinite sequences $\mathbb{B} = \mathbb{N}^{\mathbb{N}}$
computable functions	partial recursive function	computable function (analysis)
type of computable mathematics	recursive mathematics	computable analysis, Type Two Theory of Effectivity
type of realizability	number realizability	function realizability
partial combinatory algebra	Kleene's first partial combinatory algebra	Kleene's second partial combinatory algebra

The subcategory on the effectively computable morphisms of the function realizability topos $RT(\mathcal{K}_2)$ is the Kleene-Vesley topos. The category of “admissible representations” $AdmRep$ above is a a reflective subcategory of $RT(\mathcal{K}_2)$ and the restriction of that to $KV$ is $AdmRep_{eff}$

$$\array{ AdmRep_{eff} &\hookrightarrow& KV \\ \downarrow && \downarrow \\ AdmRep &\hookrightarrow& RT(\mathcal{K}_2) }$$

See also

• topological domain theory

References

Lecture notes include

• Andrej Bauer, section 2 of Realizability as connection between constructive and computable mathematics, in T. Grubba, P. Hertling, H. Tsuiki, and Klaus Weihrauch, (eds.) CCA 2005 - Second International Conference on Computability and Complexity in Analysis, August 25-29,2005, Kyoto, Japan, ser. Informatik Berichte, , vol. 326-7/2005. FernUniversität Hagen, Germany, 2005, pp. 378–379. (pdf)

A useful review is in section 4 of

• Ingo Battenfeld, Matthias Schröder, Alex Simpson, A convenient category of domains, in L. Cardelli, M. Fiore and G. Winskel (eds.), Computation, Meaning and Logic, Articles dedicated to Gordon Plotkin Electronic Notes in Computer Science, 34 pp., to appear, 2007 pdf

Textbooks include

• Klaus Weihrauch, Computable Analysis. Berlin, Springer, 2000

• Jaap van Oosten, Realizability: an introduction to its categorical side, Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008 (preface pdf)

Concrete examples with an eye towards applications in computable physics are discussed in section 2 of

• Klaus Weihrauch, Ning Zhong, Is wave propagation computable or can wave computers beat the Turing machine?, Proc. of the London Math. Soc. (3) 85 (2002) (web)

$\,$

$\,$

$\,$

$\,$

$\,$

$\,$

$\,$

$\,$