Notions of Probabilistic Computability on Represented Spaces
Notions of Probabilistic Computability on Represented Spaces
复制标题
表示空间上的概率可计算性概念
DOI：
10.1016/j.entcs.2008.03.013
复制
发表时间：
2008
影响因子：
--
通讯作者：
Volker Bosserhoff
中科院分区：
文献类型：
--
作者：
Volker Bosserhoff
我们定义和比较几个概率减弱概念的可计算性映射表示空间（配备了措施或外措施）到有效的度量空间。因此，我们推广了Ko [Ko，K.-一、“真实的函数的复杂性理论”，Birkhäuser，Boston，1991]和帕克[帕克，M.W.，Rn中的不可判定性：Riddled Basins，KAM Tori和太阳系的稳定性，科学哲学70（2003），pp。359-382;帕克，M.W.，Three concepts of decidability for general subsets of uncountable spaces，Theoretical Computer Science 351（2006），pp. 2-13]，并进一步介绍了新的概念，可计算性的意思。一些结果采用可计算测度的概念，该概念起源于Weihrauch [Weihrauch，K.，单位区间Borel集上概率测度的可计算性，Theoretical Computer Science 219（1999），pp. 421-437]和Schröder [Schröder，M.，概率测度的可接受表示，理论计算机科学电子笔记167（2007），pp。61-78]。在著名的表示定理的精神，我们建立之间的依赖关系的削弱的可计算性概念和映射的经典性质。最后，我们提出了一些积极的结果，度量空间上的向量值积分的可计算性，并讨论了与我们的定义所产生的某些可测性问题。
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,” Birkhäuser, Boston, 1991] and Parker [Parker, M.W., Undecidability inRn: 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.