Randomness for non-computable measures
Randomness for non-computable measures
复制标题
不可计算测量的随机性
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Joseph S. Miller
中科院分区：
文献类型：
--
作者：
A. Day;Joseph S. Miller
已经采取了不同的方法来定义不可计算的概率测量的随机性。我们将解释Reimann和Slaman的方法，沿着Levin首先介绍并被Gacs，Hoyrup和Rojas使用的统一测试方法。我们将证明这些方法在本质上是等价的。在澄清了对于不可计算的概率测度来说随机意味着什么之后，我们将注意力转向莱文的中性测度，对于它所有的序列都是随机的。我们证明了每一个PA度计算一个中性测度。我们还表明，一个中立的措施没有至少图灵度表示和解释为什么框架的连续度（子结构的枚举度研究米勒）可以用来确定计算复杂性的中立措施。这使我们能够证明，中性测度下的图灵理想正是斯科特理想。由于X ∈ 2是中性测度μ的原子当且仅当它可从μ的（每个表示）计算，我们对中性测度的原子的可能集合有了完整的理解。一个简单的推论是，每个中性测度都有一个马丁-洛夫随机原子。1.设X是Cantor空间的元素，μ是Cantor空间上的Borel概率测度.如果X相对于μ是随机的，这意味着什么？在μ是勒贝格测度的情况下，μ随机性理论就发展得很好了（关于这个问题的最近论文，读者可以参考唐尼、赫希费尔特和奈斯[2，13]）。事实上，如果μ是一个可计算的测度，那么莱文的早期工作表明，μ-随机性本质上可以被视为勒贝格测度随机性的一个变体[10]。这就留下了一个问题，如果μ是不可计算的，如何定义随机性。我们将证明，对于不可计算的μ，先前用于定义μ-随机性的两种方法是等价的。稍后，在定理4.12中，我们将用枚举度给出μ-随机性的另一个刻画。最后一次编译：2011年9月8日最后一次更改以下日期：2010年11月22日。2010年数学学科分类。小学03 D32;中学68 Q30，03 D30。第二作者由国家科学基金会资助，资助额为DMS-0945187和DMS-0946325，后者是药物随机性重点研究组的一部分。
Different approaches have been taken to defining randomness for non-computable probability measures. We will explain the approach of Reimann and Slaman, along with the uniform test approach first introduced by Levin and also used by Gacs, Hoyrup and Rojas. We will show that these approaches are fundamentally equivalent. Having clarified what it means to be random for a non-computable probability measure, we turn our attention to Levin’s neutral measures, for which all sequences are random. We show that every PA degree computes a neutral measure. We also show that a neutral measure has no least Turing degree representation and explain why the framework of the continuous degrees (a substructure of the enumeration degrees studied by Miller) can be used to determine the computational complexity of neutral measures. This allows us to show that the Turing ideals below neutral measures are exactly the Scott ideals. Since X ∈ 2 is an atom of a neutral measure μ if and only if it is computable from (every representation of) μ, we have a complete understanding of the possible sets of atoms of a neutral measure. One simple consequence is that every neutral measure has a Martin-Lof random atom. 1. Defining randomness Let X be an element of Cantor space and μ a Borel probability measure on Cantor space. What should it mean for X to be random with respect to μ? In the case that μ is the Lebesgue measure, then the theory of μrandomness is well developed (for recent treatises on the subject the reader is referred to Downey and Hirschfeldt, and Nies [2, 13]). In fact if μ is a computable measure, then early work of Levin showed that μ-randomness can be seen as essentially a variant on randomness for Lebesgue measure [10]. This leaves the question of how to define randomness if μ is non-computable. We will show that the two approaches that have previously been used to define μ-randomness, for non-computable μ, are equivalent. Later, in Theorem 4.12, we will provide another characterization of μ-randomness using the enumeration degrees. Last compilation: September 8, 2011 Last time the following date was changed: November 22, 2010. 2010 Mathematics Subject Classification. Primary 03D32; Secondary 68Q30, 03D30. The second author was supported by the National Science Foundation under grants DMS-0945187 and DMS-0946325, the latter being part of a Focused Research Group in Algorithmic Randomness.