22理论计算机科学电子笔记120（2005）59-72www.elsevier.com/locate/entcs由第一值运算符定义的函数类的层次（扩展摘要）阿明·赫默林1Instittfu？rMmatikundInfmatikErnst-Moritz-ArndtUniversit？tGreifswald D-17487 Greifswald，Germany摘要第一值运算符将一个新的此类函数赋给任何相同类型的部分函数序列。它的定义域是序列函数的定义域的并集，它在任何一点的值就是序列中第一个定义在该点的函数的值在本文中，第一值运算符被应用于建立各种设置下的函数类的层次结构。对于可计算离散函数的有效序列，我们得到了一个层次，和厄绍夫的 那 个 有联系实函数上的非有效版本与不连续度有关，并产生与Borel类中的HausdorDifference层次相关的层次。最后，近似可计算实函数上的有效形式形成了一个层次，为可计算分析提供了一个有用的工具。关键词：函数的层次，不连续度，可计算分析，有效描述集理论，Hausdor层次，Ershov层次1导言和基本概念设F=（f ∈）∈< α是某些类型p e的部分函数的有限或超有限序列。 这种方法是指f：A>−→B，对于A和B，α是序数，并且贯穿集合{：<$<α}={<$：<$∈α}=α。的1电子邮件地址：hemmerli@uni-greifswald.de1571-0661 © 2005由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2004.06.03460A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）59⊆{F∈所以，0（F）={}，其中0是空函数，并且1（F）=F。更进一步，∇当α≤β时，从F出发，它遵循β（F）。如果ηdom（fη）函数f的第一值运算Φ：A>−→B，定义如下f（x）<$$>f<$x（x）if{<$α：f<$（x）↓}<$且<$x=min{<$α：f<$（x）↓}，↑如果−→{0，1}c表示为Mf={x：f（x）=1}。在本论文中，兴趣是针对类的功能本身。从某个基本类F中通过首值算子得到一个函数所需的序列的（最小）长度决定了该函数的水平（或次数）w.r.t.。F.这种方法不仅对经典可计算性理论和描述集合论的一些著名概念产生了统一的观点，而且还导致了关于有效分析主题的一些新的特征和工具。我们首先解释第一值层次结构的非有效版本的基本原理。 设F是部分函数f：A>−→B的非空基类。对于任意方向的N，<$α（F）={Φ（F）：F =（f <$）<$<α，其中f <$∈ F对所有<<$α}。α+1 （F）=f：f（x）g（x）如果g（x）↓，h（x）否则，对g∈<$α（F）和h∈F}.dom（f），则函数f不影响序列Φ（F）的结果。因此，给定一个序列F=（f）α，通过有限递归n，可以确定-求一个序列FJ=（f<$J）<$αJ使得αJ≤α，ηdom（fηJ）η≤dom（fηJ）且Φ（F）= Φ（FJ）。 因此，对于可数宇宙A，我们可以限制自己，长度α属于第二个数类CII的序列，C II由有限基数或可数无限基数的所有序数组成。又若A是可分拓扑空间，且f∈F都有开域，则长度为αCII的序列足以获得首值算子应用于由F的函数构成的任意序列的所有可能结果。本文的主要目的是在关于论域A和基类F的几种情形下，结合序列的要求，研究线性族（·α· ·（F））α∈CⅡ的性质必须应用运算符Φ的F。 它们将由上部A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）5961>−→>−→≥∈S>−→S>−→标签上的标签。作为第一个例子，假设A=B=N，并考虑基本类Fsing={f：f：N>−→N，card（f）≤1}且Ffin={f：f：N>−→N，card（f）<ω}。显然，如果1 ≤ n ω，则n（Fsin）={f：card（f）≤ n}和n（Ffinn）=Ffinn<，但对于所有α ≥ ω，nα（Fsing）=nα（Ffinn）={f：f：N>−→N}。相当类似的结果适用于f型函数：NkN，k1，以及许多其他类似的设置。因此，离散宇宙上的第一值层次的非有效版本已经在水平ω处坍缩，具有最大可能的部分函数类，即使对于简单的基本类F也是如此。为了在离散论域上获得更有趣的结果，算子Φ将被限制为有效序列。这只是下一节的主题。然后我们将考虑欧氏空间上的实值函数f：RkR。第3节中研究的非有效设置提供了第四节阐述了有效版本的基本背景。2离散函数现在我们要研究f型可计算函数的有效序列上的首值算子：NkN 。 相关的概念和结果基本上是已知的递归理论设置周围Ershov的层次结构，比照。[3]的文件。通过构造序数的方法定义了transfinite序列的E_（？）我们报告一些基本的事实和外延采用的续集。更多细节，读者可以参考[16]。设（φn：nN）为部分递归函数的Kleene数。一个（序数的）命名系统S由编号νS：NCII给出，使得• ran（νS）是序数的初始段，对α∈CⅡ，ran（νS）=α={ε：ε α};• 对任意n∈dom（νS），（用部分递归函数KS）可判定νS（n）是否=0或νS（n）是否为后继数或极限数;• 对于任何数n，其中νS（n）是后继数，数nJ是可计算的（通过部分递归函数pS），使得n∈ν−1（νS（nJ）+1）;• 并且对于极限数λ的任意名称n∈ν−1（λ），指数nJ是可计算的（通过部分递归函数q S），使得φ nJ是全函数且（ν S（φ nJ（m））m∈N是收敛于λ的递增序数序列。更精确地说，S=（νS，kS，pS，qS）。一个序数α∈CII称为con-62A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）59≤F>−→F⊆ ∇α/S∇\n\nλ/Sξ α1EE构造性地，存在一个命名系统S，其中α∈ ran（ν S）。如果集合{（n，NJ）：n，NJ∈dom（νS），νS（n）≤νS（nj）}是递归的，则称S是递归相关的，如果集合{（n，nj）：n，nj ∈ dom（ν S），ν S（n）≤ ν S（nj）}是递归的，则称它是单叶的，如果νS是内射的，则称它是单叶的. 对于任何构造序数α，都有一个递归相关的单价（brie y，r.r.u. 系统S给该序数分配一个名称。因此，我们可以把自己限制在以α/S形式表示的这种特殊命名系统中。对于α ω，总是使用具有与编号相同的映射的规范命名系统，w.l.o.g.对于命名系统S，S-可算性是指函数f：Nk×CII>−→N，k∈N，有一个递归函数f：Nk×N>−→N，其中f（→x，n）f（→x，νS（n））对n∈dom（νS）有一个递归函数. 用于命名系统α/S，一个函数f ∈：Nk>-→ N的nα-s方程F=（f∈）<$<α称为S-可算函数，其中e是一个nS-可算函数f：Nk×CII>-→N，满足f（→x，<$）f<$（→x）f或所有→x∈Nk且所有序数<<$α。然后，如果S是递归相关，函数Φ（F）的域是r.e.：dom（Φ（F））= dom（f）∈φ0.对于k元部分递归函数的S -可计算α -序列，称函数f：NkN为α/S-递归的i <$f= Φ（）;对于某些r.r.u.，f称为α-递归的i <$f是α/S-递归的。命名系统α/S。因此，我们得到以下Ershov函数类，在符号相关和符号无关的版本中，即，带和不带Eα（/S）={f：f是从某个Nk到N的α（/S）-递归函数}。显然，E（α+1）（/S）如果S也是α+1的命名系统。让<α（/S）=β< αβ（/S）。E提案2.1对于所有r.r.u.命名系统（α + 1）/S和λ/S，具有极限数λ，Eα/SE（α+1）/SE<λ/Sλ/S。这直接来自于类EEE的模拟结果的原始Ershov层次结构，参见。[4、3、7]。这些类由Nk的所谓α/S-递归子集组成，这些子集的特征在于它们的总特征函数在上面定义的意义下的α/S因此，由于经典的结果，甚至有全{0， 1}值离散函数，E（α+1）/SEα/S 而E<λ/S，分别。Q下面的命题描述了在Ershov层次中出现的函数. 它还表明，符号无关的层次崩溃在水平ω2。 回想一下，f ≤T0 J意味着函数f是0 J-可计算的。一函数f：Nk>−→Nis称为极限-可压缩函数，其中有一个全循环函数n：Nk+1−→Nsuchthatf（→x）li mn→∞n（→x，n）。∇α（/S）∇∇∇⊂ ∇⊂ ∇和A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）5963α/S2ω2∈⊆>−→α<αβα（α+1）<λλf= Φ（F）。注意，dom（f）=−→N等价：(i) f∈E，对一个构造序数α和一个r.r.u. α/S系统(ii) f ≤ T0J且dom（f）是r.e.;(iii) f是极限可计算的，dom（f）是r.e.;(iv) f∈E。（ii）惠（iii）的等价性是众所周知的。(iv)（i）是平凡的，并且（i）(iii)很容易显示。最后，在[3]中证明了Q3实函数Hausdor这种拓扑逻辑设置主要针对点集类，不能直接转移到函数类。此外，在拓扑学中，处理部分函数是不太习惯的，这是应用算子Φ的基本特征。一个相当大的进展，相关的分类的功能是由赫特林-Weihrauch和赫特林谁介绍和研究的水平不连续的功能，见[10，8，9]。最后，在[7]中，我们已经展示了如何通过第一值算子来刻画点集类的Hausdorhierarchy。这种设置现在被转移到欧氏空间上的某些实值函数的分类。对于实函数，我们指的是任何部分函数f：RkR ， 对于任意维数kN+。它被称为是连续的，对于所有开G R，原像f −1[G]也是开点集。特别地，dom（f）= f −1[R]必须是开的。我们将要介绍的层次结构的基本类是连续函数，f={f：f是连续实函数}。对序数α∈CⅡ，实函数f称为α-连续的，且存在连续函数f∈F <$的α -序列F=（f<$）<$α，使得1-连续函数就是F的成员。实函数的Hausdor层次结构的类定义为：H={f：f是α-连续实函数}且命题3.1对所有序数α和极限数λ，其中α，λ∈CⅡ，你好你好你好。这是根据通常的Hausdor层次结构的相关属性得出的，β α64A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）59α22UηfFFF（α+1）Fαλ<λFRKFFFFUfξFF步通过transfinite归纳，它遵循任何工会，FFFFFFFFFFFF类E3H，cf。[7]的文件。它们由α-闭点集A构成，而α-闭点集A恰好是其全特征函数χ A是α-连续的点集。因此，在本发明中，有{0， 1}-值实函数的总数在{0，1}和{0，1}-值实函数中，分别Q豪斯多尔函数层次的另一个特征 这也可以追溯到豪斯多·[5]，他证明了可分解集正好是CVB的成员。在[6，7]，我们已经结合了他的方法与特点Ershov在此之前，Hertling-Weihrauch [10]和Hertling [8，9]已经将Hausdor方法应用在这里，我们基本上遵循他们的设置，即使为了保持与[7]一致而修改了符号，并为顺利通过下一节的有效版本做准备。对于闭集F<$Rk和任意A<$F，设A|表示内部相对于F. 你好，A|F=F{B<$F：B<$F<$A，B在Rk中是开的}。给定一个实函数f：Rk>−→R，使得p∈C，U∈Rk，f∈Rf f所有序数都可以用transfinite递归定义如下：C0={→x：f（→x）↓，且fiscontinusin→x} |◦、这是f的连续域的内部。对于0，将U =C ηη ξ且C<$={→x∈U <$：f（→x）↓，f|{n n=n→x} |◦ .在本文中以及整篇文章中，上划线表示集合的补集。由于U0=Rk=Rk，所以初始步骤包括在一般递归中Cη是开放Rk和所有的宇宙Uk都是闭点集。 此外，如果η/=π，则Cη<$Cη =π，f f f和Rk= U0<$U1<$. U无国籍（f）。因此，存在一个最小序数α∈CII使得Uα=Uα+1，或者等价地，Cα=α。当所有η≤α时，我们都有U ηU和Cη=U，但U α=U且C <$=<$，对于所有<$≥ α。函数f对于这个最小序数α被称为可分解的i <$U α= dom（f），在这个序数处宇宙序列变得稳定。在本例中，我们有dom（f）=ξ α C.并定义了点t→x∈dom（f）w. r. t的一个深度h. 函数f由ξdepthf（→x）=<$i <$→x∈C，A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）5965FF F ∈∈FCFUFFFFF更确切地说，f∈（→x）=f（→x）f或所有→x∈dom（f∈）\（η∈dom（fη） ）=dom（f∈）ndom（fη）dom（f）U，且f连续。 因此，dom（f）Uη≤ξCηdom（f）η≤ξFη≤ξη≤ξFF|ηFFFFCF命题3.4一个实函数是可分解的，如果它是α-连续的，对于某些而f的全局深度由下式给出：udepth（f）= min {n：U = dom（f）}。可分解性与α-连续性之间有着密切的关系。引理3.2设f=Φ（），其中=（f <$）<$<α，f <$F<$，αCⅡ.对于所有的序数<α，η≤ ξ dom（fη）η≤ξCη。这适用于θ= 0，即，dom（f0）<$C0，因为C0是上其中f是连续的，f0与f在dom（f0）上重合，并且f0是连续的。现在，让所有的人都来完成这个断言。<然后，U =C η=C ηdom（f η）=dom（f η）。是U的最大相对开子集，f在其上是连续的。Fη ξC、以及Fdom（fη）= dom（fη）Fη ξFFFdom（fη）dom（f）C（dom（f）<$U）<$Cη<$Cη.Q从引理3.2可以得到任何实函数的可解性，是α-连续的。实际上，如果f = Φ（F），其中序列F =（f<$）<$α，f<$∈F<$，则η α dom（fη）= dom（f）。以来η ξFF对于所有序数，它遵循C α=。因此，f是可分解的。此外，根据引理3.2，udepth（f）是连续函数序列F的长度的下界，其中Φ（F）=f。引理3.3如果一个实函数f是可分解的，则存在一个序列F=（f∈）φdepth（f）φh，其中f=Φ（F），并且，（+）f<$∈F<$且η≤ξdom（fη）=η≤ ξη对于所有<的深度（f）。设f0= f |C0，满足条件（+）。假设fη对所有η都有定义，使得（+）成立。 然后我们有dom（fη）=Cη。根据C的定义，有一个开集，G<$Rk使得C<$=U<$<$G，即，GCηdom（f）.此外，f |ξF是C上的连续函数，被认为是正规的闭子集空间G.因此，根据Tietze-Urysohn定理，见[2]，f |C语言可以扩展到一个连续的函数，函数G。因此我们有一个vedom（f）=G和f（→x）=f（→x）对all→x∈C<$。 满足dom（fη）=Cη，并且d（+）被填充。 QCFFη ξη ξη ξη ξFη≤ξη ξη ξFη ξη ξFF66A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）59α22∈在闭F_∞条件下，i.集合FJ=η dom（fη）也是闭的。因此/∈ξi ωα∈ C Ⅱ. 更准确地说，对于任何α∈ C II，f ={f：f是可分解的实函数，且udepth（f）≤ α}。这只是总结了迄今为止取得的一些成果Q实函数列F =（f <$） <$<α称为贪婪函数列，其中f = Φ（F），y→x∈dom（f），→x∈dom（f<$），其中verdepthf（→x）=∞.请注意，函数f的贪婪序列的长度α显然可以限制为udepth（f）。现在引理3.3可以表示如下。推论3.5任何可分解的实函数都可以用Φ（F）得到，其中F是连续函数的贪婪序列。QHertling [8]对度量空间上的全函数给出了以下结果，强调可分解函数在描述集合论的框架内属于相当低的复杂性水平。这里使用了Γ-可测函数的概念，参见。[11，15]：给定一类点集，Γ，实函数称为Γ-可测 i<$f−1[G]∈ Γ，对所有开G<$R。引理3.6任何可分解的实函数都是可测的.这可以通过集合可分解性来证明，参见。[8]的一项建议。在这里，我们用命题3.2来画出一个直接的证明，它可以用一种相当直接的方法来证明第4款.设f=Φ（F），序列F=（f<$）<$α，f<$∈F<$，G<$R是一个开放的集合。 则f−1[G]=<$<αξ（f−1[G]ξη ξ dom（fη））。开放点集f−1[G]是可数个闭集的并集：f−1[G]=我，f−1[G]=ξ α（（i ω F，i）<$FJ）=ξ αi ω （F，i FJ）.这意味着f −1[G]<$B，作为闭集的可数并。类似地，得到了补集的相关Q对任意集合A∈<$B，A<$Rk，实函数fA=A×{1}是<$B-2B2可测量的然而，如果dom（f A）= A，则它不可分解2001年。这是一一个悬而未决的问题是引理3.6的转换是否适用于具有开域的函数，或者等价地，如人们所示，适用于全函数。4实函数函数的Hausdor-Ershov层次是通过将离散函数的Ershov层次和实函数的Hausdor-Ershov层次的成分适当地组合而得到的效率的一个特点是，A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）5967κ=1∈M∈KM{∈ − ∈}M（）A=∈∈∈MM我们从Ershov的设置，包括在限制的序序的顺序类型的实函数序列。此外，这些函数必须是可计算的，这是在可计算分析的框架内定义的，参见。[17 ]第10段。我们简要回顾了一些相关的基本概念和符号。更多细节，请参见[6，7]。实数（和元组）由快速收敛的有理数（元组）柯西序列表示。设有理数集Q={qn：n∈N}的全标准数为νQ=（qn：n∈N）. 本文将它推广到QkviaC算子的k -上界函数，使Q k = { → qn：n ∈ N }. 对于p〇 ints-x=（x1， . . ，xk）∈Rk，我们满足极大范数n→xn=maxk|xκ|这在逻辑上等同于任何一个欧几里德核。R k中的自然拓扑由所有有理开球的基生成，Ballq （ →x） ={→y∈Rk：<$→x−→y<$ − → R的可计算性。s→x∈Rk的点可用迭代收敛Cauchy序列表示，即， 由集合CF→x= σNω：→qσ（n）→x<2−n对于nN. 一种功能型轨迹跟踪机（OTM）得到一个自然数n作为输入，σ=（i0，i1，i2，. ）Nω作为oracle，它产生了一个输出σ（n）N当它停下来的时候。在其工作过程中，它可以把oracle查询“，其中m ∈ N，它们由序列σ的第（m + 1）个元素im回答.一个实函数被称为（近似）可计算的，如果存在OTM，Msuchtatforall→x∈R：(i) 如果f（→x）↓，则nMσ（n）ex是f或所有σ∈CF→x且n∈N，且ndit成立（Mσ（n））n∈N∈CFf（→x）;(ii) 若f（→x）↑，σ∈CF→x，则对w∈Mσ（n）↑，n输入n ∈ N。柯-弗里德曼使用了一个更具限制性的概念。如果f（→x）↑，则Mσ（n）对于所有l σ ∈ CF → x和所有n ∈ N都是下定义的.对于OTM M，我们称函数f为KF-可计算的i ∈（i）和（m∈N+，是一个点集，对于全递归函数n：Nm−→N，中国1 NN2 N···nm N ball n（n1，n2，···，nm）如果m是奇数，n1∈Nn2∈N···nm∈N球<$（n1，n2，···，nm），如果m是偶数.68A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）59∗SF∇α（/S）αSξα点集类的层次结构产生α如果允许λ是任意离散函数，则（）是Borel集A∈λB的典型表示.而近似的域米塔可计算函数正好形成有效Borel层次中chy（m∈N+），KF-可计算函数的域就是米塔R.E. 开集，即，1991年的成员。 更准确地说，我们有引理4.1点集A是r.e. open i A = dom（f）对于一个KF-可计算的实函数f。一个近似可计算实函数f是KF-可计算的i（f）是r.e. 打开.第一部分是由于柯-弗里德曼[13]，第二部分很容易遵循。由于引理4.1，并且由于可计算函数在其定义域上是连续的，因此KF-可计算实函数形成了一个适当的有效性连续函数类的对应物，F。 因此，我们采取FKF={f：f是KF-可计算的实函数}作为有效第一值层次结构的基本类定义了从FKF出发的一列函数的超越性。一些R.R.U.命名系统α/S。序列F=（f<$）<$α称为S-KF-可计算的，其中是一个OTMM，对于或所有的p→x和定常变量α，(i) 如果fσ（→x）↓，则对所有的σ∈CF→x和所有的n∈N，有n个Mσ（n_m，n_n）↓，其中m=ν−1（n），且i∈holds（Mσ（m，n））n∈N∈CFf（→x）;(ii) 若f∈（→x）↑，对所有llσ∈CF→x，所有lln∈N，m=ν−1（n），有theNMσ（n ∈ m，n ∈）↑.显然，对于所有的<$α，它遵循f<$∈FKF。对 于 S-KF- 可 计 算 序 列 = （ f <$ ） <$α ， 实 函 数 f 称 为 α/S-toprecursive i <$f= Φ（F）<. α-上递归性是指α/S-上递归性w.r.t.一些R.R.U.命名系统α/S。1-toprecursive函数就是KF-可计算函数。每个α-toprecursive函数都是α-连续的，并且有一个r.e.开放域。对于构造序数α（和r.r.u. α/S），符号相关和符号无关的，分别，版本的豪斯多-埃尔索夫函数类被定义为他α（/S）={f：f是α（/S）-toprecursive real function}。由于基数的原因，我们有{α是一个构造序数}H，对于α/= 0，甚至你好 相关的属性命题4.2对于所有的构造序数α，构造极限λ（和相应的r.r.u.分别命名系统（α + 1）/S和λ/S），他α（/S）他（α+1）（/S）他<λ（/S）他λ（/S）∇⊂ ∇和⊂ ∇α∈CⅡ.A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）5969α（/S）α（/S）1MMMM⊆M∈⊆2−→∗B−→>−→α/S事实上，点集ARk在[7] i其总数的意义上属于HE特征函数χA属于非线性函数。因此，使用[7]的结果我们得到严格的包含。Q为了使Hausdor E-Ershov代数的类中出现的函数局部化，引理3.6可以在可计算分析的框架内被直接地E-E化。我们画了这个布里干酪。有关定义和证明技术的详细信息，请参阅[1]。设Nm是所有离散全函数的集合<$：Nm−→N，m∈N+。它们可以用序 列σ∈Nω 以 规 范 的 双 射 方 式 表 示例 如 ， 设 σm （ n ） =σ m （ γm（n）），其中γm是有效标准N到Nm上的双射。因此，集合A∈NωB也可以由序列σ∈Nω表示，即如果对于某个满足典型上面给出的等式（）。现在，实函数f称为有效可测函数，如果存在（近似）可计算函数g：NωNω这样，无论何时，序列σ表示开集A， A 、B、R，the序列g（σ）表示原像f −1[A]作为ΣB的成员。类似地，我们称一个实函数f∈B-可测i ∈B-有（近似）可计算的函数g，g：NωNω，使得当一个序列σ表示一个开集AR时，序列g（σ）r表示原像f−1[A]，g（σ）表示补像f−1[A]，两者都是的成员。 通过对引理3.6的证明的有效模拟，使用[1]中准备的工具进行的一些技术分析表明，引理4.3如果一个实函数是α/S-toprecursive w.r.t.一些R.R.U.命名为α/S系统，则它是有效的可测的。Q对于点集类，通过考虑点集A<$Rk的离散部分A<$Nk，得到了Hausdor-Ershov层次与Ershov层次之间的关系. 对于函数来说，情况就不那么简单了，因为实际函数f：Rk>−→R到Nk的限制并不一定是离散的。相反，非空离散函数f：NkN，如果它们被认为是实函数，则在第3节的意义下不是连续的，因为域不是开的。然而，离散函数的Ershov族可以通过运算符Q嵌入Hausdor Ershov族中，以指定离散函数f：Nk>−→N连续函数K3Q（f）：R>−→R定义为Q（f）={Ball1（→x）×{f（→x）}：→x∈dom（f）}。命题4.4对于f：Nk>−→N，且任何时候都是r.r.u。系统mα/S，Eα/S我的Q（f）∈HE.实际上，对于离散函数的S-可计算序列F=（f<$）<$α，f∈ F，则实函数Q（F）=（Q（f∈F））<$α的等式S-可计算于00，f∈H70A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）59α/SJα/S1Sν−1（π）。α/Sξ<α/S这是一种感觉。 更进一步，Φ（Q（F） ）=Q（Φ（F））。对于k元实函数的S-可计算序列F =（f <<$）<$α，若Q（f）= Φ（F），则序列FJ=（f <$J）<$<α，其中f <$J= f <$|由离散函数组成，S- 第2节意义上的可此外，Φ（FJ）=f.Q因此，函数类的Hausdor E-Ershov层次结构至少和相关的Ershov层次结构一样丰富。 命题2.1和4.4表明，公司简介公司简介包含不属于αJ<α的任何下界的连续函数。换句话说，存在实函数f∈H =F，其在符号依赖的Hausdor E-Ershov中具有水平α/S层次结构，即，f∈HE\HE . 所以一个真正的函数可以任意高于其连续性水平。那些允许可计算贪婪序列的函数，通过第一值算子来表示它们，是特别有趣的。 对于这样一个函数，它在Hausdor层次结构中的级别与Hau sdor-Er sh o vhierar chy中的级别一致。更重要的是，对于一个来自于domain的t → x，函数valuein→x的计算可以通过计算fa（→x）来进行，仅仅在第一阶段，由于拓扑原因，这是完全可能的。因此，实函数f称为弱（α/S-）可计算的，且存在S-KF-可计算的贪婪序列F=（f<$）<$α，其中f= Φ（F）。一个更苛刻的条件是，如果f（→ x）↓，则它是一个p→y = 0→x，使得f（→ y）=0，则f（→y）=f（→y）↓.更精确地说，实函数f称为安全（α/S-）可计算的，如果存在一个S-KF-可计算的二重序列D=（fn，<$）n< ω，<$<α使得序列Fn=（（fn，<$）<$<α是贪婪的，且Φ（Fn）= f，对所有n∈N，且当verfn，<$（→x）↓时，它是一个pont→y∈Bal l2−n（→x）且hdephf（→y）=<$。D的S-KF-可计算性意味着存在OTMM，使得对于所有points→x，numbersn∈N，(i) iff <$（→x）↓，thenMσ（<$n，m，l<$）↓，对所有ll σ∈CF→x，n，l∈N且m=ν−1（n），它有（Mσ（<$n，m，l<$））l∈N∈CFf（→x）;(ii) 若f∈（→x）↑，则对allσ∈CF→x，allln，l∈N，m=S通过[7]中构建的示例，我们有引理4.5对任意r.r.u.系统α/S，存在一个安全的α/S-可计算函数fα/S：R−→ {0，1}，其中udepth（f α/S）= α.Q因此，fα/S证明存在安全的α/S-可计算的，因此也是弱的α/S-可计算的，在（非有效的）Hausdor层次中的α级函数从[7]中的讨论，还可以得出存在弱可计算（全）函数，它们不是安全可计算的。A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）5971FSFξF−F2通过r.e.的概念，闭集，安全可计算的函数可以被刻画在弱可计算的函数之中.回想一下，点集A∈Rk被称为r. e。闭i <$A =<$N或存在全递归函数<$：N2−→N，则at是poi nts→xn∈Rk的序列e（→ xn）n ∈ NSattisfyingg→q（n，m）→xn<2−m对于一个lln，mN，ndA=cl（→xn：nN），其中cl表示集合的闭包如果一个实函数f是安全的α/S-可计算的，那么连续域的闭包，即， 集合cl（C），<α，一致r. e. 关门了这意味着它是一个递归函数nnn：N3>−→ N，它证明了函数nn n n：N2>−→N，由n n n（n，m）n n（v−1（n），n，m）定义的d是全值的，并且证明了集合cl（C）是r.e.在上述意义上的闭集。反之，给定弱α/S-可计算函数f，使得集合cl（C∈），<α，一致r.e.封闭的，很容易证明α/S-可计算性所以我们有引理4.6弱α/S-可计算函数f是安全的α/S-可计算的，如果集合cl（C∈），α<，是一致r.e. 关门了Q我们在这里结束。 本文提出的概念和结果提供了一个统一的框架，非有效和有效的层次结构的类，所有实函数都是可测的和有效可测的，2 2分别 这为某些功能的从描述集合论和可计算分析的观点来看。然而，应该指出的是，到目前为止，我们只知道一些基本的事实和关系，许多问题仍然是开放的。引用[1] V. Brattka：函数的有效Borel可测性和可归约性。见：2003年CCA会议记录[2] R. Engelking：General topology. Heldermann Verlag，柏林，1989年[3] R.L.爱泼斯坦河哈斯河Kramer：低于0J的集合和度的层次。在：逻辑年1979/80，大学康涅狄格州ed. 由M.Lerman，J.H.R.I.施梅尔Soare. 数学859中的LNSpringer Verlag，32-48[4] Yu. L. Ershov：集合的层次结构。一、二、三。Algebra i Logica，v. 7（1968），no.1，47-74; no.4，15-47; v.9（1970），no.1，34-51（Plenum P.C.英译[5] F. Hausdorr：GrundzügederMengenlehre. W. 德格鲁伊特&公司，BerlinandLeipzig1914;转载：切尔西P.C.，1949年纽约[6] A. Hemmerling：特征的类Euclidean空间。Proceedings of CCA出现在数学逻辑季刊50（2004）72A. Hemmerling/Electronic Notes in Theoretical Computer Science 120（2005）59[7] A. Hemmerling：欧几里德空间中的Hausdor Ershov层次。提交出版[8] P. Hertling：Unstetigkeitsgrade von Funktionen in der e Escherektiven Analysis.论文。Informatik Berichte 208-11/1996，Fern-Uni Hagen（1996）[9] Hertling：拓扑复杂性与连续操作。Journal of Complexity 12（1996），315-338[10] P. Hertling，K. Weihrauch：几何算法的退化水平和精确复杂度下限。第六届加拿大计算几何会议论文集，Saskatoon 1994，第237-242页[11] A.S. Kechris：古典描述集合论。施普林格出版社，纽约，1995年[12] K. -I. 科：请给我看看你的真实情况。 Birkhauser，Bostontal. 1991[13] K.- I. Ko，H.弗里德曼：实函数的计算复杂性。Theoretical Computer Science 20（1982），323-352[14] C. Kreitz，K.Weihrauch：实数和函数的复杂性理论LN in Computer Science 145（1982），165-174[15] 阴号Moschovakis：描述性集合论。北荷兰省， Amsterdam等人，1980年[16] H.小罗杰斯：递归函数理论与有效可计算性。麦格劳-希尔，纽约，1967年[17] K. Weihrauch：可计算分析。 Springer-Verlag，Berlin et al. 2000
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
