Notions of Probabilistic Computability on Represented Spaces

AbstractWe 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,” Birkhäuser, Boston, 1991] and Parker [Parker, M.W., Undecidability in Rn: 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 Schröder [Schröder, 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