实数的不同表示及其原始递归性的关系

理论计算机科学电子笔记167（2007）303-324www.elsevier.com/locate/entcs实数在不同表示陈庆良a，b，1，2苏凯乐a，c，3郑喜忠b，d，4a中山大学计算机科学系，中国广州510275bTheoretische Informatik，BTUCottbus Cottbus 03044，Germanyc澳大利亚昆士兰州布里斯班市Gri Benneth大学集成与智能系统研究所，邮编4111d江苏大学计算机科学系，江苏镇江212013。摘要在数学中，研究了实数的各种表示法。所有这些表示在数学上都是等价的，因为它们导致相同的实结构--戴德金完备有序场。甚至这些表示的有效版本在它们定义实数的可计算性的相同概念的意义上也是等价的。然而，原始递归（p.r.，这些表征的不同版本可以导致不同的P.R.概念实数关于p.r.的几个有趣的结果。实数可以在文献中找到。本文总结了实数在不同表示下的本原递归性的已知结果，并给出了一些新的关系。我们的目标是系统地阐明原始递归性如何依赖于实数的表示关键词：原始递归，实数表示，E可计算。1国家自然科学基金项目60496327、10410638、60473004，德国研究基金项目446 CHV 113/240/0-1，中山大学KAISI基金项目，澳大利亚研究理事会项目DP0452628。2Email：tsingliangchen@ ya hoo. C om3电子邮件：isskls@zsu.edu.cn（通讯作者）4电子邮件：zheng@informatik.tu-cottbus.de1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.08.018304Q. Chen等人理论计算机科学电子笔记167（2007）3031引言实数的可计算性是由Alan Turing在他的开创性论文[19]中介绍的根据图灵的说法为了精确地定义由于图灵机精确地计算自然数上的可计算函数，因此图灵实际上将具有可计算十进制展开式的实数定义为可计算的真的很好。 如果存在可计算函数，则x是f：N→ {0， 1，···，9}，使得x=∞n=0例 f（n）·10−（n+1）。Herreweconsider只有区间[0， 1]中的实数。 正如罗宾逊[16]，Myhill [11]，Rice [15]和其他人，实数的可计算性可以通过Cauchy序列，Dedekind割和实数的其他表示来等价定义。也就是说，实数的可计算性与它们的表示无关。可计算实数的类将用EC表示（E可计算）。除可计算性外，还讨论了次递归实数，如本原递归实数和多项式时间可计算实数。如果使用不同的表示，则可以定义次递归实数的不同概念。Specker [18]是第一个研究这个问题的人，他证明了十进制展开，Dedekind切割和Cauchy序列导致了三个不同版本的p.r.实数后来，彼得[14]，莫斯托夫斯基[10]和雷曼[9]研究了其他版本的p.r.。并进一步揭示了公共关系概念之间的关系。基于不同表示的实数。然而，并不是实数的每一个重要表示都被讨论过，而且到目前为止，对实数的次递归性还没有一个系统的概述。本文旨在解决这一缺陷。本文总结了文献中关于实数的本原递归性的已知结果。我们将给出p.r.的一些新的性质reals，并系统地分析了reals的原始递归性对表示的依赖性。本文的组织结构如下。在下一节中我们首先回顾实数可计算性理论中的表示，然后在第3、4、5、6、7节中我们将分别用区间套、Cauchy序列、b-adic展开、Dekedind割和连分式来考察和探讨这些表示的层次最后一节是对全文的总结。Q. Chen等人理论计算机科学电子笔记167（2007）303305F|−|≤≥2实数的表示在本节中，我们回顾了本文将要讨论的实数的表示。首先，我们解释的经典形式的representations。由于我们感兴趣的是表示到不同水平的等价化，所有表示将再次以统一的方式定义，使得它们依赖于某个给定的函数类F根据选择在这个类中，可以定义关于实数的不同层次的各种可计算性。这些概念还取决于所选的表示。为了简单起见，我们只考虑单位区间[0，1]中的实数如果一个实数x不在这个区间内，则存在一个y∈[0， 1]和一个自然数n使得x=y+n或x=y−n。在这种情况下，实数x和y在任何合理的意义上都应该具有相同的可计算性水平。现在我们非正式地回忆一下实数的表示。一个有理数序列（x s）称为柯西序列，如果对于任何n> 0，存在一个N使得x s Xt 对所有s，t N. 也就是说， 柯西序列是简单的收敛序列。柯西序列（xs）表示实数x，如果序列收敛于x。这种表示被称为朴素柯西表示（见Weihrauch [20]）。换句话说，实数x的朴素柯西表示是一个序列（xs）。收敛于x在可计算分析中，柯西序列的一种更流行的表示是使用具有有效收敛模的柯西序列，我们称这种表示为柯西表示。更准确地说，实数x的柯西表示是一个有理数序列（x s），它在某种意义上逐次收敛于x，|x s−x|对于所有s，≤ 2 −s。柯西表示的一些变化将在第4节中讨论。戴德金割是一对（C，D）有理数集合，使得C向下闭合，即，如果u≤v且v∈C，则u∈C，且D向上，即，如果u≤v且u∈D，则v∈D。一个Dedekind截集（C，D）表示一个实数x，实际上意味着x是C的最小上界。由于一个戴德金割（C，D）是由集合C唯一确定的，我们通常将x的（左）戴德金割定义为有理数集合Cx：={r∈Q：rx}，并将集合Cx视为x的戴德金割表示。由于任何集合都可以由其特征函数唯一描述，我们也可以将实数x的戴德金截表示定义为函数f：N2→ {0，1}，使得f（n，m）=1当且仅当n/1，我们也可以表示以b为底的实数。这是一个B-adic的扩展操作。也就是说，一个b-adicreep表示一个realnumberx是函数f：N→ {0，1，...，b− 1}，则x =∞s=0时 f（s）·b−（s+1）。If基数b= 2，则b-adic表示称为二进制表示。实数的二进制表示将实数与集合联系起来自然界中的自然现象。设f：N→N{0，1}是一个整数−（s+1）实数x的表示。那么我们有x=f（s）·2 =Σs∈A2 −（s+1）s=0时其中A：={s∈N：f（s）= 1}。因此，二进制表示是A的特征函数。实数x通常也表示为x=xA。实数的另一种表示是嵌套的有理区间序列。一个有理端点的闭区间序列（Is）称为嵌套的，如果Is+1我代表所有的人。这个序列表示实数x，如果x是所有区间的唯一公共成员。 区间序列可以由两个函数定义。因此，我们可以将实数x的嵌套区间表示定义为函数对f，g：N→Q，使得f（s）≤f（s+1）≤x≤g（s+1）≤g（s）对所有s且lims→∞（g（s）−f（s））= 0。最后，我们解释了实数的连分式展开它已知每个正实数x都有一个唯一的正则连分式展开式，1x=b0+b1+21加...（一）其中b0≥ 0，bn≥ 1，n∈N. 为简洁起见，我们写x= [b0，b1，b2，···]，其中数bn称为n阶偏商。很明显，在有理数的情况下，bn的个数是有限的。的如果x是有理数，则x=[b0，b1，b2，···，bn]，其中n是某个数。为方便起见，我们用x=[b0，b1，b2，···，bn，0， 0，···]表示这个有理数。因此，实数x的连分数表示是函数f：N →Nsuchtatx=[f（0），f（1），f（2），·· ·]。上面提到的所有表示在数学上都是等价的，因为它们推导出了相同的（更准确地说，同构的）结构，称为戴德金完备有序场。然而，如果我们对实数的可计算性感兴趣，情况就不同了。为了更精确地解释这一点，我们首先看看如何将可计算性概念引入实数。这个想法很简单。正如我们所看到的，每个X=BQ. Chen等人理论计算机科学电子笔记167（2007）303307222上述实数的表示使用从自然数到自然数或从自然数到有理数的函数。因此，关于这些函数的任何幂律概念都可以自然地转移到由这些函数表示的实数上。为此，我们必须将自然数上的函数的可计算性（或子可计算性）扩展到从自然数到有理数的函数。这个扩展看起来像下面这样：设F是一类函数f：N→N。 我们说一个函数g：N→Q属于F是指在F中存在函数a，b，c：N→N，使得g（n）=（a（n）−b（n））/（c（n） +1）或所有n。现在我们给出函数类F的所有上述表示的相对化的精确定义。定义2.1设F是一类函数f：N→N或f：N→Q，x∈[0，1]是实数。(i) x有F-Cauchy表示（x∈CS（F）），如果存在函数f：N→Q在F中使得序列f（s）分别收敛于x(ii) x有F-Dedekind截表示（x∈DC（F）），如果存在F中的函数f：N2→ {0， 1}使得f（n，m）= 1当且仅当n/（m+ 1）1.我们c a llare a lxb-adicprimit ivecursive（或b-adicp. r. 如果有一个公共关系。函数f使得x=∞n=0例 f（n）·b−（n+1）。这类课程涵盖了所有的B类和D类。R. real数字由Rb表示。在本节中，我们可以看到类Rb是2 2Cauchy p.r.的真子集实数类R1，对所有b>1。此外，我们认为，对于不同的b，类Rb不一定相同。2Σ∞−（n+1）注意，如果x有一个p. r。 b-adic展开，即，X=n=0f（n）·b做公关。函数f，则函数g定义为g（n）=ni=0时 f（i）·b−（i+1）是一个公关。 x的柯西表示 这一观察意味着，R2等于R1另一方面，Specker [18]表明R10/= R1。Specker对不等式R10/ = R1的证明思想是证明R10在以下条件下不是闭的：Q. Chen等人理论计算机科学电子笔记167（2007）303313联系我们联系我们算术运算因为R1在算术运算下是闭的，所以它们是不同的。这一思想可以推广到其他基b的情况。因此，基于柯西表示和b进展开的实数的本原递归性是不同的.Specker引理5.1（Specker [18]）有p.r.函数u和v使得函数q定义为这不是公关。功能q（n）：=u（（μt≥n）（v（t）= 0））定理5.2（Specker [18]）存在一个小数p.r.实数x使得3x不是十进制p.r.。证据我们想找到一个实数x：= 0.a0a1a2a3···，使得由a（i）：=ai定义的函数a是p. r.，但对于3x=b.b0b2b2b3···，由b（i）：=bi定义的函数b不是p.r。让为了简单起见，我们限制ai∈ {1， 3， 5}对所有i。x = 0。a0a1a2···：= 0. 335131155 33 1 51 1 ···3 x = b。b0b1b2···：= 1 .一、005393465 99 4 53？···在哪里“？” can be 3 or 4 depending on the first non-3 digit of检查bi的奇偶性，我们可以发现一个数字bi是偶数，当且仅当第一个数字aj，j > i且aj/= 3是5。也就是说，对于任何n，我们有b（n）0mod 2a（（μt > n）（a（t）= 3））= 5.（五）现在问题被简化为找到一个P.R.。函数a：N1， 3， 5，满足条件（5）的函数b不是p. r.。这是为了找到一个PR。函数a：N→ {1， 3，5}，使得函数q：N→ {1， 5}定义为q（n）：=a（（μt> n）（a（t）3））（6）不是公关。 对于任何公关 函数u：N1， 5 而v：N N，如果我们定义函数a，a（n）：= 3·sg（v（n））+u（v（n））·sg（v（n））其中SG和SG是信号函数。然后我们有a（n）∈ {1， 3， 5}，a（n）= 3当且仅当v（n）= 0a（n）=u（n）对所有n. 这意味着a（（μt> n）（a（t）= 3））=u（（μt> n）（v（t）= 0））314Q. Chen等人理论计算机科学电子笔记167（2007）30322n=0例2i=0时2因此，问题进一步简化为找到两个P. R。函数u：N→ {1， 5}和v：N→N，使得函数定义为q（n）：=u（（μt> n）（v（t）= 0））不是原始递归。这种PR的存在。函数u和v由引理5.1得出。Q注5.3通过斯佩克的同样的结构，不难看出，任何p.r. b进展开实数在算术运算下不是封闭的。推论5.4 b-adic展开类p.r. reals是Cauchy p. r.类的真子集实数，即，RbR1.现在我们来探讨类Rb对于不同的b首先，我们来看看一个实施例。Letb，d>1bebasuchatereisak >0，使得bk=d。如果x是b-adicp.r.实数，即，x：=n∈Nf（n）·b−（n+1）对于p. r。函数f，当函数g（n）：=k−1f（nk+i）isalsoP.R.因此x=Σn∈Ng（n）d−（n+1）i=0时是d-adicp.r. 也 此观察结果Mostowski [10]将其推广到以下结果。定理5.5（Mostowski [10]）设b，d > 1. 如果b的幂能被d，则任何b-adic p.r.实数也是d-adic p.r.，也就是说， R bR d.证据设bk=s·d，对某个k，s∈N，x=∞是一个公关。b-adic展开式。 定义一个p. r。函数g由g（n）：=f（n）b−（n+1）f（n·）k+i）·bk−1−i。Noticethat，g（n）≤（1+b+·· ·+bk−1）（b−1）=bk−1，becausef（i）≤b−1对所有i。现在x的d-adic展开式可以得到如下。Σ∞X=n=0例f（n）b−（n+1）=Σ∞n=0例g（n）b−k（n+1）（7）卢恩=i=0时Σ∞h（i）d−（i+1）+r（n）b−k+I=nΣ∞g（i）b−k（i+1）=n=0例h（n）d−（n+1）（8）在那里，公关。函数r和h归纳地定义为：⎧q（0）：=qt（g（0），s）⎪g（0）：=rs（g（0），s）.Σn（n+1）：=qt g（n）+r（n）bk，sn+1⎪Q. Chen等人理论计算机科学电子笔记167（2007）303315（n+1）：=rs .Σg（n）+r（n）bk，sn+1.记住，qt和rs分别是商函数和rest函数。根据定义，对于所有n，我们有r（n）1，Rb<$Rd当且仅当d整除2 2b的幂，即，（bk，s）（bk= s·d）.为了证明这个定理，Lachlan给出了一个等价的刻画，类Rb如下。 设R（b）：={m·b−n：n，m∈N}是所有b进有理数对于任何有理数集合A，用C0表示实数x的类，使得x的戴德金截限于A（即，交集C x{\displaystyle C x{\displaystyle C}}是原始递归的。然后拉克伦表明，Rb=C0，对于任何b>1。也就是说，实数x是b-adic p. r。当且仅当2R（b）集合{（n，m）：m·b−n1，如果b的幂不能被d整除，则R（b）\R（d）国际新闻社 稠密。 这就意味着有Rb\Rd=C0\C。6Dedekind割表示本节讨论具有p.r.的实数。戴德金会切。我们将看到，这些实数可以用四种不同的方式等价地描述。 根据定义，实数x的（左）戴德金截集是集合Cx：rQ：有理数的r< x。因此，x具有p. r。 Dedekind割表示集合Cx是p. r.设置，即，特征函数χ x：Q0， 1是P.R. 这里我们需要一个公关的概念。从有理数到自然数可以通过将有理数表示为整数对来定义的数。然而，我们可以通过考虑由L x（m，n）定义的关系L x：m/（n + 1）1/2。设γ x（n）被定义，且x位于某个最低阶Farey序列中两个相邻分数之间，这两个分数已被广泛使用，比如s1/t1和s2/t2。 则定义γ x（n +1）：=0，如果x<（s1+ s2）/（t1+ t2），且当x>（s1+s2）/（t1+t2）时，γ x（n+1）：= 1Hurwitz特征提供了一种简单的方法来找到实数的连分数。我们将在第7节定理7.4的证明中解释。下面的定理给出了Dedekind的一个新的特征P.R. 实数定理6.2（Lehman [9]）实数x∈（0，1）是Dedekind p.r. 当且仅当它的Hurwitz特征γx是p.证据设x（0，1）是Dedekind p.r.，也就是说，x是p。定义一个函数e，如果x m/（n+1），则e（m，n）= 1，如果x> m/（n+1），则e（m，n）= 0318Q. Chen等人理论计算机科学电子笔记167（2007）303t1（n）+t（n）2t（n）t1（n）+t（n）2⎪⎪11x22 2x1t（n）t2（n）nE是P. R。现在，赫尔维茨特征线γx可以借助四个附加函数s1，s2，t1和t2更正式地定义如下。最初令γx（0）：= 0，s1（0）：= 0和s2（0）=t1（0）=t2（0）：=1。在阶段n，假设x位于s1（n）/t1（n）和s2（n）/t2（n）之间。然后定义eγx（n+1）=0或r1，其中rxs1（n）+s2（n）或不. 的是我们有γ x（n+1）=e（s1（n）+s2（n），t1（n）+t2（n）−1）.（9）某些F序列的s_1（n+1）和s_2（n+1）的新序列之间存在N × 10 ~（-1）的关系t1（n+1）t2（n+1）whichequaltos1（n）1s1（n）+s2（n）t1（n）+t2（n）若γx（n+1）=0，或s1（n）+s2（n）s2（n）t2（n）否则，分别。 也就是我们要⎧εs1（n+1）=s1（n）+γx（n+1）s2（n），n=t（n） +γ（n+1）t（n），εs2（n+1）=s2（n）+（1−γx（n+1））s1（n），γt（n+1）=t（n） +（1−γ（n+1））t（n）。（十）因此，由等式（9）和（10）定义的所有函数γx，s1，s2，t1，t2为P.R.尤其是x有一个p. r Hurwitz特征。另一方面，假设x有一个p. r。Hurwitz特征γx。我们可以定义四个P。根据（10）的函数s1、s2、t1和t2通过一个简单的归纳，我们可以看到，对于所有的n，max{t1（n），t2（n）}> n.康-序列号1（n）1s2（n）t2（n）是某个Farey级数中的相邻分数，或-大于n的。因此，不可能有m/n这样的数，s1（n）t1（n）M < s2（n）。 因此，我们有[nx]=[ns1（n）/t1（n）]=[ns2（n）/t2（n）]。所以x有个公关。 由定理6.1切割的戴德金。Q现在我们讨论戴德金P. R.和b进实数。请注意，实数x的b进展开式的任何有限初始段都对应于小于（或等于，如果x是有理数）x的有理数。因此，从一个PR。Dedekind cut ofx to find a p.r. x的b-adic展开式这可以通过和和和 1. 任何Dedekind公关 实数是b-adicP.R. 但是有一个很好的公关。真实的，这不是戴德金公关。 也就是说，R3<$R b。证据如果x∈[0，1]是Dedekind p.r.，则根据定理6.1，Beatty函数[n·x]是一个p. r.功能x的b-adic展开f可以递归地定义为f（0）：=[x]，对于任何n，320Q. Chen等人理论计算机科学电子笔记167（2007）3032222[·[·22f（n+1）：= max= max.t≤b：.t≤b：卢恩i=0时卢恩i=0时Σf（i）·b−（i+1）+t·b−（n+2）≤xΣf（i）·b（n+1−i）+t≤[b（n+2）x<$因此，x是b-进展开p. r。因此R3<$Rb。为了证明不等式R3Rb，通过矛盾假设R3=Rb对于某个b>1。选择一个自然数d，使得d不能整除bk对任意k∈N。 根据定理5.6，我们有R3= Rb <$Rd。这与R3≠Rd的事实相矛盾。Q根据定理6.3，我们不能总是得到一个p. r。 戴德金从一个公关公司剪下的一个真正的x。b-adic展开式。 然而，如果x可以在所有基b中递归一致地表示为b-进展开基元，则情况不同。这里b进展开式对其基的一致依赖性b表示每个数字对基数的依赖性这可以被描述“统一数字函数”。确切地说，函数f：N2→N称为实数x的一致基展开式，如果对所有n∈N和任何自然数b≥2，0≤f（b，n）1，我们有f（b，1）f（b，2）∞b·x=f（b，0）+x +x+ ···=f（b，i）b−i.xb1b2i=0时因此，我们有bx=fx（b，0），如果x不是有理数，因此不具有x=m/bk的形式。也就是说，x的贝蒂函数是p. r。根据定理6.1，x是一个Dedekindp. r。实数如果x是有理数，那么x显然是戴德金p. r。实数也是。另一方面，如果x是一个Dedekind p. r。实数，则它的Beatty函数n x是p. r。x的均匀基展开式f x可以明显地归纳定义为：Q. Chen等人理论计算机科学电子笔记167（2007）3033212112⎧fx（0）：=[b·xfx（n+1）：=[bn+1·x因此fx是p.r. 也就是说，x有一个p. r。 统一的基数扩大。Q在柯西公共关系。雷尔斯-戴德金出版社Reals Specker [18]已经证明了下面的分解定理。定理6.5（Specker [18]）每个Cauchy p.r.实数是两个Dedekind p. r的和。实数证据 设x是柯西p. r。 实数 假设w.l.o.g. x> 1。它这是一个公共场所。函数f：N→{1，2，3}suchthat∞x=n=0f（n）= 0 定义两个P. R。函数h0，h1，⎧如果[n]是偶数，h0（n）：=01如果[⎧n是奇数;如果[n]是偶数，h1（n）：=00如果[n是奇数;因此，实数x可以分解为实数s和t，即，x=s+t，其中s和t定义为：Σ∞S=n=0例h0（n）f（n）·2−n和t=Σ∞n=0例h1（n）f（n）·2 −n