实数的内在计算复杂性和内在随机性的关系

36《理论计算机科学电子札记》66卷第1期（2002年）网址：http://www.elsevier.nl/locate/entcs/volume66.html17页平凡的现实罗德·G 唐尼1号惠灵顿维多利亚大学数学与计算科学学院新西兰Denis R. 赫希费尔特美国芝加哥大学数学系。而r'eNies奥克兰大学新西兰弗兰克·斯蒂芬2德国海德堡大学数学研究所摘要Solovay证明了存在不可计算实数α使得H（αTn）≤H（1n）+O（1），其中H是无前缀的柯尔莫哥洛夫复杂度。由于算法复杂性和有效随机性之间的联系，这种H-平凡实是有趣的。我们给出了一个新的，更容易的建设一个H-平凡的真正的。我们还分析了H-平凡实数的各种可计算性理论性质，例如，没有H-平凡实数可以计算停机问题（这意味着我们构造一个H-平凡可计算可解集是一个特别容易的，无损伤的不完全c.e.构造。set）。最后，我们与H-trivials其他类的1由新西兰马斯登基金支助[2]德国研究共同体（DFG）海森堡计划资助，资助号Ste 967/12002年由ElsevierScienceB出版。 诉 操作访问根据C CB Y-NC-N D许可证进行。DOWNEY，HIRSCHFELDT，NIES和 STEPHAN372--∈21介绍我们关心的是实数的内在计算复杂性和实数的内在随机性之间的关系。在[11，12]中，我们与LaForte一起研究了通过测量实数的相对初始段复杂度来理解实数的内在随机性的方法（在本文中，因此，例如，如果α和β是实数（在（0，1）中），作为二元序列给出，那么我们可以通过研究基于相对初始段复杂度的约简概念来比较α和β的复杂度。例如，我们定义α≤Kβ，如果K（αTn）≤K（βTn）+O（1），其中我们将用K表示经典柯尔莫哥洛夫复杂度。对于无前缀的柯尔莫哥洛夫复杂度H，我们类似地定义α≤Hβ论文[11，12]的目的是研究上述可约性的结构给定两个雷亚尔，哪个更随机？如果我们将实数划分为具有“相同随机度”的实数的等价类随机实数的经典例子是随机实数的停止概率无前缀机器M，Chaitin的<$= σ ∈dom（M）2 −|σ|.众所周知证明了对所有实数α，α有α≤H α的性质。一个自然的问题是：给定实数α≤Qβ（对于Q H，K），那么相对于图灵约简，α和β的计算复杂性可以说些什么呢？例如，如果我们将注意力限制在可计算可排序（c.e.）reals（其左割是可计算的），那么像H-complete一样的reals意味着real是图灵完备的。一个自然的猜测是，对于所有实数，如果α≤Qβ，则α≤Tβ。然而，这并不普遍。本文研究的是从随机性的角度来看，这些实数在Loveland [29]的基础上，Chaitin证明了如果α是实数且K（αTn）≤K（1n）+O（1），则α是可计算的。也就是说，如果就其柯尔莫哥洛夫复杂度而言，α看起来像1ω，那么它在计算上一定是微不足道的Prefix-free版本怎么样？Chaitin还证明了，如果一个实数α具有H（αTn）≤H（1n）+O（1）的性质，则α是n =0。他问如果这可以改进为α必须是可计算的。这是一个值得注意的结果，人们不能这样改进：Solovay [35]证明了存在100个不可计算实数β使得H（βTn）≤H（1n）+O（1）. 索洛维和邪恶。所有已知的索洛维定理的证明都使用他的技巧的变体。在第3节中，我们将给出一个新的，简短而简单的证明，证明了DOWNEY，HIRSCHFELDT，NIES和 STEPHAN38∨−∈Solovay为了陈述这个结果的一个扩展，我们需要另一个平凡性概念。对拉姆巴根、库什切拉和特温的库什切拉和特温问题的回答[22]构造了一个集合X，它对于随机数是低的。这里我们说X对于random（也称为Martin-Lo？f-low）是低的，其中集合srandom相对于X的集合就是随机集合的集合可以修改第3节给出的构造，以表明存在不可计算的可计算可列集，它们既是H-平凡的，又是低随机的。H-平凡无疑是一个值得注意的现象。本文件的其余部分将专门探讨这一概念。我们证明了没有一个H-平凡集可以是图灵完备的，并且确实每个H-平凡集都有数组不可计算（anc）度，其中一个度是anc，如果它包含Downey，Jockusch和Stob [13，14]的数组不可计算集之一（定义见第6节）。这意味着构造一个不可计算的H-平凡实数为波斯特问题提供了一个非常简单（本质上是一行在一份未发表的报告中，Zambella [40]证明了存在一个可计算函数f，使得对于每个c，至多有f（c）许多实数α，H（αTn）≤H（1 n）+c.Zambella定理的证明还没有出版。我们将证明这个结果。约简≤H是一个预序，因此我们可以从它形成一个度结构，即H-度。在c.e.上得到的学位结构。reals的连接操作是普通加法。即[α] [β] = [α+β]，其中[α]是α的H-度。H-平凡实构成最小H-度.平凡性的概念似乎与弱真值表约简密切相关。回想一下A≤wttBi，存在一个图灵过程Φ和一个可计算函数ψ，使得ΦB =A，并且对于所有x，在输入x上查询B的最大数目由ψ（x）限定证明了H-平凡实在wtt-度上形成理想.与H-triviality相关的是Kummer的工作[24]。Kummer研究了根据经典的（非无前缀的）柯尔莫哥洛夫复杂度，我们知道如果A是一个可计算的集合，那么对于所有n，K（ATn）≤2 logn+O（1）。Kummer构造了可计算的可积集合A和常数c，使得K（ATn）2 logn c有无穷多次。 他称这样的集合为复杂集合。 库默尔还表明，可计算的可计算度表现出缺口现象。也就是说，要么一个度a包含一个复集合A，要么所有c. e. Aa是0. (By Chaitin库默尔证明了包含这种复杂集合的度就是anc度。我们证明（i）不是每个DOWNEY，HIRSCHFELDT，NIES和 STEPHAN39--↓↓⇒↑2（ii）存在只含Kummer平凡集的图灵度，而不含H平凡集。结果（ii）意味着库默尔平凡不使一个集合H-平凡。2基本定义我们的符号是标准的，除了我们遵循使用H表示无前缀复杂度和K表示非无前缀复杂度的传统。我们的可计算性理论符号遵循Soare [33]。我们处理0和1之间的实数，用它的二进制展开来识别实数，因此用其特征函数与该展开相同的自然数集合来识别实数。实数α是c. e。如果它的左割是c.e.作为一个集合，或者等价地，如果α是可计算有理数递增序列的极限我们使用输入和输出字母0， 1的机器。一个机器M是无前缀的（或自定界的），如果对于所有有限的二进制串σ和τ ∈ τ J，我们有Mσ（τ）Mσ（τJ），其中Mσ意味着M使用σ作为预言机。它是普适的，如果对于每个无前缀机器N，存在一个常数c，使得对于所有二进制串σ和τ，如果N σ（τ）↓，则M σ（μ）↓=N σ（τ），对于某些μ，|µ|≤|τ |+ c。我们称c为N的编码常数。二进制串的无前缀复杂度H（τ）是最短二进制串σ的长度，使得对于固定的通用无前缀机M，M（σ）=τ。（M的选择并不影响无前缀的复杂度，直到一个常数的加法因子。对于一个自然数n，我们写H（n）forH（1n）。一个实数α是随机的，或者更精确地说，是1-随机的，如果H（αTn）n−O（1）。构建无前缀机器的一个重要工具是Kraft-Chaitin定理。Theorem2. 1（Kraft-Chaitenchin）Fromac.e. 对的s e quen ce（ni，σin）i∈ω（称为公理），使得i∈ω2−ni≤ 1，我们可以有效地获得一个prefix-自由机M使得对于每个i都有一个长度为ni的τi，其中M（τi）↓=σi，而M（μ）↑除非μ = τi，对于某些i。3Solovay定理的一个简短证明我们现在给出索洛维定理的简单证明这是由Solovay在他1974年的手稿中证明的[35]。这里的证明是复杂的，只构造了一个100实数。定理3.1（在Solovay [35]之后）存在一个不可计算的c.e. 设置使得H（ATn）≤ H（n）+O（1）.注3.2虽然下面的证明很容易，但要理解它为什么有效却有点困难。所以，作为动机，假设我们被要求DOWNEY，HIRSCHFELDT，NIES和 STEPHAN40{∈}{∈}⟨||⟩e则集合B= 0 n：nω 具有与ω=相同的复杂度 1例：例ω。要做到这一点，一个复杂的方法是我们构建自己的无前缀机器M，它的唯一工作是计算B的初始段。这个想法是，如果通用机器U在输入σ上收敛到1n，那么M（σ）↓= 0n。请注意，实际上，使用Kraft-Chaitin，隐式地构建M，以确保满足某个要求（或“要求”）|σ|，0n.我们保证适用Kraft-Chaitin。τ∈dom（M）2−|τ|≤σ∈dom（U）2−|σ| 1，因此还请注意，为了方便起见，我们可以像在主配置文件中一样，使用长度为|σ|+1，在这种情况下，我们将确保τ∈dom（M）2−|τ|<一半。定理3.1的证明 这个想法如下。我们会建立一个不受信任的首席执行官。设A代替注释中描述的B，如上所述，我们将在n上盲目地跟随U，在这个意义上，每当U在阶段s枚举一个较短的σ，其中U（σ）=n，那么我们将枚举一个要求⟨|σ|+1，AsT nn，对于我们的机器M。 为了使A不可计算，我们有时也会使AsTn/=As+1Tn。然后对于每个j，其中n≤j≤s，对于当前最短的字符串σj计算j，我们还需要枚举M的公理σj，As+1Tj。这种构造通过使添加到M的域上的额外测度变小而起作用。我们可以定义A：A={E，n∈E，s∈A，s= E，n∈E，s∈E，s ∈A，s = E，n ∈ E，n ∈ N，n ∈ NΣe，n2-H（j）[s]2-（e+2））}，<其中，We，s是第e个近似于第e个c. e的阶段。集合，H（j）[s]是j的H-复杂度的阶段s近似。Σ显然，A是C。由于jm2−H（j）随着m的增加而趋于零，如果We”[10]“是的，是的。很容易看出，这意味着A是不可计算的最后，将ex tra测度放在M∈N的域上，进入U域的一半，由e2−（e+2）（对应于每个e的至多一个初始段变化），其中ΣΣ2 −|σ|<2-（|σ|+1）+2−（e+2）≤ 1 + 1 = 1。σ∈dom（M）2 2σ∈dom（U）e因此M是一个无前缀机器，因此H（A T n）≤ H（n）+O（1）。✷我们注意到，上述证明可以修改，以证明一个更强的结果，这似乎是由于Muchnik，即存在一个不可计算的c. e。集合A是超-H-平凡的，在这个意义上，相对于A的H-复杂性与H-复杂性相同，直到一个加法常数。这样的A是H-平凡的，并且对于随机数是低的显然，这个证明也承认有许多变化。例如，我们可以一个迅速简单的，或低于任何非零的可计算的程度。我们DOWNEY，HIRSCHFELDT，NIES和 STEPHAN41e∀我⟨⟩不能控制跳跃或使图灵完备，因为，正如我们将看到的，所有的H-trivials都是图灵不完备的，事实上，低2。我们不知道H-trivials是否与随机集的低点一致。一个有趣的测试案例是是否所有的H-trivials都是低图灵度的，因为所有随机集的低图灵度都是低图灵度的（通过合并Kucera和Terwijn[22]和Nies[31]的结果4H-trivials的图灵度在这一节中，我们给出了一个证明，每个H-平凡的c. e。实数是图灵不完备的。这个证明可以修改，以表明每个H-平凡实数α都是图灵不完全的，并且没有高h（即，，αJTJ）。 一个更复杂的修改表明α必须是数组可计算的，因此低2（即，αJJ <$T<$JJ）。定理4.1每个H-平凡c.e.真正的图灵不完整。证据 因为每一个C. E。实际上存在WTT等效的C. E。这是一个很好的证明定理。集.假设A是H-平凡的，c.e.，完整和反映当前情况为方便起见，假设使得t 0∈/A，因此，虽然t是实数，但A≤1/2。让我来吧ΦA =K，其中K是停机问题，设d使得n（H（ATn）≤H（n）+d）。我们建立一个CE。集合B和一个无前缀机器M（通过Kraft-Chaitin定理）。 通过递归定理，我们可以假设我们知道i，ΦK =B和M的编码常数b。设Γ = Φi<$ Φe，则其中，ΓA=B，且c=b+d，s∈H（ATn）≤HM（n） +c。设k=2c+2。对于Γ的γ的用法，我们采用通常的约定所有值都附加了[s] 将在舞台结束时进行 我们还假设我们已经放慢了我们的构造速度，使得s <$n≤ s（H（AT n）[s] ≤ HM（n）[s]+ c）和s<$n≤s（Γ A（n）[s] ↓）。我们将有以下全局变量：自然数m0，...，mk−1，始终保持递增顺序; realsUsed和Trash;以及自然数集合Current j（j ≤ k）和Successful。在下面的每个过程中，q将始终是局部变量。让我们首先定义增加的程序：(i) 设s+ 1为当前阶段。(ii) 选择一个新的大n并枚举 n，2−γA（mk−1）[s]作为公理，M. 将2−γA（mk−1）[s]加到Used。(iii) Ifduringgstages+1somenumbentersAbellowγA（mk−1）[s]thenremovee2−γA（mk −1）[s] fromUsed and add it toTrash.在这种情况下，返回0。(iv) 将n枚举到Currentk中，结束阶段s+1，并返回2−γA（mk−1）[s]。现在让我们定义过程LLOAD（j）：DOWNEY，HIRSCHFELDT，NIES和 STEPHAN42∈∞M(i) 如果j=k，则返回INCREASE。(ii) 设q= 0，s+ 1为当前阶段。(iii) Whileq2−γA（mj−1）[s]（orq1/2ifj=0）：<<(a) 调用LOAD（j+1）并将返回值加到q上。(b) 结束当前阶段t。(c) 如果γA（mj−1）[t]/=γA（mj−1）[s]，则从mUed重新计算q，并将其添加到垃圾在这种情况下，清空Currentj+1并返回0。(iv) 将mj枚举到B中，并为每个mi，iJ.(v) 如果，在当前阶段t+1，somenumberntersAblowγA（mj−1）[t]，则从Used中删除q并将其添加到Trash。在这种情况下，清空Currentj+1并返回0。(vi) 将Currentj+1中的每个数字枚举到Currentj中，清空Currentj+1，结束阶段t+ 1，并返回q。我们的主要程序如下：(i) 令Used=Trash= 0，并令每个Currentj为空。选择值m0，...， mk−1。(ii) 电话LOAD（0）(iii) 假设成功=当前0。很 容 易 检 验 M 的 公 理 的 总 量 等 于 Used + Trash ， Used≤1/2 ，Trash≤A≤1/2。(To注意，对于每个n A，作为n在阶段s进入A的结果而放入垃圾桶的量最多是对应于当前j的元素的量，对于最小的j，使得n <γA（mj）[s]，并且这个量nt由y2−γA（mj）[s]限定。此外，主程序必须终止。这可以通过以下方式来论证：逆向归纳法首先，LOAD（k）总是返回。现在假设LLOAD（j+ 1）总是返回。那么LOAD（j）卡住的唯一方法是如果连续调用LOAD（j+1）返回的值变为0。但这将意味着limsγA（mj）[s] =，与对Γ的选择相矛盾。因此，通过归纳，LOAD（0）总是返回，并且通过与上面相同的参数，连续调用此例程返回的值不会变为0。这意味着主过程最终会终止。Σ现在很容易检查Used=n∈Successful 2−HM（n） = 1/ 2。 我们声称对于每个n∈Successful，如果s最小使得HM（n）[s+1]=HM（n），则一个Tn假设至少有一个在阶段后的价值。如果这是真的，那么我们这是一个矛盾，因为2c+22−c（1/2）>1。n∈成功k2−（HM（n）+c）=k 2−cn∈Successful2−HM（n）=为了验证这个说法，让n∈Successful。在某个阶段s+ 1，我们列举n，2 −γA（mk−1）[s]n作为M的公理。注意H（n）[s+ 1] =H（n），因为M我们从来没有列举过另一个涉及n的公理。对于每个j k，设tj+ 1为n进入Currentj的阶段，并设DOWNEY，HIRSCHFELDT，NIES和 STEPHAN4323⟨⟩⊕−关于我们lj=γA（mj）[s]. 由于m个输入A位于tj+1，因此我们具有A[tj+1]TljA[s]Tlj。另一方面，A[tj+1]Tlj−1=A[s]Tlj−1，因为否则n不能进入Currentj。所以我们有一个A[tk−1]Tn/=···=A[t0]Tn，如所需。✷最后一个限制如下。定理4.2 H-平凡实的图灵度有界于c.e.度严格小于0 J。证据 Nies（未发表）已经证明了每个H-平凡实数是图灵可约的一个H-平凡c.e.。集合，因此证明H-平凡c. e.集. 注意，陈述对于所有的n因此，H指数的集合平凡c.e.设置为100。我们可以列举一个分段的c.e.setA，其中i，c-第列等于WiiWi是H-平凡的，具有常数c，并且有限否则，请执行以下操作。根据定理6.3，H-平凡体在并下是闭的，所以这样的集合具有m≤nA（m）对所有m都是图灵不完全的性质。因此，结果由厚度引理的强形式得出（例如，Soare [33]，第八章，定理2.3和2.6）。✷在未发表的工作中，Nies证明了H-平凡c. e.的度集合被低2c.e.限制在0J集这一点更难证明。5Zambella在本节中，我们将证明一些未发表的材料Zambella。我们的证明是不同的，我们建立了一些中间结果的独立利益。定义5.1给定一个无前缀机器D，我们定义关于D的Zambella测度为ZD（σ）= μ（D−1（σ））。也就是说，ZD（σ）是D输出σ的概率。如果D是固定的通用机器，我们将Z（σ）写成ZD（σ）。定理5.2 ZD（σ）= O（2 −H（σ））.我们做了一些评论，然后再把它发布出去。的量度复杂度是任何函数F：2 <ω→ω，使得σ 2 −F（σ）< 1和σ，k：F（σ）≤k是c.e.。Chaitin [5]引入了这个概念，并证明了H-复杂性是复杂性的最小测度，在这个意义上，对于任何复杂性测度F，我们有H（σ）≤F（σ）+O（1）。注意log 2Z（σ）是复杂性的度量，因此，通过H在复杂性度量中的极小性，我们知道2 −H（σ）≤ Z（σ）。因此通过DOWNEY，HIRSCHFELDT，NIES和 STEPHAN44⟨ −⟩−| |||↓定理5.2，我们知道对于某个常数d，2 −H（σ）≤ Z（σ）≤ d 2 −H（σ）。因此，我们经常可以用Z代替H的用法。作为一个例子，α和β，我们有以下结果。定理5.3α≤Hβ i ≠有一个常数c使得对所有n，cZ（βTn）Z（αTn）。证据 假设α ≤Hβ。 然后有一个常数d使得对所有n，H（αTn）≤H（βTn）+d。这种情况发生在i = 1时，有一个常数dj，使得对于所有n，2 −H（α<$n）dJ 2 −H（β<$n）.对于某些c和所有n，Z（αTn）cZ（βTn），这是随机发生的。另一个方向是相似的。✷注5.4对任何σ，Z（σ）是随机的。为了证明这句话是正确的，我们使用Kraft-Chaitin定理来建立一个机器M，并证明，其中≤S是Solovay约简（见[12]关于Solovay还原的定义和讨论在阶段s，如果我们看到U（ν），其中U是通用机器，我们宣布M（ν）=σ。则对某个c=cM，存在一个满足U（νJ）=σ的νJ，且ν≤νJ+c.因此，当我们加上2-时，|ν|1、2、3、4、5、6、7、8、10、11、12、13、14、15、16、17、18、19、20、21、22、23、24 、 25 、 26 、 27 、 28 、 29 、 20 、 21 、 22 、 23 、 24 、 29 、 22 、23、24 、25 、26、29、22 、29 、20、21 、22 、2|ν|+c）到Z（σ），因此σ≤SZ（σ），这意味着Z（σ）是随机的。现在我们来看定理5.2的证明。证明的思想如下：我们将使用Kraft-Chaitin定理定义一个无前缀的机器M如下。每当我们看到ZD（σ）22r−n时，其中n是σ的当前H-复杂度，我们将枚举公理n r+ 1，σ（说，某个长度为n r+ 1的字符串被M映射到σ）。 对于足够大的r，我们将与H的极小性相矛盾。详细地说，在阶段s，我们做以下事情。对于每个σ，n，r s，如果• σ，n，s还没有注意到，• n >2r2，• H（σ）[s] =n，以及• ZD（σ）22r− n，然后通过枚举公理<$n−r +1，σ<$n来处理σ，r，n。请注意，对于任何固定的σ，r，我们将公理<$n−r+1，σn放入n的递减值中。设hσ，r是最后一个输入的值我们最多加Σ∞n=0例2−（hσ，r−r+1 +n） = 2−hσ，r+rDOWNEY，HIRSCHFELDT，NIES和 STEPHAN45⟨ −⟩⟨ − ⟩−因此，在本发明中，{||}在M的定义域的测度上。当我们放入最后一个公理hσ，rr +1，σ时，我们看到ZD（σ）22r−hσ，r。由于D是无前缀的，对于这个固定的r，我们可以得出结论，Σ2 2r−hσ，r≤ 1。σ因此，2 r2 −hσ，r+r≤ 1。σ因此，对于r，我们至多可以将2−r加到M的整环的测度上。因此，当r1时，我们可以应用Kraft-Chaitin定理得出M存在的结论。设c为，H（σ）≤HM（σ）+c。设d=22（c+2）. 我们声称ZD（σ）≤ d 2 −H（σ）。为了证明这一点，让r=c+ 2。如果ZD（σ）>22r−H（σ），那么最终我们放入公理H（σ）r+ 1，σ，因此HM（σ）≤H（σ）（c+ 1），这是一个矛盾。这就完成了定理5.2的证明这个结果允许我们得到Chaitin关于字符串描述数的结果的模拟推论5.5存在一个常数d，使得对所有c和所有σ，|ν|≤ H（σ）+ c }|≤d 2 c。| ≤d 2 c.证据简 单 地说，μ（{ν：D（ν）= σ|ν|≤H（σ）+c}）2−（H（σ）+c）·|{ν：D（ν）=στ|ν|≤H（σ）+c}|. 但同时，μ（{ν：D（ν）= σ |ν|≤ H（σ）+c}）≤ d·2 −H（σ），根据定理5.3。d2−H（σ）2 −c 2 −H（σ）|{ν：D（ν）= στ|ν|≤H（σ）+c}|.因此，d2c|ν|≤ H（σ）+ c }|.|.✷我们现在可以得出结论，只有很少的三价氢.定理5.6集合Sd=σ：H（σ）0，存在一个常数c，使得对于所有n，K（DTn）≤（1 + n）logn + d.包含复集合的相关度是Downey，Jockusch和Stob的数组不可计算度。 回想一下，一个非常强的数组{Fx：xN是一个强数组，使得Fx c有V Fg=A Fg，与A的数组不可计算性相矛盾。对于每个e，我们做以下事情。首先我们通过对 公理 2d+e+1，1z进行计数， 我们可以得到某 些freshz>maxx：xFe+c。 单向机必须在某个阶段s通过在长度≤d+e+ 1 +c的某个输入σ上收敛到AsTz来响应。然后，我们枚举到Vs，我们的“杀死”c.e.。set，theleastpFe+c在Vs中不存在，使Fe+cA[s]=VsFe+c[s]。注意，只有在U的整环测度上加上一个量子2e+1+c+d后，才能触发V的计数。现在，我们可以将in变换为V的可能的变换数目为Fe+c，其大于2e+c+1+d。因此，A不能每次都响应，因为如果它响应，那么U的域的测度将大于1。✷人们可能会认为，库默尔琐碎的c. e.集合和H-平凡集合对应。下一个结果显示至少有一个包含失败。这个证明是技术性的，为了节省篇幅，我们省略了它。定理6.7有一个c. e.图灵度a只由Kummer平凡数组成，不含H平凡数。数组不可计算度与我们的研究还有一个联系。回想一下，集合A对于随机i是低的，每个随机集合仍然相对于A是随机的。KuChercera和Terwijn[22]是最早构造这种集合的人。他们利用Sacks [32]的一个定理证明了随机集A的任何下界都必须是GL1图灵度。也就是说，AJTAJ。Nies [31]改进了这一点，他还表明，对于随机，只有可数多个低他们都是一群人，他们都是一群人，他们都是一群人。，AJTJ）.Thefollowowing结果似乎是Zambella定理在伊斯穆哈梅托夫之后[16]，一个可追踪的或弱可计算的集合，如果存在一个可计算函数，f使得对所有g≤TA，存在弱数组{Wh（x）：x∈N}使得DOWNEY，HIRSCHFELDT，NIES和 STEPHAN502(i) |Wh（x）|≤ f（x）对于几乎所有的x和(ii) g（x）∈Wh（x）对所有x.Ismukhametov [16]观察到，如果一个度是弱可计算的，那么它是数组可计算的，并且这些概念对于可计算的集合是一致的伊斯穆哈梅托夫证明了显着的定理，c.e.具有强极小覆盖的度就是弱可计算度。此外，任何弱可计算度（一般情况下）都有强极小覆盖.定理6.8假设A对于随机数是低的。 A是低的（Nies [31]）此外，A必须是弱可计算的。素描证明。如果有人模仿Terwijn-Zambella证明Schnorr低集是可计算追踪的（[37]），但使用Martin-Lo？flownessinplaceofSchnorr lowness，则“if”方向证明了✷引用[1] A mbos-SpiesK.， 和A.Ku Chancera，Randomnessinomputability Theory，inComputability Theory and its Applications（Cholak，Lempp，Lerman，Shore，eds.），当代数学257，美国数学学会，Providence，2000，1-14.[2] 卡鲁德角，信息论与随机性，数学观点，Springer-Verlag，Berlin，1994.[3] 卡 鲁 德 角 ， P. Hertling ， B. Khoussainov ， B. ， 和 Y. Wang ，RecursivelyRecursible reals and Chaitin[4] 卡鲁德角，和A. Nies，Chaitin，Numbers and strong reducibilities，Journalof Universal Computer Science 3（1998），1162[5] Chaitin ， G. ， A theory of program size formally identical to informationtheory，Journal of the Association for Computing Machinery 22（1975），329[6] Chaitin，G. 递归无限弦的信息理论特征，理论计算机科学2（1976），45[7] 唐尼河，10度和转移定理，伊利诺伊州数学杂志31（1987年），419-427.[8] 唐尼河和E.Gri Alberths，On Schnorr randomness，in preparation.[9] 唐 尼 河 和 D. Hirschfeldt ， Aspects of Complexity （ Short courses inComplexity from the New Zealand Mathematical Research Institute Summer200