Notions of Probabilistic Computability on Represented Spaces

We define and compare several probabilistically weakened notions of computability for mappings from represented spaces (that are equipped with a measure or outer measure) into effective metric spaces. We thereby generalize definitions by Ko [Ko, K.-I., ''Complexity Theory of Real Functions,'' Birkhauser, Boston, 1991] and Parker [Parker, M.W., Undecidability inR^n: Riddled basins, the KAM tori, and the stability of the solar system, Philosophy of Science 70 (2003), pp. 359-382; Parker, M.W., Three concepts of decidability for general subsets of uncountable spaces, Theoretical Computer Science 351 (2006), pp. 2-13], and furthermore introduce the new notion of computability in the mean. Some results employ a notion of computable measure that originates in definitions by Weihrauch [Weihrauch, K., Computability on the probability measures on the Borel sets of the unit interval., Theoretical Computer Science 219 (1999), pp. 421-437] and Schroder [Schroder, M., Admissible representations of probability measures, Electronic Notes in Theoretical Computer Science 167 (2007), pp. 61-78]. In the spirit of the well-known Representation Theorem, we establish dependencies between the weakened computability notions and classical properties of mappings. We finally present some positive results on the computability of vector-valued integration on metric spaces, and discuss certain measurability issues arising in connection with our definitions.

• Publication year

  2008

• Venue

  International Conference on Computability and Complexity in Analysis

• Publication date

  2008-03-01

• Fields of study

  Mathematics, Philosophy, Computer Science

• Identifiers
  DOI 10.1016/j.entcs.2008.03.013
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Are unbounded linear operators computable on the average for Gaussian measures?

  2008cited by this paper
• Admissible representations for probability measures

  2007cited by this paper
• Computable metrization

  2007cited by this paper
• Three concepts of decidability for general subsets of uncountable spaces

  2006influential reference
• Finite approximation of measure and integration

  2006cited by this paper
• Representing probability measures using probabilistic processes

  2006cited by this paper
• Computability of measurable sets via effective topologies

  2006cited by this paper
• Computable Analysis

  2005influential reference
• A Computable Version of the Daniell-Stone Theorem on Integration and Linear Functionals

  2005cited by this paper
• Computability of measurable sets via effective metrics

  2005cited by this paper
• Undecidable long-term behavior in classical physics: foundations, results and interpretation

  2005cited by this paper
• Uniform test of algorithmic randomness over a general space

  2003cited by this paper
• Undecidability in Rn: Riddled Basins, the KAM Tori, and the Stability of the Solar System

  2003cited by this paper
• Effectivity in Spaces with Admissible Multirepresentations

  2002cited by this paper
• Extended admissibility

  2002cited by this paper
• Effectivity in Spaces with Admissible Multirepresentations

  2002cited by this paper
• Computability on Random Variables

  1999cited by this paper
• Complexity and information

  1999influential reference
• Computability on the Probability Measureson the Borel Sets of the Unit Interval

  1997influential reference
• Domain theory and integration

  1994cited by this paper
• Dynamical Systems, Measures and Fractals via Domain Theory

  1993cited by this paper
• Complexity theory of real functions

  1992cited by this paper
• Information-Based Complexity

  1988cited by this paper
• Classical descriptive set theory

  1987cited by this paper
• Probability Distributions on Banach Spaces

  1987cited by this paper
• The Stability of the Solar System

  1961cited by this paper
• On the Solvability of Ill-Posed Problems in two Models of Computation

  year unknowninfluential reference

• Computable Measure Theory and Algorithmic Randomness

  2021influential citation
• Randomized Computation of Continuous Data: Is Brownian Motion Computable?

  2019cites this paper
• On the close interaction between algorithmic randomness and constructive/computable measure theory

  2018cites this paper
• Computability on measurable functions

  2016cites this paper
• The Twelfth International Conference on Computability and Complexity in Analysis

  2015cites this paper
• On computability and disintegration

  2015influential citation
• Average-Case Bit-Complexity Theory of Real Functions

  2015cites this paper
• Algorithmic randomness over general spaces

  2014cites this paper
• Representations of measurable sets in computable measure theory

  2014cites this paper
• Topics in algorithmic randomness and computable analysis

  2013cites this paper
• ALGORITHMIC RANDOMNESS, MARTINGALES AND DIFFERENTIABILITY

  2013cites this paper
• L1-Computability, Layerwise Computability and Solovay Reducibility

  2013cites this paper
• Probabilistic computability and choice

  2013cites this paper
• Computable randomness and betting for computable probability spaces

  2012influential citation
• Computability and analysis: the legacy of Alan Turing

  2012cites this paper
• Characterization of Kurtz Randomness by a Differentiation Theorem

  2012cites this paper
• Computability, inference and modeling in probabilistic programming

  2011cites this paper
• On the Computability of Conditional Probability

  2010cites this paper
• Computable exchangeable sequences have computable de Finetti measures

  2009cites this paper
• Computable de Finetti measures

  2009cites this paper
• Computable Exchangeable Sequences Have Computable de Finetti Measures

  2009cites this paper
• An Application of Martin-Löf Randomness to Effective Probability Theory

  2009cites this paper
• Representing Measurement Results

  2009influential citation
• Effective Symbolic Dynamics

  2008cites this paper
• Are unbounded linear operators computable on the average for Gaussian measures?

  2008cites this paper
• Metric structures and probabilistic computation

  2008cites this paper
• Effective symbolic dynamics, random points, statistical behavior, complexity and entropy

  2007cites this paper
• Antrag auf Förderung einer wissenschaftlichen Zusammenarbeit zwischen Deutschland und Großbritannien

  year unknowncites this paper