Notions of Probabilistic Computability on Represented Spaces

Abstract: We define and compare several probabilistic notions of computability for mappings from represented spaces (that are equipped with a measure or outer mea- sure) 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 com- putable measure that originates in definitions by [Weihrauch 1999] and [Schr¨oder 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.