0J-可计算实数的度结构及其复杂性分析

1≤|≤关于我们- -《理论计算机科学电子札记》66卷第1期（2002年）网址：http://www.elsevier.nl/locate/entcs/volume66.html12页关于0J-可计算实数George Barmpalias乔治·巴姆帕利亚斯1，2英国利兹大学数学学院摘要给定一个0J-可计算实数x，我们感兴趣的是集合Az=i：zix}<我们感兴趣的是这些集合的相对复杂性（相对于强约简）。首先，不难证明1.感谢我的导师 S。B. 库珀对他的支持，以及裁判对有关论文陈述的2电子邮件地址：georgeb@amsta.leeds.ac.uk2002年由ElsevierScienceB出版。 诉 操作访问根据C CB Y-NC-N D许可证进行。臂甲鲶2XX≤命题1.1如果x是0J-可计算的，则存在一个（可计算的）序列z趋向于x，Az无限且共无限。从现在开始我们只考虑这样的序列，我们用字母z，w来表示它们;limz，limw是它们的极限。对于给定的实数x，考虑所有这样的集合，并以强约简≤r对它们进行排序，我们得到：到与实数相关的度结构Dr这个结构证明了的图灵度内的所有r-度之一的子结构，X.直觉上，这种结构的性质给出了关于实数的信息。特别是，如果它是丰富的，这意味着有许多不同的方式来近似x。如果是穷人，例如。由唯一的m-度组成（如定理2.3），那么所有近似x的方法看起来都非常相似。 我们注意到，对于各种z，所有的Az都包含关于x的相同信息，其中lim z = x（见命题2.1）。 不同之处可能是这些信息以不同的方式排列。这是当Az/rAwfor limz = limw =x时的情况。如果Az#rAw，从Aw的角度来看，Az中的信息被重新排列了很多，以至于一个强大的预言程序（基于#r）不足以从Aw解码Az。集合Az（对于一个序列z，其中lim z = x）可以被看作是x的一种“表示”或“表示”，这是一个在现代可计算分析中非常流行的术语。实数的表示可以用许多不同的方式来定义，例如[2]，[3]和[10]中的一般“表示理论”（不限于实数）。此外，关于实数表示的递归理论（在某些情况下是度理论）分析的工 作 已 经 完 成 ， 例 如 Calude ， Coles ， Hertling 和 Khoussainov[2] ，Downey，Laforte [3]，Soare[9]。我们注意到，还没有人对我们正在研究的那种表示做过任何工作，但他们的研究似乎引起了一个很好的结果。0J-可计算实数的分类最后一项索赔的证据在于结构Dr的多样性（x的表示的结构，r）for different realsx.与现有学位工作的联系（其他）表示（无论如何，这是定义的，例如[2]）似乎并不琐碎，它们肯定是进一步研究的良好动机。本文的第二部分讨论了这些集合的免疫性质我们表明，这些集的免疫性质是大致相同的所有不可计算的现实。特别是，这种豁免问题并不提供关于特定真实的信息。然而，这些结果是令人满意的，因为它们是一般性的：例如，超超免疫从未发生，而超免疫总是以这样或那样的方式存在（见定理4.1，推论4.4）。作为参考，我们给出以下内容定义1.2一个实数x称为可计算的（c.e.或左可计算），如果它是一个可计算的有理数递增序列的极限;它被称为co-c. e。（或右可计算），如果它是可计算的有理数递减序列的极限臂甲鲶3≤R产品介绍注 1 我 们 写 h-immune 和 hh-immune 分 别 表 示 hyperimmune 和hyperhyperimmune。我们所说的半可计算是指c. e。或co-c.e.实数的次数是它的二进制展开的次数，当它被看作一个集合时。对于可计算分析的背景和术语，我们参考例如。第一章：李白和李白的故事Soare[7]和Odifreddi[5]涵盖了本文中使用的可计算性（即递归）理论（假设对优先级参数有一定的了解）。2Az的度数我们考虑的情况下，lim z = lim w = x的两个可计算序列的有理数z={zs}，w ={ws}。不难证明命题2.1Az，Aw无限元和共无限元AzTAwTx一个问题是这是否适用于更强的可约性（例如wtt-度）。当然，答案取决于x的图灵度的性质;例如，如果deg（x）包含唯一的wtt-度，则命题2.1对wtt-度成立。下面的定理否定地回答了这个问题3。定理2.2对于可计算序列z，w和Az，存在满足limz = limw = x的实数x|wttAw.在另一个方向上，我们提出以下未经证明的定理2.3（Barmpalias[1]）存在不可计算的c.e. reals x与属性limz = limw =xAz，Awco−infinite⇒Az ≡mAw这两个定理的对比（尤其是第二个定理的极端）表明，Sx={Az：limz=x<$Azinfinite andco−infinite}由强约简器排序的r4可以根据实际情况X. 这使得对这些结构的研究变得有趣，也激发了对这些结构的研究。以下定义2.4对于每个实数x，我们赋予其度结构Dx={degr（A）：A∈ Sx}关于强约简r（=m或wtt）。这个定理对xc. e也成立Barmpalias[1].[4]我们可以证明（Barmpalias[1]）tt²x=m²x，即tt-约化和m-约化在这样的类上是一致的。臂甲鲶4X根据命题2.1，Dr 是一个子结构的一个所有的x的图灵度中的r-度。3定理2.2证据是一个有限的伤害论点。3.1关于建设我们的要求很简单R2e：<$[Φe（Az）=Awwithbound <$e]R2e+1：<$[Φe（Aw）=Azwith bound <$e]其中（Φ e，Φe）是值在{0，1}中的部分可计算泛函和部分可计算函数的所有可能对的有效枚举。我们采用通常的约定，即如果Φe（A，n）在阶段s定义，则e，n，Φe（A，n）以及计算的使用都小于s（对于Φe也是类似的陈述）。R2e和R2e+1是对偶的，并且以相同的方式满足。所以我们稍后可以关注R2e，这里有两个问题.首先，我们被迫在构造过程中继续定义z和w的项，而不会因某些要求的行为而导致任何延迟因此，如果我们x固定（但任意），这样的构造似乎是不可能的，因为一旦我们定义了一个项zi，我们就自动确定（永远！）是否i∈Az，因此我们无法根据Re的行为改变我们的想法（如在任何典型的优先构造中）。这样的构造确实是不可能的，因为在引言中有一个注释（当deg（x）包含唯一的wtt-度时的情况）。但幸运的是，我们实际上可以在构造过程中构建一个合适的x，这使得我们可以在需要时改变对i∈Az的看法，换句话说，尽管我们可能已经定义了zi，但我们可能还没有最终决定x是在zi的右边还是左边。 所以我们有一个参数βizi（对于wi ，类似地，i= z i），其在构造期间在0和1之间改变值（根据x >zi还是xzi）。在特定阶段之后，βi，βi将停止变化（limsβs =βi和limsβs =βi），并且极限βi，βi，我我随着i的增加，将确定x在单位间隔中的确切位置在我们解决了这个问题之后，仍然存在一个困难;即，我们在构建过程 这是因为我们对x是在zi或wi的右边还是左边的“猜测”必须在每个阶段s都是一致的;换句话说，如果它发生了，例如， zi> zj我们不能在任何阶段都把βi= 0和βj= 1。因此，改变βi或βi的动作可能会迫使其他项的参数发生变化（由于我们要求保持猜测始终一致）。 这个问题可以通过为Re选择合适的见证人以及稍后描述的Re策略来解决。特别是，我们使用的事实，如果例如。wi∈ In（见定义3.1），则当j≤n时，βi的变化不会迫使βj，βj发生任何变化。我们有臂甲鲶5en我们的团队我e2e2e2e2e2e2e2e2e2e2e2e ↓我我2e2e2e2e2eβi= 0zi∈Azwi∈Aw我们从列Ne=e，t：tN中为Re选择见证人xe，并将其改变无限次，直到找到合适的见证人（在阶段s，当前见证人是xs）。在每个阶段，我们都有Re的约束r（e，s），并且limsr（e，s）=r（e）。此外，R（e，s）=max{r（i，s）：ie}是Re在阶段s必须遵守的约束（并且R（e）= limsR（e，s））。我们注意到，我们对Az和Aw都有一个约束;这是因为将元素放入Az通常会（直接）影响集合Aw（反之亦然）。最后，我们将注意使项zi，wi在越来越小的嵌套区间中累积，这一事实给出了z，w收敛到唯一的实数x。定义3.1In=（an，bn）其中an=max{zi，wj：i，j≤n<$βi=0，<$j=0}bn=min{zi，wj：i，j≤n<$βi= 1，<$j = 1}区间Is的定义类似，将上述参数代入它们的s-近似值（用第s级近似，例如βi用βs近似）。此外，我们说，我们修改In，使y∈In，当我们把βi=0，如果zi y，j= 1，如果wj> y，对所有i，j ≤ n。当然，当我们说，例如，我们把βi= 0（在一个特定的阶段s），我们的意思是，我们定义βs= 0。换句话说，Is是猜测区间，I n我们相信，根据s-猜测（在阶段s可用），zi，wi，i≤n关于x的位置（如果对所有i≤n，βs=βs= 0，我们设Is=（0， minzi，wi：i≤n），类似地，在对偶情况下，我们通过n n①的人。如果一个参数（例如，xs）在s+1阶段没有重新定义，则它保持其最后一个值（xs+1=xs）。e eR2e的策略我们直接使用约束条件;假设一个当前见证xs。有两个部分的战略，当第1已经执行（为当前证人）我们设置R1↓（否则R1（2）当第二完成时，我们设置R2↓（否则R2↑）。部分1. 我们等待直到e（xs）↓（如果这永远不会发生，e就不是总数）。 然后我们修改Ie（xs），使wxs ∈Ie（xs）. 注意wxs 已经被定义，因为<在阶段s，我们定义zs，ws。 我们还设置r（2 e，s）= e（xs），保护关系wxs ∈Ie（xs）（完成第2所需成功地）在后期阶段。 一旦我们完成了第1部分（因此R1↓），我们想完成部分2. 我们等待直到Φe（Az;xs）（如果这永远不会发生Φe（Az）是部分的）。当这种情况发生时，检查这个计算的使用是否受限制，如果不是，我们设置r（2e，s）=u（e，Az，xs，s）来保护计算。2e2eX臂甲鲶62e2e2e2e2e2e2e2eeeR（e，s）SSeR（e，s）e2e2eeeee2然后，我们有证据的满意度R2e，因为特定的计算是没有适当的限制。否则设置s s sAw（x2e）= 1 − Φ e（Az; x2e）（即 xs = Φ e（Az; x2e））对所有i，j≤szi，wj≤wxszi，wj≥wxs美国海军陆战队美国海军陆战队= 1βi =j= 1=0βi=j = 0从而在xs保持猜测的一致性请注意，第2部分的操作并不强制对（参数）进行任何更改的）以下的项（即βi，对于i≤e（xs）的i）;这是因为2e2e在第1部分中，我们注意到，∈ Ie（xs）. 因为，既然，如果计算Φe（Az;xs）↓受Φe（xs）的限制，则计算不会2e2e被我们的行动所影响我们还设置S s(1)r（2e，s）=max{u（e，Az，x，s），x}以保护计算以及分歧的证据R2e+1的策略类似于上面描述的策略（将z替换为w（反之亦然），2e与2e +1和β与β（反之亦然））。当然，每次我们对Re采取行动时（根据策略的第1部分或第2部分），我们必须尊重更高优先级的要求;因为任何行动都可能迫使改变Az，Aw，并可能改变受ie约束的元素。我们通过选择合适的证人来解决这个问题。xs的选择见证人xs将对Re起作用，因此它必须考虑R（e，s）。S s特别地，我们必须总是在任何阶段s+1 =xe（in）有z xs，wxs∈IR（e，s）换句话说，当zs+1，ws+1在阶段s+1定义时，S s是需求Re（s +1 = xe）的当前见证，则zxs，wxs∈ IR（e，s））。这样，当对Re采取行动时，更高优先级的将不会被违反。对于最后一种关系，有εs∈ zs+1，ws+1∈ Is。 在阶段s +1，我们对x的最佳猜测是located是区间Is，因此，除非某些Re，es作用于s，否则我们定义zs+1，ws+1在Is中（例如，我们将其分为3，并将zs+1作为结尾第一部分结束时，ws+1为第二部分结束时）。 请注意，我们总是有R（e，s） s]1e公司e，s↑3. R↑，R臂甲鲶7eR（e，s）R（e+1，s）SR（e+1，s）R（e，s）R（e1+1，s）I↓R为了简化验证，在此对这个定义作一些解释是值得的。当我们根据2定义xs时。在上面，zxs，wxs仍然是unfined。当他们在那里的时候，他们就在那里。e eR（e，s）已经改变，在这种情况下，相同的过程将发生在新的证人）。现在，在一些Re，e1+ 1，则r（i，s）= 0，因此R（i，s）=R（e1+1，s）。更多关于建筑根据对策略的描述，我们说Re需要注意在以下两种情况下，在阶段s(i) R1e，s−1 ↑和e（xe）[s−1]↓(ii) R1e，s−12e，s−1↑和Φe<$（Az;xe）[s−1] ↓其中，当e为2t或2t+ 1时，e=t(as表达式前面的usual [s]表示表达式的s-近似与（i）相关的行动在上述战略的第1部分中描述（例如，当e偶数时），第2部分的行动针对（ii）。当一个行动是为了Re而进行时，我们说这个要求受到注意。3.2建设stage 0初始化所有Re并定义z0=1，w0=2。3 3s+1期臂甲鲶8我s+1eee∈Se公司Se公司Se公司Se公司步骤A定义Is如果在s处没有采取动作，（a，b）=sSR（e+1，s），如果Re作用于s且zs+1，ws+1在（a，b）中;特别地，定义zs+1 =a+b−a32ws+1=a+3（b−a）设βsss+1 = 0，除非它们的值由上下文指定（即zi，wi，i≤s）。步骤B寻找需要注意的最小Re（e s），并执行相关操作（在前一节中描述）。初始化所有Ri，i> e。3.3核查引理3.2对于所有e[limR1 = limR2=↑][limR1=↑ ± limR2=↓][limR1 = limR2=↓]S和e公司se，s• 最小值sxs=xe• R（e，s）=R（e）• 如果e是偶数，则<$[Φe <$（Az;xe）=Aw（xe），有界<$e]• 如果e是奇数，则<$[Φe <$（Aw;xe）=Az（xe），有界<$e]证据 很容易看出，在每一个阶段，我们的猜测都是一致的（所以Is有意义）。 我们证明引理归纳，假设它适用于所有的i s0。在对R i执行最后一个动作之后，<即，xe被重新定义，使得wxeIR（e）和从那时起xe，IR（e）保持（并且将保持）恒定（由于归纳假设）。现在我们考虑以下情况R1↑，R2↑（在s0时）。如果这是永恒的，那么我们就结束了。ee否则，我们就像在下面的案例中那样进行论证。R1↓，R2↑（在s0），则R1↓发生在对某个Ri，i执行最后一个动作s0zs，ws∈Jn且limn|JN|=0。 我们将只描述如何从一个项Jn传递到它的后继项Jn+1。 考虑一个IR（e0）= Jn和s0，使得εs >s0，没有Ri，i≤e0作用于s（所以R（e0）= R（e0，s））。取最小的e1> e0，使得Re1在s0之后作用;s1是R（ e1）最后一次作用的阶段。它是R（ e1）= R（ e1，s），其中s >s1，且IR（e1）<$IR（e0）（因为R（e1）≥R（e0））。在s1+ 1，zs1+ 1，ws1+ 1将把IR（e1）分成三部分，在βs1+ 1之后，ws1+ 1取它们的最终值（根据引理3.3，假设阶段s2），所有zi，wi，i>s2将位于IR（e1）的三分之一，长度至多为1的区间Jn+1|IR（e）|. 继续（对于Jn+2的定义）取e2，R（e2）>s1+ 1和s3使得Ri≤e2Ri继续就像我们从IR（e0）开始一样。✷4免疫特性我们感兴趣的是，依赖于x，上述集合有多免疫。人能证明臂甲鲶10/定理4.1（Barmpalias[1]）如果x不是半可计算的，则Az，Bz是h-免疫的，而不是hh-免疫的.如果x是c。不可计算，则Az是h-单的，如果是co-c.e。则Bz是h-单的。(it很容易看出xc. e. Azc.e.）。一个很自然的问题是Az或Bz对于半可计算实数是否可以是hh免疫的（我们对于非半可计算x的证明不能适用于这种情况）。我们证明这是不可能发生的。事实上，我们证明了一些更强的东西，即（例如对于xc. e的情况）z不可能是fsh（finitely strongly hyper）-simple（这是一个比hh- simplicity弱的性质作为参考，我们给出以下内容定义4.2（Soare[8]）一个集合D是有限强换句话说，如果Wg（n）是这样的数组，则n[Wg（n）<$D=n]。 B是fsh-简单的，如果它是c.e. 而N-Bz是fsh-im mune。定理4.3如果x是c.e.则Az对任何可计算有理数序列z ={zs}，且limz = x都不是fsh-单的.注意，定理4.3的对偶版本对于co-c. e成立类似的证明（similar上述结果与定理4.1一起给出推论4.4若x = lim z，对于z ={zs}可计算有理数序列，则Az，Bz不是hh免疫的.定理4.3的证明是一个递归理论（有限伤害优先）的论证，没有任何对角化。我们用这个证明背后的想法的草图来结束这篇论文4.1关于定理4.3的证明。我们想定义一个弱数组Wg（t），它表明Bz不是fsh免疫的。这个想法是试图在x的右手侧安装一系列标记yi和见证人wk= zik，并同时吻合z的项（的索引）的枚举，使得以下成立：X... y）。在这种情况下，我们说，ys（或yi）受伤（在阶段s1）。 根据我们留下它被定义为;在符号ys1↑中。 现在我们让ws依赖于ys。我我我4.5定义ws= max{zt：t≤s<$zt i。这意味着我们对所有j> i设置ys↑，σs↑。这就结束了证明的草图该定理的完整证明，包括形式构造和验证，可以在Barmpalias[1]中找到引用(1) G. 李文，关于0J-可计算实数的若干定理，未发表的草稿.(2)C. S. 卡卢德河Coles，P.H. Hertling和B.库赛诺夫可计算可量化实数的度InS. B.库珀和J. K。特拉斯，臂甲鲶12编辑，模型和可计算性，伦敦数学学会讲义系列第259卷，第23-39页，剑桥，1999年。北京大学出版社. 1997年逻辑学术讨论会邀请论文，利兹。(3)G. L. L. Rod Downey，G.L. 拉福特 可计算实的表示。DMTCS-135，离散数学与理论计算机科学中心，2000年。(4)C.- K. 何，相对递归实数和实函数，理论计算机科学，210（1999）99(5)杨文，(6)M. B. Pour-El和J.I. Richards，柏林伦敦：施普林格，1989年(7)R. I. Soare，Springer-Verlag，1987(8)R.I.Soare，计算复杂性，可加速和可水平集，J。符号Log. 第41（1977）号来文，第545(9)R. Soare.递归理论和戴德金切割。美国数学学会，140：271 - 294，1969.(10)K. 魏劳奇，可计算分析，北京：清华大学出版社，2000