可计算逼近实数的边界函数和数学性质分析

理论计算机科学电子笔记167（2007）325-344www.elsevier.com/locate/entcs可计算近似的发散边界分类1西中正2江苏大学计算机科学系，江苏镇江212013。Theoretische Informatik，BTUCottbus D-03044 Cottbus，Germany摘要一个实数称为可计算逼近的，如果有一个可计算的有理数序列收敛到它，为了研究可计算逼近实数的复杂性，我们可以考虑序列的收敛速度本文介绍了一种自然的方法，通过计算在一定阶段后出现的一定大小的跳跃来测量收敛速度这种大跳跃的次数可以由边界函数来限定对于边界函数的不同选择，我们引入了不同逼近性质的实数类，并讨论了它们的数学性质和可计算性理论性质.保留字：可计算实数;可计算逼近;收敛速度;层次。1引言实数可以用许多不同的方式表示。例如，它们可以用柯西序列、十进制展开式、二进制展开式或戴德金割等表示。对于数学来说，所有这些表示都是等价的，因为它们推导出相同的实结构（所谓的戴德金完备有序场）。然而，如果我们对实数和实函数的可计算性感兴趣，实数的表示的选择确实起着重要的作用。第一个定义1 本工作得到DFG（446 CHV 113/240/0-1）和NSFC（10420130638）的支持。2电子邮件：zheng@informatik.tu-cottbus.de1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.08.019326X. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）325图灵[10]的可计算实数的可计算性是建立在十进制展开的基础上的。正如Robinson [8]、Myhill [6]、Rice [7]和其他人所指出的，实数的所有经典表示都导致相同的可计算性概念和图灵的一样。然而，对于实函数的可计算性，情况完全不同。例如，加法函数是可计算的，正如我们对柯西表示的预期。但它是不可计算的相对于十进制表示（见Weihrauch[11]）。实际上，正如[11]所示，柯西表示导致了实空间可计算性的最自然的概念，并被认为是可计算分析的实数的标准表示因此，一个实数被称为可计算的，如果它有一个可计算的柯西表示。这里，实数x的柯西表示是一个有理数序列（xs），它在以下意义下逐次收敛于x：（n∈N）（n，t≥n）（|xs−xt|≤2−n），（1）和有理数序列（x s）是可计算的意味着有三个可计算函数a，b，c：N→Nsuchthatxs=（a（s）−b（s））/（c（s）+（1）所有S。一个（可能是部分的）实函数f：R→R称为com-假设存在一个等价过程（所谓的Type-2图灵机），它将任意x∈dom（f）的柯西表示转换为f（x）的柯西表示。基于柯西表示的实数的可计算性可以用几种等价的方式定义。例如，x是可计算的，当且仅当存在一个可计算的有理数序列（xs），使得（n∈N）（|x−x n|≤ 2 −n）。（二）条件（1）和（2）是等价的，即给定一个满足一个条件的序列，我们可以有效地构造一个新的序列，该序列具有满足另一个条件的相同极限我们更喜欢使用条件（1），因为它不直接包含极限x。然而，条件（2）更清楚地表明了实数x的可计算性的本质。也就是说，给定任何误差界，比如2−n，我们可以有效地找到xn到x的有理逼近。根据这一原理，可计算实数可以用更一般的方式等价地定义：实数x是可计算的，当且仅当存在一个可计算的有理数序列（xs）和两个可计算函数e，d：N→N，使得d是无界的和（n∈N）（ns，t≥e（n））.|x s− x t|≤Σ1d（n）.（三）在这种情况下，函数e和d被称为模函数和距离X. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）325327函数的序列（xs），分别。没有条件（1），（2），（3）或其他等价条件，极限x称为可计算逼近的。 正如Specker [9]所示，并非所有可计算的可近似实数都是可计算的。如果x是不可计算的，那么对于任何收敛到x的可计算有理数序列（x s），将存在指数对（s，t）到（3）的一些例外这种异常的数量取决于n，它可以用一个函数表示这个函数描述了序列的收敛质量，称为序列的（e，d）-发散度发散度是极限x的复杂性的自然度量。如果（e，d）-发散度由函数f限定，则称x是（f，e，d）-e可迭代计算的。我们将看到，模函数e在这个定义中实际上并不起作用，因此我们可以将模函数e固定为恒等函数id（n）=n。（f，id，d）-e可迭代计算的实数简称为（f，d）-e可迭代计算的。此外，对于任意可计算距离函数d，当指数函数ep（n）= 2n和一个新的边界函数g时，（f，d）-有效可计算性可归结为（g，ep）-有效可计算性. （f，ep）-e迭代可计算实数简称为f-e迭代可计算实数. 对于一类函数C，我们称一个实数C-e是有效可计算的，如果它对于C中的某个函数f是有效可计算的。本文研究了不同函数f的f-e可计算实数的性质。特别地，我们将证明常函数f的Ershov式层次定理和可计算函数f的一般层次定理，该定理断言，如果可计算函数f f和g在无限多的地方是不同的，那么有效的可计算性和有效的可计算性是不同的。此外，对于非常自然的函数类C，我们证明了C-e可计算实数类在算术运算下是封闭的，因此是域。本文所引入的f-有效可计算性实际上是文[13]中的f-柯西可计算性和文[12]中的f-有界可计算性的一种改进它们之间的区别在于对应该被计算在内的大跳跃的定义。与有效可计算性不同，有效可计算性是一个重要的问题。柯西可计算性计算了在阶段n之后出现的大小在2−n和2−n+1之间的跳跃，而所有大于2−n的跳跃都将被f考虑。有限可计算性已经证明，f-柯西可计算性有一个很好的层次定理.但由f-柯西可计算性定义的实数类通常不具有良好的数学性质。例如，对于常数函数f，所有f-柯西可计算实数的类在加法下不是封闭的另一方面，328X. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）325由f-有界可计算性导出的实数的可计算性具有更好的数学性质。然而，没有一个Ershov式的层次的f-有界可计算性，虽然有一个一般的层次定理，f-有界可计算性是不同的，从g-有界可计算性，如果函数f和g有一个无界的距离。而且，可计算实数类也不能用f-有界可计算性来描述.本文引入的f-有效可计算性具有f-柯西可计算性和f-有界可计算性的优点因此，它提供了一种更自然的方法来接近可计算逼近实数的复杂性。本文的组织结构如下。在第2节中，我们通过界定发散度来定义有效可计算性的三个不同版本，并讨论它们之间可能的约简第三节讨论了常数函数f的有效实数类，并证明了一个Ershov层次定理.第四节研究了有限可计算实数类，证明了一个一般的层次定理。最后，我们在第五节中考虑了C-有效可计算性，证明了C-有效可计算实数类是一个域，如果C包含所有常数函数，并且在复合下闭。2有效可计算性的定义在本节中，我们将给出本文中讨论的主要概念的精确定义首先定义了（f，e，d）-有效可计算性的最一般概念然后，我们解释，如何这个概念可以减少到一个更简单的概念，有效的可计算性在两个步骤。因此，以后只能研究有效可计算性。我们的目标是分类的可计算逼近实数根据有多快，他们可以被近似。为了衡量序列的收敛速度，我们考虑超出有效界的“大”跳跃的数量回想一下，实数x是可计算的，如果它可以用有效的误差估计有效地近似，我们用EC表示所有可计算实数的类因此，给定任何误差ε>0，我们可以在此误差范围内有效地找到x的近似xs|≤ε。| ≤ ε. x的有效逼近通常由收敛于x的可计算有理数序列（xs）给出。因此，x的可计算性实际上需要一个有效界e，使得没有s≥e，|x−x s|>ε，或者等价地，没有s，t≥e，|x s−x t|>ε。 在e之后的对（s，t）使得|x s− x t|> ε是无爱的“大跳跃”，它可以摧毁X. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）325329SSx的可计算性一个可计算序列的跳跃越大，其极限的可计算性就越小。为了更精确地描述边界e对误差ε的依赖性，对于无界函数d：N→N和自然数n，误差将由1/d（n）给出。 然后，实际上依赖于n，并且可以表征为函数e：N→N。函数d和e分别称为距离函数和模函数。对于任何序列（xs），在阶段e（n）之后的非重叠大跳跃（大小大于1/d（n））的数量由v（n）表示。功能v称为序列（xs）的发散度（关于e和d函数v、e和d提供了关于如何有效地近似实数的最重要的信息。这就引出了我们的第一个定义。定义2.1设f，e，d：N→N为函数。(i) 序列（xs）的（e，d）-发散度是函数v，使得v（n）等于非重叠索引对（s，t）的数目，使得s，t≥e（n）.Σ1|> d（n）|>d(n).（四）(ii) 一个可计算序列（xs）（f，e，d）-e渐近收敛于x，如果（xs）的（e，d）-发散度v由f有界.(iii) 一个实数x是（f，e，d）-e递归可计算的（简称（f，e，d）-ec），如果存在一个可计算的有理数序列（xs），它使（f，e，d）-e递归地收敛到x。所有（f，e，d）-EC实数的类记为（f，e，d）-EC。一般来说，一个函数v被另一个函数f约束意味着对所有n，v（n）≤f（n）。对于定义2.1。（ii）和后面的定义，它要求发散度v几乎处处由f约束v（n）≤f（n）对几乎所有的n成立。原因是，如果一个可计算序列的发散度v几乎处处受f约束，那么显然存在一个新的具有相同极限的可计算序列，其发散度（完全）受f约束因此，我们在本文中不明确区分这两种情况。只考虑无界距离函数d是非常自然的。反之，对所有n，证明d（n）≤N.然后，对于任何可计算收敛序列（xs），我们可以通过xJ定义一个新的可计算序列（xJ）：=xN为s s1所有s≤N1且xJ：=xs fors> N1，其中N1是最小自然数n（1）（2）（3）（4）（5）（|x s− x t|≤ 1/N）。这个序列（xJ）收敛于（0，e，d）-对于任何模函数e， 因此，有界距离函数是330X. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）325S毫无意义 此外，我们也只考虑了无界模函数因为有界模函数没有多大意义。对模和距离函数的另一个自然限制是它们应该是非减的。因此，本文只考虑无界非减模函数e和距离函数d. 即使在这种限制下，（e，d）-发散度v仍然可以是非单调函数。然而，由于我们只对限定函数v的边界函数f感兴趣，所以当我们讨论实数的（f，e，d）-等价可计算性时，我们还假设函数f也是非减的。引理2.2设f，e，d：N→N是非减函数，使得e，d是无界的。如果e是可计算的，则实数是（f，e，d）-e可计算的，如果id（n）= n，则实数是（f，id，d）-e可计算的。证据 设x是一个（f，e，d）-等价可计算实数. 那么是一个可计算的有理数序列（xs），它收敛于（f，e，d）-即与x对应。显然，由xJ定义的可计算序列（xJ）* =xe（s）S s（f，id，d）-e依序收敛于x。另一方面，假设（xs）是一个可计算的有理数序列，它使（f，id，d）-e渐近收敛于x。设e是可计算的非减无界函数。通过v0：= 0和vn+1：=（μt > v n）（e（t）> ） 归 纳 地 定 义 自 然 数 的 递 增 可 计 算 序列（v s）。e（vn））。 然后我们有e（v n）= e（s）对任何n和v n≤ s d（n）|>d(n).（五）(ii) 一个实数x是（f，d）-e递归可计算的（简称（f，d）-ec），如果存在一个可计算的有理数序列（xs），它（f，d）- e递归收敛于x。所有（f，d）-ec实数的类表示为X. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）325331（f，d）-EC。因此，实数x是（f，d）-e可迭代计算的，当且仅当它是（f，id，d）-e可迭代计算的。在这种情况下，函数d决定了“大跳跃”的大小函数f和d共同揭示了（f，d）-可迭代计算实数的复杂性信息。稍后我们将看到，不同的函数f，d导致不同的（f，d）有效可计算性。也就是说，它们不能进一步减少。通过定义，如果对几乎所有的n，f1（n）≤f2（n）且d1（n）≥d2（n），则任何（f1，d1）-e可迭代计算的实数也是（f2，d2）-e可迭代计算的。在边界函数f和距离函数d之间，我们可以显示关于（f，d）-有效可计算性的折衷现象我们首先解释一些关于反函数的符号。对于一个无界的非减函数h：N→N，我们可以用下面两种不同的方法定义它的反函数。h−1（n）：= min{t∈N：h（t）≥n};h−1（n）：= max {t∈N：h（t）≤n}。函数h−1和h−1分别称为h的上逆和下逆函数。对于一个无界的非减函数h，它的上下反函数都是非减的。此外，它们还具有以下性质，这些性质直接来自定义。命题2.4设h：N→N是无界非减函数.然后我们有(i)（n∈N）（h<$h−1（n）≥nh−1<$h（n）≤n）;(ii)（n∈N）（h<$h−1（n）≤nh−1<$h（n）≥n）;(iii) （<$n∈N）（h<$h−1（n）=nh<$h−1（n）=n），如果h是满射;(iv) （<$n ∈ N）（h−1<$h（n）= n &h−1<$h（n）= n），如果h是单射的。引理2.5设f，d是非减函数，d是无界的. 如果h是一个无界非减可计算函数，则我们有(i)（f<$h−1，d）-EC<$（f，d<$h）-EC<$（f<$h−1，d）-EC;(ii) （f，d）-EC（fh，d h）-EC。证据（一）.对于第一个包含，设x是一个（fh−1，d）-e可计算的实数。存在一个可计算的有理数序列（xs），它使（fh−1，d）-e依序收敛于x。 也就是说，对于几乎所有的n∈N，非重叠索引对（s，t）的数量使得s，t≥n，|> 1 /d（n）由f h −1（n）有界。|> 1/d (n) is bounded by f ◦ h−1 (n). 定义一个可计算序列332X. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）325（ys）的有理数由ys：=xh（s）对于所有s。序列（ys）也收敛到x现在我们证明这个序列是（f，dh）-e渐近收敛的。给定一个n，如果（s，t）是一个指数对，使得s，t ≥ n，|y s−y t|>dh（n），则有h（s），h（t）≥h（n），|x h （ s ）−x h （ t ）|>dh（n），因为h是一个非减函数。通过序列（xs）的（f<$h−1，d）-等价收敛，这样的非重叠对（h（s），h（t））的个数由f<$h−1（h（n））限定，根据命题2.4的第二部分，f<$h−1（h（n））又由f（n）限定。（i）和f的单调性。由于h是非减的，对于具有上述性质的每一对（h（s），h（t）），存在两个不相交的自然数区间[s1，s2]和[t1，t2]，使得对任意SJ∈[s1，s2]和TJ∈[t1，T2]，h（s）=h（SJ）和h（t）=h（tj所有这些对（sJ，tJ）彼此重叠。这意味着，最多有f（n）个非重叠索引对（s，t），s，t≥n，|y s−y t|>dh（n）.也就是说，序列（ys）（f，dh）-e迭代收敛于x，因此x是（f，dh）-e迭代可计算的。对于第二个包含（i）， 设x是一个（f，d）-可计算实数，（xs）是一个可计算有理数序列，它将s（f，d）-可计算化为x. L etys：=xh−1（s）. 我们要去商店可计算序列（ys）迭代收敛于（fh−1，d）-e。对于给定的n，令（s，t）满足s，t ≥ n，|y s−y t|> 1/d（n）。 由h−1的单调性和不等式n≤h <$h−1（n），我们有h−1（s），h−1（t）≥h−1（n）和nd|xh−1（s）−xh−1（t）|>1/d（n）≥1/d<$h<$h−1（n）。 通过序列（x s）的（f，d<$h）-等价收敛和h −1的单调性，这意味着可计算序列（ys）（f <$h−1，d）-等价收敛于x，因此x是（f<$h−1，d）-等价可计算的。(ii). 它类似于（i）的证明Q因此，我们讨论了可能不可计算函数f和d的实数的（f，d）-等价可计算性。然而，如果涉及到跳跃的次数，则跳跃的大小应该被有效地给定是一个非常自然的要求在下文中，我们主要对可计算的距离函数d感兴趣，而边界函数f仍然是不可计算的。下面的引理表明，任何可计算的距离函数都可以简化为单位距离函数。引理2.6设f是一个非减函数。如果d是一个可计算的无界非减函数，则我们有（f，d）-EC =（f <$d−1，id）-EC。证据第一，引理2.5。(ii)我们有（f，d）-EC<$（f<$d−1，d<$d−1）-EC。这意味着包含（f，d）-EC<$（f<$d−1，id）-EC，因为不等式d<$d−1（n）≥n。包含的另一个方向（f<$d−1，id）-EC<$（f，d）-EC直接由引理2.5得出。（一）.QX. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）325333引理2.6表明，如果对可计算距离函数d考虑（f，d）-等价可计算性，则对不同函数f只考虑（f，id）-等价可计算性。然而，由于在很多证明中的简单性，我们更喜欢使用距离函数ep（n）：= 2n而不是恒等函数id。由于下面的引理，这并没有从本质上改变问题。引理2.7设f是一个非减函数。我们有(i) （f，id）-EC=（f，ep，ep）-EC;(ii) （f，d）-EC =（f <$d−2，ep）-EC对于任意无界非减可计算函数d，其中d−2（n）：= d−1<$ep（n）= min {t：d（t）≥ 2 n}。证据（i）包含（f，id）-EC（fep，ep）-EC可以直接从引理2.5得到。（二）.对于 包含 的另一 个方向 ， 我们有 （fep，ep）-EC=（f ep，idep）-EC（f(i))n（f，id）-EC（由于ep∈ep−1（n）≤n）(ii)由引理2.6，我们有（f，d）-EC=（f<$d−1，id）-EC对于任何无界非减可计算函数d。第（i）项，我们有（fd−1，id）-EC=（fd−1ep，ep）-EC。因此，（f，d）-EC=（f<$d−2，ep）-EC。Q在下文中，我们只考虑可计算距离函数。根据引理2.7，实际上只需要考虑距离函数ep（n）：= 2n。这导致了以下定义。定义2.8设f：N→N是一个非减函数。(i) 一个序列（xs）f-依序收敛，如果对几乎所有的n∈N，至多有f（n）个不重叠的指标对（s，t），使得s，t≥n&|xs−xt|>2−n。（六）(ii) 一个实数x是f-e迭代可计算的（简称f-ec），如果存在一个可计算的有理数序列（xs），它使f-e迭代收敛于x。所有f-可计算实数的类记为f-EC.因此，一个实数是可计算的，当且仅当它对于常数函数f∈0是f -e可计算的，或者简单地说，它是0-ec。对于一个函数类C，一个实x称为C-e迭代可计算的，如果它对于一个函数f∈C是f-可计算的。所有C-e可迭代计算实数334X. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）3252表示为C-EC。下面几节将研究不同类C的C-EC的性质3恒定界限在本节中，我们讨论了常数函数f的有效可计算性。根据tradeo引理2.5和引理2.7，可计算距离函数在这种情况下不再起作用。也就是说，对于一个常数函数f，（f，e）-等价的可计算性不依赖于可计算的无界非减函数d的选择。因此，我们有以下引理。引理3.1设f为常数函数。(i) f-EC=（f，d）-EC对任意无界非减可计算函数d;(ii) f-ECg-EC 对于任何非减无界函数g。证据 它直接由引理2.7导出。（二）. 定义2.8设k为任意自然数，f∈k为常数函数。我们称一个f-e有效可计算的实数k-e有效可计算的或简称k-ec。 所有k-ec实数的类记为k-ec. 实数x称为有界等价可计算的（bec，简称bec），如果对于某个常数k，它是k-ec。 所有有界有效可计算实数的类是记为：=k∈Nk-EC。对于k-ec实数，我们有下面的层次定理，类似于自然数的Δ 0 -集的Ershov定理3.2对任意自然数k，存在一个（k + 1）-ec实数不是k-ec，即，k-EC=（k +1）-EC。证据k是自然数。我们将构造一个非k-ec的（k+ 1）-可计算实数.也就是说，我们构造了一个可计算的有理数序列（xs），它（k+ 1）-e渐近收敛于一个非k-ec实数x.因此，x必须满足以下所有要求：Re：（εe（s））s迭代收敛于ye= εx ye，其中（e）是所有可计算函数e的有效枚举：Q.为了满足一个单一的要求Re，我们选择两个距离为2−e的有理区间I1和I2。默认情况下，让x0是I1的中点。如果有一个s≥e使得xe（s）进入区间I1，则重新定义xs为区间I2的中点。如果在稍后的阶段t>s，则Δe（t）进入X. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）325335I2，然后让xt再次成为I1的中点，依此类推，我们最多允许k+1个这样的跳跃。这就保证了如果所构造的序列k-e渐近收敛，则该序列的极限x与lims→∞∈e（s）的可能极限为了同时满足所有要求，我们采用标准的有限伤害优先构造。 细节在此省略。Q关于k-e可迭代计算实数的算术运算，我们有如下结果.引理3.3设i，j，k为自然数。(i) 若x∈i-EC，y∈j-EC，则x + y，x-y，x·y，x/y∈（i + j）-EC。(ii) 在算术运算下，类E-EC这是一个领域。(iii) 存在一个k-ec实数x和一个1-ec实数y，使得x + y不是k-ec。因此，类k-EC在加法下不是闭的，因此不是场。证据（一）.设x∈i-EC，y∈j-EC. 存在可计算的有理数序列（xs）和（ys），它们分别依序和依序收敛于x和y这里我们只考虑乘积xy。其他业务的情况类似。选择一个常数c，|X s|、|y s|所有s ≤ 2 c。对于任何自然数s，t和n，如果|x s−x t| ≤ 2 −n且|y s−y t| 2-n，则有|≤ |X s|y s − y t||+的|y t |x s − x t||≤ 2 −（n −（c +1）） 。|≤ 2−(n−(c+1)).（7）定义一个可计算的有理数序列（z s），通过z s：= x s y s。这个序列显然收敛于xy。对于任意给定的自然数n，如果s，t是指数，且s，t≥n，使得|> 2 −（n −（c +1）），则我们 有|x s − x t |≥ 2 − n 或|ys − y t |2-n（7）。| ≥ 2 −nby (7).由于（x s）和（ys）分别依序收敛和依序收敛，因此这些性质的非重叠指数对（s，t）的数目由i + j限定。也就是说，序列（z s）收敛于（（i + j），λn。2n−（c+1））-e。根据引理3.1，xy是（i+ j）-e可迭代计算的。(ii). 它直接来自断言（i）。(iii). 我们可以构造两个可计算的有理数序列（xs）和（ys），它们分别k-e迭代和1-e迭代地收敛于x和y，使得它们的和x+y不同于任何k-e迭代可计算的实数。也就是说，x+y满足以下条件：Re：（ε e（s））s迭代收敛于ze= εx +yze.序列（xs）和（ys）的构造应用了标准跳跃336X. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）325法为了满足一个单一的要求Re，我们选择两个有理区间I1和I2，使得对于某个自然数，它们之间的距离为2−nn.默认情况下，设x0为I1的中点，y0：= 0。当序列（t）在阶段n之后进入区间I1时，我们将xs改变为I2的中点，而ys保持不变。如果序列（xe（t））稍后进入区间I2，则xs可以再次回到区间I1这种xs的跳跃最多允许k次。 在x s的k次跳跃之后，我们可以将y s增加或减少2 −n次，以迫使xs+y s的和离开区间I1或I2，这取决于序列（t）进入I1或I2。通过这种方式，我们保证序列（xs）和（ys）分别以k-e迭代和1-e迭代收敛但如果序列（t）ke收敛，则极限x+y与序列（te（t））的可能极限不同。为同时满足所有要求，我们采用有限伤害优先施工技术。Q现在我们比较k-等价可计算性和半可计算性.回想一下，一个实数x被称为左可计算或可计算（例如，如果有一个递增的可计算有理数序列（xs）收敛到x。实数x称为右可计算或co-c.e.，如果-x是c. e。左、右可计算实数称为半可计算实数。左、右和半可计算实数类分别用LC、RC和SC我们首先证明了半可计算实数类并不包含所有有界有效可计算实数。实际上，即使是1- e可计算的实数也不是半可计算的。定理3.4存在一个1-e可半计算的实数，它不是半可计算的。即1-EC和SC。证据设（εe）是所有部分可计算函数εe：εN→Q的有效枚举. 如果y是一个半可计算的实数，则存在一个e使得函数εe是一个单调全函数使得lims→∞εe（s）=y。现在我们要构造一个可计算的有理数序列（xs），它1-e依序收敛于x，并且x满足以下所有要求：Qe：（ke）是全单调的，lim_e（s）=y_e=xs→∞是的。满足单个要求的策略是相当简单的。 假设我们在年龄s0时定义了dxs0。 如果我们可以找到一个t>s0，这样我们就可以验证有限序列（xe（s））s≤t是递增的，并且0≤xs0−xe（t）≤2−e，那么我们就可以确定xt：=xs0−2−e。类似地，如果有限序列e（e（s））s≤tis递减，且d0≤e（t）−xs0 ≤2−e，thende fineX. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）3253370x t：= x s+2 −e。这就保证了所构造的序列（xs）的极限不同于可能的极限lims→∞e（s），如果e是单调函数。注意，在这个策略中，一个大小为2−e的表面的跳跃。为了同时满足所有要求，我们再次应用有限陪审团优先构造。这里唯一的问题是如何保证序列（xs）的1-e有效收敛根据上述策略，为了满足要求Qe，我们需要序列（xs）的大小为2−e因为元素xs是在阶段s定义的，这意味着，在阶段s之后，最多允许一个e≤s的需求Qe被该策略攻击。S.此限制可能导致某些要求无法满足。为了解决这个问题，我们定义了一个新的需求列表Re：R i，j：=Qi。也就是说，每个需求Qe将在列表中出现无限次。如果iiJ或i=iJ和j jJ，则要求Ri，j具有比r要求RiJ，jj更高的先验y。这样，所有的需求Qi都有无限多的机会被攻击，并且可以通过上面的列表（Re）策略来满足，尽管有些需求Re可能永远不会被攻击。Q现在我们将证明半可计算实数类不包含在有界有效可计算实数类中。实际上，甚至存在一个强的c.e.。一个没有界的有效可计算的实数。这里，根据Downey [3]，实数x是被称为ds tronglyc. e。 如果你不介意的话。 二进制扩展，即，有一个c.e。设置i+1）A<$N使得x=xA：=i∈A2−（.因此，类SC和类E-EC是无与伦比。定理3.5存在一个强c.e.对于任何自然数k都不是k可计算的实数x。因此我们有SC-EC。证据我们建立一个CE。设A∈N，使得强c.e. 实数xA满足所有e=i，j的所有要求：Re：（ε i（s））s迭代收敛于ye= εx A/= ye。为了满足一个单一的要求Ri ，j，我们选择j+ 1个不同的自然数a02−（n-k）通过f（x s）的k-e-ectiveconvergee。换句话说，至少有一个s ∈ [n-k，n]使得|x s− x s+1|≤ 2 −（n-k）。一般来说，对于任何i ≤ n-k，至少有i +1个指数s ∈ [n-k-i，n]，使得|x s− x s+1|≤ 2−（n-k-i）。 这意味着，有n-k个不同的指数s0，s1，···，s n-k，使得|xs−x s+1|对于所有i≤n-k，≤ 2 − i。选择一个常数c，|x s−x s+1|对于所有的s∈N，然后我们有卢恩s=0时克恩|x s− x s+1| ≤i=0时|xsi — i+1|+ ck≤克恩i=0时2 −i+ ck ≤ 2+ ck。X. Zheng/Electronic Notes in Theoretical Computer Science 167（2007）325339s=0时因此，|xs — xs+1| ≤ 2+ ck, i.e.,（xs）弱有效收敛于x因此x是弱可计算的。 因此，ECO-ECECOWC。Q4可计算边界在本节中，我们讨论可计算函数f的有效可计算性。本文首先给出了可计算函数f的f-ec实数的一般层次定理。然后对一些特殊函数f的半可计算性、弱可计算性与有效可计算性进行了比较。回想一下，在[12]中，实数x被称为f-有界可计算的，如果存在一个可计算的有理数序列（x s）收敛到x，使得对于任何n，非重叠索引对（s，t）的数量（不一定在n之后），|x s−x t| ≥ 2 −n由f（n）有界。 用f-BC表示所有f-有界可计算实数的类.所有可计算函数f的所有f-BC的并集是DBC，这是在[14]中首次引入的发散有界可计算注意，对于f-有界可计算性，所有大于2−n的跳跃都被考虑，不管跳跃是否发生在阶段n之后。因此，如果一个实数x是f-有界可计算的，那么它也是f-有界可计算的，即，对于任意函数f，f-BCf-EC。另一方面，对于任何n，在阶段n之前最多有n个大跳跃。也就是说，如果x对于一个函数f是f-e可计算的，那么它对于这个函数是f1有界可计算的。f1（n）：=f（n）+n，即，f-EC-1-BC 。因此，DBC也是工会对于所有的可计算函数f，f=EC。对于f-有界可计算性，在[12]中表明，对于任何可计算函数f和g，f-BC/=g-BC当且仅当函数f和g具有无界距离，即，（c）（n）（|f（n）−g（n）|≥ c）。对于有效可计算性，我们有另一个层次定理如下。定理4.1设f，g：N→N是可计算函数.如果有无穷多个n使得f（n） v e，s，使得对于所有t≤t