可计算性与相对可计算性是经典递归论的研究对象，关于随机性的研究则兴起得较晚却成长迅速。可计算性与随机性都可以被看作是关于自然数集（或实数或无穷序列）的性质。不仅如此，这两组概念系统有着密切的互动。从历史上看，可计算性理论是随机性理论的前提，但对随机性概念的研究也反过来加深了人们对可计算性的理解。

回顾上一节中对随机性的刻画，随机性基本被呈现为可计算性的反面。例如，马丁-洛夫随机性被定义为不被任何一个能行的测试所捕获，或者它的任何前段都不能被能行地压缩，又或者没有能行的押注策略能在其上获胜。对随机性概念的加强或减弱也往往通过调节对相关测试的能行性要求。对测试越弱的能行性要求对应于越强的随机性概念；越强的能行性要求对应越弱的随机性概念，因此，n-随机的序列都不是Ø（n-1）下可计算的。这一模式对利用柯尔莫哥洛夫复杂度或马提克策略的刻画也是有效的。

低效性（lowness）是来自可计算性理论的一个重要概念，被用来刻画一个集合作为神谕的无用性。低效的集合曾被认为是接近递归的集合。

定义　2.27（低效性）　给定集合A⊂N。

（1）称集合A是低效的（low1），当且仅当A′≡TØ′；

（2）称集合A是超低效的（superlow），当且仅当A′≡ttØ′；^[21]

（3）称集合A是广义低效的（generalized low，也记作GL1），当且仅当A′≡A⊕Ø′。

由于总有A≤TA′，低效的集合都是≤TØ′，也即的。广义低效集则未必是的，但在集合上，低效与广义低效是等价的。由于真值表归约（见定义2.5）是比图灵归约更严格的归约概念，超低效性蕴涵低效性，反之则不然。我们可以推广上述定义：对n ≥1，称集合A是lown的，当且仅当A（n）≡TØ（n）；称集合A是GLn的，当且仅当A（n）≡T（A ⊕Ø′）（n-1）。显然，lown/GLn分别蕴涵lown+1/GLn+1。

显然，低效的集合是不能作为神谕计算停机问题Ø′的，否则Ø′就可以计算相对于自己的停机问题了。因为Ω（≡TØ′）是马丁-洛夫随机的，所以马丁-洛夫随机未必是低效的。这可能给人以错觉，即随机序列可能包含大量有用的信息。例如，可以用来判定停机问题。这或许是量子计算机在公众间享有很高期待的原因之一。在信息科学中，人们的确可以根据随机序列不可压缩性的特点宣称其中包含很多信息。但是，随着对随机性概念，尤其是强随机性概念更深入的研究，人们发现更强的随机性反而会导致低效性。

定理　2.28（考茨）假设X是（n+1）-随机集合，那么X（n）≡TX⊕Ø（n）。特别地，所有2-随机集合都是GL1的。

考茨（Kautz，1991）的结果意味着，2-随机集合不会出现在倒锥体T（≥T0′）中。

利用随机性概念，人们还可以定义更多的低效性。例如，尼茨、斯蒂芬和特尔文扬（Nies et al.，2005）刻画的对Ω低效性（lowness for Ω）。

定义　2.29（对Ω低效）　集合A是对Ω低效的，当且仅当Ω是相对于A马丁-洛夫随机的。

如果集合A是对Ω低效的，意味着它作为神谕并不能得到更多的测试以排除Ω的随机性，而尼茨等人证明了，2-随机集合都是对Ω低效的。不仅如此，马丁-洛夫随机序列的低效性甚至是它作为2-随机的充分条件。

定理　2.30（尼茨-斯蒂芬-特尔文扬）马丁-洛夫随机集合A是对Ω低效的，当且仅当A是2-随机的。

类似带神谕的图灵机，我们可以刻画并枚举带神谕的无前束程序，并由此定义带神谕的通用无前束程序Upf，X，以及相对于X的无前束柯尔莫哥洛夫复杂度KX（σ）=KUpf，X（σ）。米勒（Miller，2009）借用无前束柯尔莫哥洛夫复杂度概念定义了弱对K低效性（weakly lowness for K）。

定义　2.31（弱对K低效）　集合A⊂N是弱对K低效，当且仅当存在常数c，存在无穷多σ∈2＜ω使得

K(σ)≤KA(σ)+c。

换句话说，弱对K低效的集合作为神谕在很多情况下都不能提高无前束程序的解压缩能力。^[22]米勒证明，集合A是弱对K低效的，当且仅当它是对Ω低效的。由此，2-随机的集合也是弱对K低效的。

在较弱的随机性概念中也存在见证随机性蕴涵低效性的定理。例如：

定理　2.32（尼茨-斯蒂芬-特尔文扬）假设集合A是施诺尔随机并且不是高效的，那么A是马丁-洛夫随机的。

其中，高效（highness）性被定义为低效性的对偶性质。我们称集合A是高效的（high1），当且仅当Ø′′≤TA′；称A是highn的，当且仅当Ø（n+1）≤TA（n）。

米勒和喻良（Miller and Yu，2008）的定理从另一个角度证明了随机集合所含信息的无用性。

定理　2.33（米勒-喻良）假设A≤TB且A是1-随机的，那么B是n-随机的蕴涵A也是n-随机的。

用较高随机性的集合作为神谕能算出来的集合（除去如递归集合这样的简单集合）也往往是高度随机的，没有什么有用的信息。

K-平凡性（K-triviality）作为一种反随机性概念最早由柴廷在20世纪70年代初期提出。在（Chaitin，1976）中，柴廷证明，如果序列f是递归的，那么存在常数c，对任意n＜ω有

因为，要描述f↾n，我们只需要一个程序找到n的描述并由n计算出f↾n就行了。类似地，也可以证明如果f是递归的，那么

我们将满足（2.8）的序列称作C-平凡的（C-trivial），将满足（2.9）的序列称作K-平凡的。

定义　2.34（K-平凡）　序列f∈2ω是K-平凡的，当且仅当存在常数c，对任意n＜ω有

K(f↾n)≤K(n)+c。

柴廷还证明了C-平凡的序列都是递归的。这是因为C（n）有一个递归的上界。柴廷在（Chaitin，1975）中证明：存在常数d，对任意常数c，至多只有2c+d个在c下K-平凡的序列。^[23]由于K-平凡性本身构成了一颗树，柴廷的结果表明每个K-平凡序列都是其中的一根孤立枝，因而也是的，即≤Ø′。然而，索罗维（Solovay，1975）构造了不可计算的K-平凡序列。事实上，可以构造递归可枚举的不可计算的K-平凡序列（Downey et al.，2002），这同时是对波斯特问题的一个不依赖于优先方法的解决方案。^[24]

由于存在常数d使得K（n）≤2 log n+d，对比定理2.17可得：K-平凡的序列都不是马丁-洛夫随机的。如果忽略常数，那么K（f↾n）的上下界分别是n+K（n）和K（n）。马丁-洛夫随机序列每个前段的无前束柯尔莫哥洛夫复杂度几乎都位于上限≤2 log n的范围内，而K-平凡序列每个前段的复杂度几乎都位于下限。因此，K-平凡性可以被看作反马丁-洛夫随机性。

容易证明，K-平凡集合在向下的图灵归约与信息和下封闭：如果B是K-平凡的并且A≤TB，那么A也是K-平凡的；如果A和B都是K-平凡的，那么A⊕B也是K-平凡的。人们有理由猜测，K-平凡或许对应于某种低效性。

赞贝拉（Zambella，Domenico）在1990左右定义了对马丁-洛夫随机低效性（low for Martin-Löf randomness）。

定义　2.35（对马丁-洛夫随机低效）　集合A是对马丁-洛夫随机低效的，当且仅当每个马丁-洛夫随机序列都是相对于A的马丁-洛夫随机。

直观上，对马丁-洛夫随机低效的集合作为神谕没有带来更多的信息，没有提供更有效的测试来排除任何随机序列。换句话说，随机的序列在知道了A的人看来仍然是随机的。显然，如果集合A是对马丁-洛夫随机低效的，那么A是GL1的，但并不能直接看出对马丁-洛夫随机低效的集合是否都是的。库塞拉（Kučera，Antonín）和特尔文扬（Kučera and Terwijn，1999）证明：存在非递归的递归可枚举集是对马丁-洛夫随机低效的。穆奇尼克在1999年定义了对K低效性（low for K），刻画了一类对通用无前束程序不会带来任何效能提升的集合。(www.daowen.com)

定义　2.36（对K低效）　称集合A是对K低效的，当且仅当存在常数c使得，对任意字符串σ∈2＜ω有

KA(σ)≥K(σ)-c。

尼茨（Nies，2005）证明：对马丁-洛夫随机低效与对K低效这两种低效性概念是等价的。更令人惊讶的结果是，这两种集合作为神谕的低效性与集合的反随机性是等价的（Nies，2005）。

定理　2.37（唐尼-希施费尔德-尼茨-斯蒂芬）　对集合A，下述命题等价：

（1）A是K-平凡的；

（2）A是对马丁-洛夫随机低效的；

（3）A是对K低效的。

由于K-平凡的集合都是的，因而所有对马丁-洛夫随机低效的集合也都是的，从而是low1的。利用类似的方法，尼茨证明了所有K-平凡的集合都是超低效的。

通过随机性理论与可计算性理论的互动，人们对自然数集这两组概念系统的理解取得了显著的进展。强随机性无疑是反可计算的，没有任何随机性概念允许递归集合是随机的，弱2-随机、2-随机序列甚至不是的，即不是停机问题可计算的。另一方面，强随机性虽然在不可压缩性意义上意味着高信息量，但却是“无用的”信息，强随机的序列作为神谕为相对可计算性提供的效用是很低的。而反随机性虽然不必然蕴涵可计算性，但确实是相当接近可计算的。所有K-平凡的集合都是的。令人惊讶的是，反随机性也蕴涵低效性，并且与某种低效性是等价的。这里的关键是，反随机性与低效性的等价发生于T（≤T0′）内；而强随机性则往往处于T（≤T0′）之外，并且也是低效的。

【注释】

[1]克罗顿的菲洛劳斯是毕达哥拉斯学派主要代表人物，著有《论自然》（On Nature），据称是毕达哥拉斯学派首部著作（Huffman，1993，p.15）。

[2]有关讨论的综述参见（Burgess and Rosen，1997）。

[3]在图灵的定义中，对图灵机的“步”有严格的定义。在之后递归论的研究中，“步”往往是在语境下的相对概念。在复杂性理论中，对每个输入n，程序停机所需的步数s（n）函数的增长速度是度量程序或函数复杂度的重要依据。而在递归论中，往往只关心是否停机。

[4]当我们希望同时运行所有Φe（e）、随着时间的推移不漏过任何Φe，s（e）的结果时，我们可以先运行Φ0（0）到第2步（即Φ0，2（0））、Φ1（1）到第1步（即Φ1，1（1）），然后运行Φ0，3（0）、Φ1，2（1）、Φ2，1（2），如此类推。这是递归论中常用的方法，后文中提到“逐一”运行时均指采用这种方式运行。

[5]多到一可归约的命名对应于一到一可归约。后者要求见证可归约的递归函数是一一的，也即，要判定不同的自然数是否属于A时，需要问B不同的问题。这是比多到一可归约略强的归约概念。

[6]由于每个自然数的有穷集合都可以被编码为一个自然数，因此，说一个由有穷自然数集组成的集合族是递归可枚举的就是说由这些有穷集合的编码组成的自然数集是递归可枚举的。

[7]值得一提的是，哈林顿（Harrington，Leo）和索阿雷（Soare，Robert Irving）在（Harrington and Soare，1991）中证明存在（E，⊂）上可定义的性质Q（不涉及任何相对可计算的归约概念），使得所有满足Q（X）的递归可枚举集X都有0TXTK。这被认为是在一定意义上实现了波斯特计划。

[8]后文中，在上下文不引起歧义的前提下将结构（T，≤T）简写为T。

[9]我们用x＜Ty表示x≤Ty且yTx。

[10]在递归论语境下，称自然数集族是独立的，当且仅当其中每个集合都无法图灵归约于其他集合的信息和，即。类似地，可以定义一集图灵度是独立的。

[11]对01字符串σ∈2＜ω，我们用|σ|表示该字符串的长度。显然，|σ|=dom σ=card σ。

[12]库珀的证明在后来被发现是错误的。现代的证明使用的是下文中斯拉曼-武丁的方法。而“在……中递归可枚举”的可定义性尚未可知。

[13]理想是偏序结构上的一种子结构，是与滤子（见定义3.17）对偶的概念。假设（P，≤）是一个偏序，称I⊂P是理想，当且仅当：（1）如果存在最小元，那么最小元属于I；（2）I向下封闭，即p∈I且q≤p蕴涵q∈I；（3）对任意p，q∈I，存在r∈I且r ≥p，q。

[14]在本节中，为方便书写，用θρ表示两个字符串θ和ρ的首尾串接，在一些文本中又记作θ^ρ。

[15]在考虑无前束程序M的时候，往往用KM（σ）=CM（σ）来表示σ的复杂度，以强调相应的程序是无前束的。

[16]|σ|是一个自然数，在K（|σ|）以及类似上下文中又指代自然数|σ|的二进制表达。

[17]冯·米泽斯同时也是一位持实证主义立场的科学哲学家，是维也纳小组核心成员。

[18]是所有以σ为真前段的无穷01序列族，它是康托尔空间的基本开集。

[19]对01序列x，y∈2≤ω，x＜Ly表示存在n＜ω使得x↾n=y↾n，x（n）＜y（n）。

[20]但也有例外。例如，德穆斯（Demuth，Osvald）在（Demuth，1988）中定义的德穆斯随机性（Demuth randomness），这也是一种介于马丁-洛夫随机和2-随机之间的随机性概念，但它与弱2-随机性是不可比的。

[21]若A≤ttB且B≤ttA，则记A≡ttB。

[22]读者可以比对“弱对K低效”与后文“对K低效”的定义（定义2.36）。

[23]事实上，唐尼、米勒和喻良（Downey and Hirschfeldt，2010，p. 505）证明了在常数c下K-平凡的集合数量G（c）远少于2c个：limc＜ωG（c）/2c=0。

[24]库塞拉（Kučera，Antonín）早在（Kučera，1986）就以随机性概念为中介，给出了一种对波斯特问题不使用优先方法的解决方案。他证明：假设R是的（即≤Ø′的）马丁-洛夫随机集合，那么存在单集S≤TR。将柴廷停机概率拆分为Ω=A ⊕B，那么，A和B相对于彼此都是马丁-洛夫随机的，因而也不能图灵归约于对方。所以，某个单集S≤TATΩ ≡TØ′就见证了非递归非完全的递归可枚举集合的存在。