nLab
computable function (analysis)

Context

Analysis

Constructivism, Realizability, Computability

Contents

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 0T_0-topological space XX is a presentation of it as a quotient space of a subspace BB 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 BXB \to X has the right lifting property against continuous functions out of other subspaces BB' of Baire space.

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

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

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

Properties

General

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

Relation to function realizability

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

Relation to topology

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

Examples

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

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 AdmRepAdmRep, and due to cartesian clossure above, for any XAdmRepX \in AdmRep also its lattice of closed subspaces is in AdmRepAdmRep.

computability

type I computabilitytype II computability
typical domainnatural numbers \mathbb{N}Baire space of infinite sequences 𝔹= \mathbb{B} = \mathbb{N}^{\mathbb{N}}
computable functionspartial recursive functioncomputable function (analysis)
type of computable mathematicsrecursive mathematicscomputable analysis, Type Two Theory of Effectivity
type of realizabilitynumber realizabilityfunction realizability
partial combinatory algebraKleene's first partial combinatory algebraKleene's second partial combinatory algebra

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

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

See also

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)

\,

\,

\,

\,

\,

\,

\,

\,

Last revised on March 3, 2014 at 23:47:53. See the history of this page for a list of all contributions to it.