Notions of Probabilistic Computability on Represented Spaces

Volker Bosserhoff (Universität der Bundeswehr, Germany)

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

Categories: F.1.1, F.1.2, F.4.1