可计算概率测度及其等价关系研究

理论计算机科学电子笔记167（2007）117-130www.elsevier.com/locate/entcs可计算概率测度Laurent Bienvenu洛朗·比恩韦努1，2基础信息管理系统法国马赛Wolfgang Merkle沃尔夫冈·梅克尔1，3InstitutfuürInforormatik，Ruprecht-Karls-Universitüat Heidelberg，Germany摘要任何关于任意可计算概率测度定义的有效随机性的概念，都规范地在这些测度上导出一个等价关系，如果两个测度各自的随机元素类重合，则它们被认为是等价的 在Bienvenu [1]工作的基础上，我们确定了由Martin-Lüofr andom n ess，comput abler and omn ess，Schn orr random n ess，andnweakrand omn ess导出的等价关系与概率测度的等价性和相容性关系之间的所有含义，只是我们不知道当两个可计算概率测度各自的弱随机性概念重合时它们是否需要等价.关键字：计算可预测性测度，Martin-Léofrandomness，计算可预测性测度，Schnorr随机性，弱随机性，概率测度的等价性，概率测度的一致性.1我们要感谢Alexander Shen和一位匿名裁判提供的有益的意见和建议2Email：laurent.bienven u@ lif. 联合国日内瓦办事处-m rs. fr3 电子邮件地址：merkle@math.uni-heidelberg.de1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.08.010118L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）1171引言自1920年冯·米塞斯的工作以来，人们提出了几个关于0和1的无限序列的随机性概念迄今为止，最重要和最具代表性的知识是随机项的Martin-L？n？n一方面，有各种各样的随机性概念，它们是根据选择规则定义的另一方面，也有一些概念可以用博彩策略来定义，如马丁-洛夫随机数或可计算的随机性。随机性和随机性的概念通常与康托空间上的一致测度有关。事实上，随机性的概念依赖于大数定律中所断言的频率收敛，不能扩展到任意或甚至任意可计算的概率测度。与此相反，根据投注策略定义的随机性概念通常自然地扩展到任意可计算的概率度量。因此，我们将重点讨论可以用鞅定义的标准随机性 这 些 概 念 是 马 丁 -L？ 随 机 性 ，可 计 算随机 性（ alsocalledrecursiverandomness），Schnorr随机性和弱随机性（也称为Kurtz随机性）。随机性和随机性的各种概念之间的关系已被广泛研究的统一措施的背景下。在续集中，我们追求一种不同的方法，因为我们比较随机性的概念与他们的行为时，潜在的概率测量是不同的。在经典概率论中，如果两个概率测度具有相同的零集，或者换句话说，如果它们具有相同的测度1的集合，这意味着它们在某种意义上非常相似，则称它们是等价的由于定义随机性的概念意味着为每个可计算测度μ选择一个特定的μ-测度1集合，并称其元素为随机的，因此很自然地定义一个等价关系，即如果两个测度具有相同的随机元素，则它们是等价的。在本文中，l我们investi-门到问题之间的关系，从各种随机性概念得到的等价关系更确切地说，我们要问的是，对于哪对随机性概念，第一个概念的等价意味着第二个概念的等价L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）117119∈∈∼2定义和概念2.1康托空间在下文中，我们将只处理康托空间中的随机性（尽管有效随机性可以扩展到更一般的拓扑空间，例如参见[3]）。康托空间，我们用2ω表示，是无限二元序列的集合。它被规范地赋予了乘积拓扑，其基础由以下形式的开集给出：联合2ω ={α∈ 2ω：u<$α}，其中u∈2<$（2<$是有限二元序列的集合，而<$是前缀关系，定义在2ω< $2<$）。如果α∈22ω，则αTn表示由α的前n位组成的有限字。如果X <$2ω，则X表示X的补数是2ω。根据Caratheodory的扩张定理，每个函数m定义在2 ω的子集上，并在[0，1]中取值，使得m（2 ω）= 1，并且对于所有u 2 <$m（u. 2 ω）= m（u0. 2 ω）+m（u 1. 2ω），导出了2ω上的唯一概率测度。因此，从现在开始，我们可以识别一个概率测度，它限制于u形式的开集。2 ω，我们将μ（u.2ω）通过μ（u）。2 ω上的典范测度是勒贝格测度λ，定义为λ（u）= 2-|u|对于所有的U2 S。此外，由于它们是我们将考虑的唯一测度，我们将讨论by定义2.1测度μ是可计算的，如果存在一个可计算函数f：2 <$× N → Q，使得对于所有的（u，n），|f（u，n）− μ（u）|≤ 2 −n。我们只考虑可计算测度的原因是，我们考虑的随机性概念，最初定义为均匀测度，可以以非常自然的方式扩展到可计算测度，而在不可计算测度的情况下没有这样完全自然的扩展在经典概率论中，关于概率测度有两个主要的关系定义2.2两个概率测度μ和ν是等价的（用μ ν表示），如果它们有相同的零集。两个概率测度μ和ν是相容的，如果不存在测度μ-测度1和ν-测度0的集合。2.2鞅继Ville [10]之后，我们现在引入鞅的概念。它可以被看作是描述一个玩家的资本，他试图猜测一个游戏的细节120L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）117∞→{∞}∈μω在有限的二进制序列中，在他们的价值上下注（永远不会超过他的当前当然，游戏的公平性取决于基本的衡量标准。定义2.3设μ是一个测度。 μ-鞅是一个函数d：2 <$R++使得对于所有的u 2 <$：d（u）μ（u）= d（u 0）μ（u 0）+d（u 1）μ（u 1）（约定+. 0 = 0）。一个鞅d被称为赋范的，如果d（ε）= 1（ε是空字）。如果存在一个可计算函数f：2<$×N→Q使得对于所有（u，n），|≤2 − n。|≤ 2 −n.下面的引理表明测度和鞅之间存在精确的对应关系引理2.4对于每一个测度（分别为可计算测度）μ，赋范μ-鞅（分别为可计算的赋范μ-鞅）恰好是形式为λ的函数，其中λ是测度（分别为可计算的度量）。(The证明是直接的）。下一个定理是关于鞅的一个著名的结果，它将在续集中有很大的用处。定理2.5（Ville [10]）设μ是测度，d是μ-鞅. 对所有k∈R+，μ{α∈ 2 ω：supnd（αTn）≥k}≤ 1/k.2.3Martin-Lüofrandomness定义2.6假设V是可计算的不可计算的（例如，）如果存在一个可计算可积A<$2<$使得V =u∈A u。2ω。C. e.的集合{Vn}n∈N开集是可计算的，如果存在可计算函数（n，k）∈N2→un，k∈2使得对所有n∈N，Vn =k∈Nun，k. 二、μ-Martin-L？of检验是一个可计算的c.e. opensets{Vn}n∈N使得对于所有n，μ（Vn）≤2−n。称α∈2ω通过test{Vn}的μ-Martin-L？}n∈N 如果α∈/n V，n.如果α∈2ω通过所有的Μ -Martin-Lf检验，则称它是μ -Martin-LF随机的（简称μ-ML随机）. 用μ MLR表示μ-ML-随机无穷序列集.L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）117121V∈∞→≥注释2.7 ML随机性的概念保持不变，如果我们定义一个Martin-L？of检验为c.e的可计算集合。o∈n设{Vn}n满足μ（n）被某个可计算实值函数f（n）所约束，该函数随着n趋于无穷而递减并趋于0。Martin-L？ofrandommnes可以在martingales的框架内进行（见[2]），但我们不需要这样做。2.4可计算随机性C. P.Schnorr在[8]和[9]中提出了两个较弱但在某种意义上更有效的有效随机性的替代概念。它们现在分别被称为可计算随机性和Schnorr随机性。可计算随机性是基于所谓的不可预测性范式：如果没有可计算策略/鞅成功，则序列是随机的。定义2.8设μ是一个可计算的概率测度。 序列α 2 ω是μ-可计算随机的，如果不存在可计算μ-鞅d使得supn d（αTn）=+.我们用μCR表示μ-可计算随机序列的集合。注2.9如果我们用lim nd（α Tn）=+ ∞代替优胜条件sup nd（αTn）=+ ∞，可计算随机性的概念保持不变。2.5Schnorr随机性Schnorr随机性甚至比可计算随机性更弱。一个序列α不是Schnorr随机的，如果存在一个可计算的策略/鞅，它不仅在它上面成功，而且以合理的速度成功：定义2.10阶是一个函数g：N N，它是非减的且无界的。序列α是μ-SCHNORR随机的，如果不存在可计算的μ-鞅d和可计算的阶g使得对无穷多个n，d（αTn）g（n）.我们用μSR表示μ-Schnorr随机序列的集合这一定义可以改写如下：命题2.11序列α是μ-Schnorr随机序列，如果不存在可计算μ-鞅d和可计算函数f：N→N使得对无穷多个n，d（αTf（n））≥n。122L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）117∈2.6弱随机性弱随机性是由S. Kurtz [4]（因此也被称为Kurtz randomness）是Martin-Lüofrandomness的对偶。如果需要一个随机序列来避免测度为0的所有有效集，我们要求它属于测度为1的所有有效集定义2.12序列α是μ-弱随机的，如果它属于所有c. e. μ-测度1的开集U。我们用μWR表示μ-弱随机序列集。弱随机性可以用鞅来刻画，特别是Schnorr随机性蕴含弱随机性。命题2.13（Wang [11]）序列α 2 ω是μ-弱随机的，如果不存在可计算μ-鞅d和可计算阶g使得对所有n，d（α Tn）≥g（n）。我们用μWR表示μ-弱随机序列集。3等价关系本文的其余部分将致力于证明以下分类：定理3.1对于所有可计算的概率测度μ和ν，下列含义成立：μCR=νCR↓μMLR=νMLR μSR=νSR\（μ∼ν↓μWR=νWR↓μ，ν一致我们将表明，没有其他含义之间的这些等价关系，除了一个可能的平等之间的经典等价和WR-等价（虽然我们猜想这是不是这样），我们离开作为一个开放的问题。L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）117123一u∈uuiW.2W.2一一N注3.2值得注意的是，上述不同等价关系之间的含义与随机性基本概念之间的含义完全无关。第一个含义（如果两个可计算测度具有相同的可计算随机元素，则它们具有相同的随机元素的Martin-L？）在[6]中得到了证明（另见[1]）。我们会证明所有其他人。命题3.3设μ和ν是两个可计算测度。(a) 如果μMLR=νMLR，则μν(b) 如果μSR=νSR，则μπν为了证明这一点，我们需要以下引理：引理3.4设A = u1，..，u N是一个有限的无前缀的词集（即没有一个是另一个的前缀）。 对于所有的可计算测度μ，存在一个赋范的μ-鞅dμ，从A等价可计算，使得对所有1≤i≤N：. A.A.Σ−1dμ（ui）=Ni=1 μ（u i）。证据对于所有的u ~ 2 π，设d μ是一个赋范μ-鞅，它试图在u上赢得尽可能多的东西（因此在所有其他长度的字上失去一切|u|）. 形式上：⎪dμ（w）=⎧μ（w）−1ifw<$u⎨μ（u）−1如果我们⎪⎪0否则Q令dμ.中国=1=1μ（ui）−1i=1 μ（u i）d μ.dμ是一个鞅，鞅的加权和，并且通过构造是赋范的并且满足所需的性质。证据[of命题3.3]我们同时证明了（a）和（b）。假设μ和ν不等价，即例如，存在一个集合X，使得μ（X）= 0且ν（X）>0。设q是有理数，使得ν（X）>q >0。定义一个测度：μ（X）= inf{μ（W）：Wopen}。 因此，对于所有k∈N，存在一个开集W <$X，使得μ（W）2−2k（当然还有ν（W）>q）。< 自从U。2ω是Cantor空间拓扑的基存在一组有限的（无前缀的）单词w1，...，w N使得w i. 2ω-ω-W，则v（Ni=1i）≥q（当然μ（Ni=1ii=1ω）2−2k）。<⎩ω124L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）117我我我{||≤≤}∈ZQ∼K我1NkKi=1我K我我1Nki=1我i=1我NkNkNk因此，对于一个给定的，一个可执行的查找（prefix-free）有限值，单词A = uk，.， u k使得，设置V =u。2ω，我们有ν（V）≥q且μ（Vk）≤2−2k（它可以枚举有限个词集，直到我们找到一个满足这些特性的人，最终会通过上述方式实现讨论）。 则令Z=nk>nVk={α：α∈ Vk，对于无穷多个k}.设v（Z）≥q，则Z为v-MartinLüof随机序列 我们现在证明Z <$μSR=<$。根据上面的引理，对于所有k，存在一个赋范μ-鞅dk=dμ使得对于所有uk：Akidk（uk）≥22k. 接下来，设d=k∈N 2−kdk。 它是一个赋范μ-鞅这个世界上有这么多的人。weig htsequalto1，ofno. r medμ-martingal ess. It对于所有W，是可计算的。d（w）−Mk=1 2−kdk（w）。≤2−mμ（w）−1（因此可以通过取足够大的m来近似d（w），误差界为可计算的m和趋于0的m趋于无穷）。设f是定义为f（k）= max的函数英国：1我N K。 对于所有α有很多的uk是α的前缀。通过构造d，对于所有k和所有i≤Nk，我们有d（uk）≥2−kdk（uk）≥2k。所以对于无穷多个n：d（αTf（n））≥2n. 这通过命题2.11断言α不是μ-Schnorr随机我们已经证明了ZνMLR/=和ZμSR=，从而完成了证明。命题3.5设μ和ν是两个可计算测度。 如果μν，则μWR = νWR。证据这是微不足道的。如果序列α是ν-弱随机的而不是μ-弱随机的，则这意味着存在μ - m ∈ 1的有效开集U，其中α∈/U。其中α是ν-弱随机的，U有一个小于1的ν-测度因此，U证明μ和ν不等价。命题3.6设μ和ν是两个可计算测度。 如果μWR = νWR则μ和ν是一致的。证据假设μ和ν不相容，即存在一个集合X使得ν（X）= 1且μ（X）= 0。我们认为，类似于命题3.3的证明，对于所有k∈N，我们可以有效地找到一个有限的无前缀的词uk，.，u k使得μ（u . 2 ω）≤ 2 −k−2且ν（u . 2ω）≥1 −2−k。那么，U=Nkki=1英国2ω是一个等价开集，ν-测度为1（因此包含所有的ν-弱随机序列），且μ-测度小于1/ 2(and因此不包含所有的μ-弱随机序列，它们构成μ-测度1）的集合。Q我们已经证明了定理3.1的所有含义。我们现在开始一项更微妙的任务，即表明在我们所研究的等价关系之间没有其他有效的蕴涵（除了提到的可能的例外L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）117125{∞}Kμ（α<$n）ν/μμ（α<$n）ν/μ+ν/μμν/μν/μμ/νμ/νν/μ∞μ/ν∞μ/νμ/νμ/νμ/νν/μKμ/νKK以上）。为了构建反例，以下数量将发挥关键作用。定义3.7设μ和ν是两个可计算测度，kR++。我们设定Lν/μ={α∈ 2：supn∈Nν（αTn）μ（αTn）≥k}(with下面的约定：如果μ（αTn）=ν（αTn）= 0，ν（α<$n）= 1，如果μ（αTn）= 0且ν（αTn）>0，ν（α<$n）=+∞）由引理2.4和定理2.5，我们得到：推论3.8对于所有可计算测度μ，ν：L∞μ CR= 我是说-特别地，这意味着thatL∞10μ MLR=100μM。对于每一个k∈R：Kν/μ）≤1/k（因此μ（L∞）=0）。证据ν是μ-鞅（根据引理2.4），L∞恰好是成功的序列。 因此，L ∞ μCR= 的事实Kν/μ）≤1/k是定理2.5的直接结果。Q下一个命题说明了我们所研究的一些等价关系与L ∞有关 .命题3.9对于每对（μ，ν）可计算测度：(a) μπνi πμ（L∞ ）=ν（L∞）= 0，(b) μMLR=νMLRiL∞μMLR=Lν/μvMLR=(c) μCR=νCRiL∞μCR=Lν/μvCR=证据对于（a）、（b）和（c），现在让我们证明“如果”的我们将使用以下事实：对于每个开集U <$2ω和所有测度μ和ν：μ（U <$Lk）≤k ν（U）(this是L k定义的一个平凡的结果 ）.(a) 设μ（L∞ ）=ν（L∞ ）= 0，且设X <$2ω使得ν（X）= 0。设k∈N. 设U是一个开集，使得X <$U且ν（U）≤1/k2. 然后又道：μ（X）≤μ（U）≤μ（U Lμ/ν）+μ（U Lk）≤μ（Lμ/ν）+k ν（U）≤μ（Lμ/v）+1/kμ（Lμ（Lω126L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）117μ/νμ/νμ/ν∞α∈LK2ωμ/ν∞μ（α<$n）≥sup2μ/λλ/μ2{∈}k ν（α<$n）μ/ν≥这对于所有k都是真的，并且由于假设μ（L∞）= 0（这是等价于limk→+∞μ（Lk）= 0），这证明了μ（X）= 0.(b) 假设L∞μMLR=Lν/μvMLR= Letα∈/VMLR。 如果∞μ/ν ，thenbyassumptionα∈/μMLR，我们完成了。 如果不是那有exi stsk∈R+s。t. α∈/Lμ/ν . Let{Un}n∈Nbeaν-Martin-Lo？f检验标准差α∈nUn. 设{un，i：（n，i）∈N}是有限元对于所有n，Un是{un，i2ω：i∈N}的不交并。对所有nVn=i{un，i 2：i∈N，μ（un，i）s0，则存在ss0suchhati，ws不是fβ的前缀，并且hus，对于所有n >3s0，d（βTn）=d（βT3s0）.现在让我们考虑μ=λ d。 通过上述讨论，L ∞L ∞ ={α}。此外，对于无穷多个s，P=2.11，α∈/μ SR.λ（α<$3s）μ（α<$3s） s。因此，根据引理2.4和Q在我们将上述命题应用于反例的构造之前，我们需要下面的重要定理。定理3.11（Nies，Stephan和Terwijn [7]）设α∈ 2 ω. 以下内容等同：(i) α具有高图灵度，(ii) α的图灵度中存在β使得β∈λCR\λM LR，(iii) α的图灵度中存在β使得β ∈ λSR\λCR.我们现在准备证明：命题3.12（a）存在一个可计算测度μ，使得λ<$μ但λM LRμMLR，λCR/= μCR，λSR/= μSR。(b) 存在可计算测度μ，使得λM LR=μMLR，λCRμ CR(c) 存在可计算测度μ，使得λCR=μCR且λSR/=μSR。证据（a）根据命题3.10，设μ是一个可计算的测度，使得∞ ∞Lμ/λ=λ，Lλ/μ={Ω}，Ω∈/μ SR. 这里Ω表示Chaitinber，其已知为left-r. e。(i.e.集合{q∈Q：qΩ}是递归可积的，这特别意味着Ω是Δ0）。由于λ（{Ω}）= 0，根据命题3.9，我们有λ<$μ。此外，由于Ω∈λM LR<$λCR<$λSR，且Ω∈/μ SR，则λMLRμ MLR，λ CR/=μ CR，λ SR/=μSR.L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）1171292μ/λ∞2μ/λ∞μ（α<$n）μ/λλ/μμ（Ω<$n）√慢慢地(b) 利用定理3.11，设α是Δ0序列，使得α ∈ λCR\λM LR.根据命题3.10，存在一个可计算测度μ使得L∞=μ，Lλ/μ={α}，α∈/μ SR. 第三步。9，其中λMLR=μ MLR（sinc e α∈/λMLR）和dλ CR/=μ CR（sinc e α∈λ CR\μ CR）。(c) 利用定理3.11，设α是Δ0序列，使得α∈λSR\λCR.根据命题3.10，存在一个可计算测度μ使得L∞=μ，Lλ/μ={α}，α∈/μ SR. 第三步。9，其中λ CR=μ CR（因为α∈/λ CR）和dλ SRμ SR（sinceα∈λ SR\μ SR）。命题3.13存在一个可计算测度μ，使得λSR =μSR，λCRμCR和λM LRμMLR再一次，我们需要一个预备引理。引理3.14设μ和ν是两个可计算测度，α∈ 2 ω。 如果α∈νSR\μSR，则存在可计算阶g使得ν（α<$n）≥g（n）经常地。证据 设α∈νSR\μSR.根据引理2.4，存在一个可计算的一个可计算的阶g，使得对于无穷大，μ（α<$n）许多;许多由于α∈νSR和g是可计算的阶，对于几乎所有的n，（α<$n）ν（α<$n）（α<$n）ν（α<$n）g（n）ν（α<$n）√g（n）。因此，对于无限多的n：μ（α<$n）=μ（α<$n）μ（α<$n）≥μg（n）=g（n）。Q证据[3.13]我们将以非常类似的方式构建，命题3.10可计算测度μ使得L∞=Ω，L∞={ Ω}，但这次我们希望Ω是μ-Schnorr随机的。根据上面的引理，确保λ（Ω<$n）比任何人都慢，可计算的顺序因此，我们将再次构造一个λ-鞅d，使得limnd（ΩTn）= 0，如果β= Ω，d（βTn），确保d（ΩTn）减少Ω为左-r.e.，设{w s}s∈N是一个词序列，Ω是该序列的逐点极限，lims→+∞|w s| =+∞，|w s| ≤ 3 sfor all s，w sis a prefix of α for infinitelymany s，如果w sis a prefix of Ω，w s<$w tfor allt> s。我们还假设（直到修改Ω为有限位数）Ω在E中没有前缀（在命题3.10的证明中定义）。设F：N→N使得F（0）= 0，且对所有s > 0，若w s<$Ω，则F（s + 1）= |w s|否则F（s + 1）= F（s）。通过定义ws，对于所有s，与Ω重合的ws的初始段至少有长度≤Q130L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）117F（s）。 F比任何可计算的顺序都要慢：假设这是L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）1171312| |Lλ/μμ（Ω†3s=+∞。λ（Ω<$n）Lλ/μμ（Ω<$n）不是这样的，即存在一个可计算的阶g，使得对于无穷多个s，g（s）≤F（s）。然后，对于无穷多个s，看ws，就有可能猜出Ω的第一个g（s）位从这句话中，构造一个λ- 鞅断言Ω不是Schnorr随机的，这是一个矛盾。我们构造一个λ-鞅d，使得对于所有s，d（ΩT 3s）=F（s）−1，并且如果βf= Ω，d（βTn）最终是常数：S值s= 0。 设d（0）=d（1）= 1/ 2。S+ 1。我们定义d（u），对于每个长度为3s+1的u：• 如果u不是ws的扩张，则设d（u）=d（uT3s）• 如果u是w s的扩张且不在E中，则设d（u）= 1/|w s|• 如果u是ws的扩张，并且在E中，则以{d（v）：vT3s =uT 3s}的平均值为d（uT3s）的方式设置d（u）然后，对于满足3su 3s+1的单词u，归纳地（按长度递减的顺序）设置d（u）=d（u0）+d（u1）。最后，设μ=d λ。它仍然表明μ是所期望的。首先我们得∞μ/λ =0。我们还可以看到，={ Ω}。事实上，对于所有s，d（ΩT 3s）=F（s）−1，且当λ（Ω<$3s）=F（s）时，F的定义意味着s向上λ（Ω<$n）nμ（Ω<$n）此外，如果n3s，通过构造d，d（ΩTn）≥d（Ω T3s），因此对于所有n，μ（Ω<$n）≤F（log3（n））。 当然，F（log3（n））=o（g（n））对于所有可计算阶数g. 最后，如果βΩ，正如我们在命题3.10，补充λ（β<$n）<+∞。nμ（β<$n）为了完成证明，请注意，通过命题3.9，我们有λM LRμ MLR和μ CR/=μ CR（sinceΩ∈λMLR和Ω∈/μ CR）。但是，我们有λSR=μSR。 实际上，根据前面的引理，μSR\λSR=λ，因为∞μ/λ =λ，且λSR\μSR=λ，因为L∞={ Ω}和λ（Ω<$n）=o（g（n））对于每个可计算阶数g.Q命题3.15存在一个可计算测度μ，使得μ和λ是一致性和λWR μWR证据设δ是使得δ（{0ω}）= 1的测度（这显然是可计算的）。设μ=δ/ 2+λ/132L. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）1172。λ和μ是一致的：设X <$2ω。当0 ω∈ X时，nμ（X）=1/2+λ（X），且当0ω∈/X时，μ（X）=λ（X）. 在这两种情况下，不可能有μ（X）= 0和λ（X）=1，反之亦然。另一方面，0ω∈μ W R和0ω∈/λ W R。QL. 比恩韦努湾Merkle/Electronic Notes in Theoretical Computer Science 167（2007）117133引用[1] 比恩韦努湖可计算概率测度的构造等价关系，俄罗斯国际计算机科学研讨会，计算机科学讲义3967（2006），92[2] 唐尼河，和D. Hirschfeldt，“随机性和复杂性”，Mandarin pt，2003年。[3] Gacs，P.，“Lecture Notes on Descriptional Complexity and Randomness”，波士顿大学，1988年。[4] Kurtz，S.，[5] Martin-Lo？ f ， P. ， Thefinitio n ofrandomsequences ， InformationanddControl ， 9 （ 6 ）（1966），602-619.[6] Muchnik，An.一、A.L. Semenov，V.A. Uspensky，随机性的数学形而上学，理论计算机科学207（2）（1998），263[7] Nies ， A. ， F. Stephan ， S. Terwijn ， Randomness ， Relativization and Turing degrees ，Journal of Symbolic Logic70（2）（2005），515[8] 施诺尔角P.，一个统一的方法来定义随机序列，数学。系统理论5（1971），246-258.[9] S chnorrr，C. P. ，（1971），Springer-Verlag.[10] Ville，J.，“Etude critique de la notion de collectif”, Gauthiers-Villars, Paris,[11] Wang，Y. ，“R and dom nes s and comple x i t y“， D ok tora l diss e r t a t io n ，Ma t hema t is ch e F aku l t？t？t，Univer er s i t？t H e idel b e rg，1996.