nLab Baire space of sequences

Redirected from "Baire space (computability)".
Contents

This entry is about the Baire space of sequences of natural numbers. For another concept of the same name in topology proper, see at Baire space.

Contents

Idea

In the study of computability, descriptive set theory, etc, by Baire space is meant the topological space \mathbb{N}^{\mathbb{N}} of infinite sequences of natural numbers equipped with the product topology.

The continuous functions from Baire space to itself serve the role of computable functions in computable analysis. See at computable function (analysis).

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

References

Lecture notes include

  • Andrej Bauer, page 5 and section 5.3.1 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)

Textbook accounts include

  • Klaus Weihrauch, section 2.3 of Computable Analysis Berlin: Springer, 2000

Last revised on June 11, 2020 at 14:50:18. See the history of this page for a list of all contributions to it.