Computability on the probability measures on the Borel sets of the unit interval
Computability on the probability measures on the Borel sets of the unit interval
复制标题
单位区间 Borel 集概率测度的可计算性
DOI：
10.1007/3-540-63165-8_174
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
K. Weihrauch
中科院分区：
文献类型：
--
作者：
K. Weihrauch
虽然许多可数集合上的可计算性理论已经很好地建立起来，并且对于实数上的可计算性应用了几个（相互不等价的）定义，但对于大多数其他不可数集合，特别是度量，到目前为止还没有被普遍接受的可计算性概念。在这篇论文中，我们引入了单位区间[0；1]。它的主要目的是证明可计算性的概念不仅仅是一个特别的定义，而是具有非常自然的属性。虽然定义和许多结果当然可以转移到更一般的度量空间，但为了保持技术细节的简单和集中在中心思想上，我们限制了我们的注意力。特别地，我们证明了简单的明显要求排除了许多相似的定义，定义导致预期的可计算结果，还有其他自然定义诱导相同的可计算理论，并且该理论顺利嵌入经典测量理论。作为背景，我们考虑TTE，即Type 2 Theory of effectiveness [KW84， KW85]，它为非常现实的可计算性定义提供了一个框架。在这种方法中，图灵机明确地在有限和无限符号序列上定义了可计算性，并通过符号和表示在其他集合上定义了可计算性。规范表示来源于信息结构[Wei97]。我们引入了一个标准的表示，通过一些自然的信息结构，这些信息结构是由某个拓扑τ on1的子基σ（原子性质）和σ的标准符号定义的。虽然对δm的一些修改乍一看似乎违反了简单而明显的要求，但δm有几个非常自然的性质，因此应该引出一个重要的可计算性理论。测度上许多有趣的函数是可计算的，特别是线性组合、连续函数的积分和任何由可计算的具有概率的迭代函数系统定义的变换。引入了一些其他的自然表示，其中包括与哈钦森度规相关的柯西表示，并证明与δm等效。作为推论，δ的最终拓扑τ是众所周知的弱拓扑。
While computability theory on many countable sets is well established and for computability on the real numbers several (mutually non-equivalent) definitions are applied, for most other uncountable sets, in particular for measures, no generally accepted computability concepts at all ha,ve been available until now. In this contribution we introduce computability on the setMof probability measures on the Borel subsets of the unit interval [0; 1]. Its main purpose is to demonstrate that this concept of computability is not merely an ad hoc definition but has very natural properties. Although the definitions and many results can of course be transferred to more general spaces of measures, we restrict our attention toMin order to keep the technical details simple and concentrate on the central ideas. In particular, we show that simple obvious reqirements exclude a number of similar definitions, that the definition leads to the expected computability results, that there are other natural definitions inducing the same computability theory and that the theory is embedded smoothly into classical measure theory. As background we consider TTE, Type 2 Theory of Effectivity [KW84, KW85], which provides a frame for very realistic computability definitions. In this approach, computability is defined on finite and infinite sequences of symbols explicitly by Turing machines and on other sets by means of notations and representations. Canonical representations are derived from information structures [Wei97]. We introduce a standard representationvia some natural information structure defined by a subbaseσ(the atomic properties) of some topologyτonMand a standard notation ofσ. While several modifications ofδmsuggesting themselves at first glance, violate simple and obvious requirements,δmhas several very natural properties and hence should induce an important computability theory. Many interesting functions on measures turn out to be computable, in particular linear combination, integration of continuous functions and any transformation defined by a computable iterated function system with probabilities. Some other natural representations ofMare introduced, among them a Cauchy representation associated with the Hutchinson metric, and proved to be equivalent toδm. As a corollary, the final topologyτofδmis the well known weak topology onM.