能行实数是可计算理论的基本概念之一。可计算有理数序列的极限称为能行实数,又称为△02实数。若该可计算有理数序列递增,则其极限称为可计算可枚举实数(c.e.或left-computable实数)。若该可计算有理数序列递减,则其极限称为右可计算实数(co-c.e.或right-computable实数)。我们讨论在[0,1]区间内的实数α,那么其二进制表示可记为α=0.XA。[0,1]区间内的实数和自然数集合的子集构成一对应关系。可计算理论中关注的可计算集合和可计算可枚举(c.e.)集合对应到特殊的c-e.实数。其中,可计算实数和可计算集合是等价的概念,但是c.e.集合区别于c.e.实数。更多能行实数的分类知识见[56]。　　 经典计算理论中通过归约比较集合的复杂性的思想自然的运用到实数。给定两个能行实数α,β,我们可以通过归约比较两者的计算复杂性。如果存在一台带外部信息源的图灵机r使得α=Γβ,那么称α图灵归约于β(记作α≤Tβ)。α(n)的值可以通过图灵机Γ查询β中元素的信息能行给出。依据查询β的信息量的多少,可以划分更细致的归约。如,当每次查询的内容总是被一个可计算函数限制的时候,称α≤wttβ。　　 可计算实数在运算“+,一,×,÷”保持封闭,也就是说,可计算实数集合构成域。在能行实数集中,有可计算实数集合的扩展域存在吗?左(右)可计算实数集作为可计算实数集的扩充,成为我们考虑的对象。但是,两者除了对“+”运算,其它运算都不保持封闭。可计算可枚举实数和右可计算实数统称为半可计算实数。遗憾的是,半可计算实数保持“×,÷”,但是对“+,-”不成立。上述的问题可转化为半可计算实数集合的闭包是怎样的实数集合。两个c.e实数的差称为d-c.e.实数。D-c.e.实数集合给出了回答。Ambos-Spies,Weihrauch和Zheng[3]证明:d-c.e.实数集合是半可计算实数集合的算术闭包。d-c.e.实数存在如下的等价刻画。α是d-c.e.实数当且仅当存在可计算有理数序列{αs}s∈N弱收敛到α,即存在常数c使得∑s∈N|αs-αs+1|≤c[3]。所以,d-c.e.实数又称为弱可计算实数。D-c.e.实数构成了特殊的能行实数类。本文中我们希望了解包含d-c.e.实数的图灵度的结构。　　 在算法随机性理论中,比较实数的随机程度是一个基本问题。复杂性K和C可以建立比较随机性的度量。令E=K或C,如果所有的n,E(α↑n)≤E(β↑n)+O(1),称α≤Eβ。此时,β比α更随机。≤E是对实数随机性的比较,但不是可计算意义下的归约。例如,对c.e.实数α和β,α≤Kβ无法推得α≤Tβ。有没有可计算意义下能够比较实数随机程度的归约呢?　　 Solovay首先对这一问题展开研究,提出了Solovay归约。Solovay[45]证明若α≤sβ,则α≤Eβ。所以,Solovay可以用于比较实数的随机性。c.e.实数在随机性理论占有重要的位置。典型的例子如下,给定前缀自由的通用图灵机M,σ∈∑*,令停机概率ΩM=∑M(σ)↓2-|σ|则ΩM为随机的c.e.实数。如无混淆,下标M可以省略。Solovay指出Ω满足Solovay完备,即所有的c.e.实数都Solovay归约于Ω。进一步,Ku(c)erm和Slaman[32]证明:若α是随机的c.e.实数,那么所有的c.e.实数都Solovay归约于α,即α是Solovay完备.上述结论给出随机的c.e.实数的完整刻画:c.e.实数Solovay完备当且仅当该c.e.实数随机。Solovay归约作为比较随机性的工具关于c.e.实数得到了很好的结果。但是,Solovay归约存在缺陷,见[14]。首先,在超出c.e.实数的范围,Solovay归约并不是一种好的归约。我们可以找到一个d-c.e.实数在Solovay归约之下,不在任何c.e.实数之上。其次,Solovay归约过于精细,过于一致。　　 为了避免Solovay归约的缺陷,Downey,Hirschfeldt,and LaForte[16]尝试引入一些新的归约作为比较随机性的度量,如cl-归约,rK-归约。本文中关注cl-归约。给定实数α和β,若存在可计算函数Γ和常数c满足α=Γβ,并且用函数u(Γ,β,n)≤(n+c),称α可计算Lipschitz归约于β(即α≤clβ)。可以看到,若α≤clβ,则α≤Eβ。相对Solovay归约而言,cl-归约显得更为直观。Soare,Nabutovsky and Weinberger将cl0(c=0)-归约应用到微分几何的研究中。　　 Downey,Hirschfeldt,and LaForte引入cl-归约后,充分比较了cl-归约和Solovay归约的关系[14]。Cl-归约和Solovay归约在c.e.集合上表现出一致,也就是说,对于c.e.集合S≤cl B当且仅当A≤s B。但是对于c.e.实数,一致性不再保持。Downey,Hirschfeldt,and LaForte[14]构造了两个c-e.集合满足在Solovay归约之下不存在下确界。依据cl-归约和Solovay归约对c.e.集合的一致性,包含c.e.实数的cl-度也不构成下半格度。对于c.e.实数,cl-归约是否也能同Solovay归约一样把随机的c.e.实数划到一个等价类呢?Stephan给出了否定的回答[5]。Ω作为特殊的随机c.e.实数,在cl-归约下是否仍然保持cl完备性呢?Yu和Ding[52]否定回答这个问题:在cl-归约之下不存在完备的c.e.实数。实际上,Yu和Ding[52]证明了更强的结果:存在两个c.e.实数,使得任何c.e.实数都不可能同时计算两者。此结果表明,包含c.e.实数的cl-度不构成上半格。综上,c.e.实数的cl-度既不是下半格,也不是上半格。这个结构表现出cl-度结构的特殊性,区别于以往的T-度,wtt-度,Solovay度等等构成上半格结构。我们希望对这特殊的非上半格结构进一步加以讨论分析。更多关于cl-度结构的结论见[4],[6],[5],[7],[35],[36]。　　 本文的具体贡献如下。我们分为两个部分叙述。　　 第一,本文对d-c.e.实数的图灵度的结构展开分析。特别的,我们引入全d-c.e实数的概念。K-平凡实数(K-trivial实数)的存在肯定回答了非可计算的全d.c.e.实数的存在。因为K-平凡实数是d-c.e.实数,而且K-平凡实数T-归约下向下封闭[17]。本文中,我们加强了全d-c.e实数存在性的结果。任给的c.e.T-度下总存在全d-c.e.实数;而且存在全d-c.e.实数满足正则的ω-c.e.。虽然所有的K-平凡实数均为低,但是本文能行的构造了一个非低的全d-c.e.实数。　　 第二,本文对c.e.实数的cl-度不构成上半格这一特殊结构展开研究。为了说明不存在cl完备的c.e.实数,Yu和Ding[52]构造了两个c.e.实数α,β使得任何的c.e.实数不可能同时cl-计算它们。本文针对α,β满足的特殊性质提出cl-极大对的概念。如果α,β属于C,并且不存在C中元素γ使得degcl(α)≤degcl(γ)和degct(β)≤degcl(γ),则称(α,β)为C的cl-极大对。　　 当C表示c.e.实数时,我们称(α,β)为c.e.实数的cl-极大对。Yu和Ding[52]的证明回答了c.e.实数的cl-极大对的存在性问题。Yu-Ding程序是证明中的关键点,它刻画了在给定区间以最小的量交替递增的两个序列可以导致cl0-计算它们的c.e.实数充分大。本文中,我们成功构造一个c.e.实数的cl-极大对,保持其中一个元素为c.e.集合。这一构造的难度在于,c.e.集合不仅保持序列的给出保持递增,而且要求对应二进制实数的每个位置至多变化一次。所以,同样长度的空间上c.e.集合与c.e.实数组合的变化远远地弱于两个c.e.实数组合的变化。Yu-Ding程序不再适用。本文中通过控制c.e.集合与c.e.实数的变化次序归纳得找到了满足要求的程序。所有的可计算实数不构成c.e.实数的cl-极大对。是否有不可计算的c.e.实数也不构成c.e.实数的cl-极大对呢?本文给出了一个很强的结果:每个不可计算的能行实数总能找到c.e.实数使得任何c.e.实数不能同时计算他们。作为推论,所有的不可计算的c.e.实数都能构成c.e.实数的cl-极大对。不难发现,以上得到的极大对中的元素都是我们可以控制的。而对于任意给定不可计算的能行实数,我们将失去控制其变化的能力,唯一可利用的就是其不可计算的性质。文中,我们成功利用了不可计算性质找到合适的程序证明了结论。　　 当C表示c.e.集合时,我们称(α,β)为c.e.集合的cl-极大对,并记(α,β)=(A,B)。我们发现,对于c.e.集合能否构成的c.c.集合的cl-极大对与阵列不可计算(array noncomputable)概念紧密相关。阵列不可计算的图灵度对应着包含c.e.集合的cl-极大对的图灵度。随后,本文观察了T-归约和wtt-归约下完备集合与构成cl-极大对的c.e集合之间的关系。Wtt-完备的c.e.集合可构成c.e.集合的cl-极大对,但T-完备无法满足充分性。最后,结合cl-归约下无最大的c.e.集合的证明方法,我们证明了给定c.e.集合,在其向上的椎体中总存在c.e.集合的cl-极大对。　　 综上所述,本文在详细分析Yu和Ding证明后对cl-极大对的结构做出详细讨论,引入新的概念与技巧,改进已有的证明方法后得到了全新的结果,具有相应的理论意义。