JUCS - Journal of Universal Computer Science 14(6): 956-995, doi: 10.3217/jucs-014-06-0956
Notions of Probabilistic Computability on Represented Spaces
expand article infoVolker Bosserhoff
‡ Universität der Bundeswehr, Munich, Germany
Open Access
Abstract
We define and compare several probabilistic notions of computability for mappings from represented spaces (that are equipped with a measure or outer measure) into computable metric spaces. We thereby generalize definitions by [Ko 1991] and Parker (see [Parker 2003, Parker 2005, Parker 2006]), 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 1999] and [Schröder 2007]. In the spirit of the well-known Representation Theorem (see [Weihrauch 2000]), we establish dependencies between the probabilistic computability notions and classical properties of mappings. We furthermore present various results on the computability of vector-valued integration, composition of mappings, and images of measures. Finally, we discuss certain measurability issues arising in connection with our definitions.
Keywords
computable analysis, computable measures, probabilistic computation