跳跃的低性与逼近

理论计算机科学电子笔记143（2006）45-57www.elsevier.com/locate/entcs跳跃的低性与逼近Santiago Figueira圣地亚哥·菲盖拉1，4布宜诺斯艾利斯大学计算机科学系阿根廷和r'eNies2奥克兰大学计算机科学系新西兰Frank Stephan弗兰克·斯蒂芬3，5新加坡国立大学计算机科学与数学系新加坡摘要通过加强跳可溯性和ω-r. e的概念，研究和比较了跳的强可溯性和集合的自然的数字。证明了存在一个不可计算的强跳迹集，如果A是好逼近的，那么A是强跳可追踪的。对于r.e.集，反之也保持我们的特点跳跃溯源性和相应的强变种Kolmogorov复杂性，我们调查这些低概念的其他属性。关键词：低值、溯源性、ω-r.e. K-平凡性，Kolmogorov复杂性1 电子邮件地址：sfigueir@dc.uba.ar2 电子邮件地址：andre@cs.auckland.ac.nz3 电子邮件地址：fstephan@comp.nus.edu.sg4个S. FIGUEIRA是一个由F和ACionAntor chas组成的集团。5楼。Stephan部分由NUS资助编号R2521571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.05.02546S. Figueira等人/理论计算机科学电子笔记143（2006）451引言一个集合A的低度性质表明A在用作预言机时是计算弱的，因此A接近于可计算的。在这篇文章中，我们研究和比较了一些一个集合是K-平凡的，当它在柯尔莫哥洛夫复杂度方面是高度可压缩的（见第2节的正式定义）。 在[8]中，Nies证明了当A是L-随机集时，集是K-三次集，且当A是L-随机集时，集是K-三次集. e. 即Martin-L？of-random集也是随机的.Terwijn和Zambella [12]定义了一个集合A是递归可迹的，如果存在一个递归界p使得对于每个f ≤TA，存在一个递归r使得对于所有x，|Dr（x）|≤p（x），且（Dr（x））x∈N是f的可能值集：对所有x，有且f（x）∈ Dr（x）.他们表明，这种组合概念的特点是低的施诺尔测试集。这一点在[9]中被修改为跳转可追溯性。一个集合A是跳跃可迹的，如果它在参数e处的跳跃，写作JA（e）={e}A（e），有几个可能的值。定义1.1A一致的r.e.族T ={T0，T1，.. . 是一个迹，如果存在一个递归函数h使得|Tn| ≤ h（n）。我们说h是T的界。集合A是跳可迹的，如果存在迹T使得<$e[JA（e）↓ <$JA（e）∈Te]。 我们说A通过函数h是跳迹可溯的，如果另外T有界h。[9]中研究的另一个概念是超低，首先在[2，7]中引入定义1.2集合A是ω-r. e。如果存在递归函数b使得A（x）=lims→∞g（x，s）对于递归{0，1}-valdg使得g（x，s）至多变化b（x）次.在这种情况下，我们说A是ω-r. e。通过函数g和边界b。A为超低i型，AJ为ω-r. e。在Turing可约性下，跳迹集和超低集都是向下闭的，并且是广义向下闭的（即： AJ≤AJ）。在[9]中，研究并比较了跳跃-两个低的概念在r.e.中一致但他们中的任何一个都不意味着另一个在ω-r.e.内。集.在这篇文章中，我们定义了强跳跃可溯性（见定义3.2）和良好可逼近性（见定义4.1）的概念，通过加强跳跃可溯性和ω-r. e.的概念，分别特别强调了A的跳跃为ω-r. e的情况。这些概念的强变体将所有阶视为界，而不仅仅是某些递归界。S. Figueira等人/理论计算机科学电子笔记143（2006）45472SD在这里，阶是一个缓慢增长但无界的递归函数（见定义3.1）。我们的主要成果包括：• 存在不可计算的强跳迹集;• 如果AJ是好逼近的，则A是强跳可迹的。反之亦然，如果A是r.e.我们的方法被用来研究与普通和无前缀的Kolmogorov复杂性相关的有趣的低属性我们研究了集合A的性质，使得相对于A的Kolmogorov复杂度只比非相对化的小一点我们证明了跳跃可溯性及其强变体的一些特征，分别在无前缀（用K表示）和普通（用C表示）Kolmogorov复杂性• A是跳跃可追踪的当且仅当存在递归p，其增长速度比线性增长快，使得K（y）被p（KA（y）+c0）+c1所限制，对于某些常数c0和c1;• A是强跳迹的当且仅当C（x）−CA（x）有界h（CA（x）），对每一阶h和几乎所有x.我们知道K-平凡性蕴涵跳跃可溯性，但不知道K-平凡性是否蕴涵强跳跃可溯性。相反的方向也是2基本定义如果A是一组自然数，则A（x）= 1，如果x∈A;否则A（x）=0. 我们用ATn表示长度为n的字符串，A（0）. A（n− 1）.如果A被给定一个0-逼近，并且是一个泛函，我们写 A（e）[s] forAs（e）。 从一个本原递归严格增函数α出发，可以得到一个本原递归严格增函数α，称为α的归约函数，使得αX∈X（e）=JX（α（e））.对于每个实数A，我们想定义KA（y）为使用oracleA对y的最短无前缀描述的长度。 Oracle机器是一个部分递归的函数M：{0，1}∞×{0，1}<${0，1}<$。 我们将MA（x）表示为M（A，x）.M是一个Oracle无前缀机器，如果MA的定义域是一个包含字符串的反链，对于每个A。设（Md）d∈N是所有Oracle无前缀机器的有效列表universal oracleprefix-free machineU由下式给出：UA（0 d 1 σ）= MA（σ），相对于A的无前缀Kolmogorov复杂度定义为KA（y）= min {|σ|：UA（σ）= y}，其中|σ|表示σ的长度。如果A= σ，我们简单地写U（σ）和K（y）。 通常，U（σ）[s] ↓=y48S. Figueira等人/理论计算机科学电子笔记143（2006）45表 示 U （ σ ） =y ， 计 算 最 多 需 要s 步 。 我 们 称A∈{0 ， 1}∞ 是 Martin-Lofrandomi∈c∈nK（ATn）>n−c。 设A是K-平凡的i ∈c∈n K（ATn）≤K（n）+c.Keraft-ChaitinTheorem说明了从一个集合中获得的不可计数值ni对序列（<$ni，σi <$）i∈N（称为公理），使得i∈N2−≤ 1，我们可以有效地获得一个无前缀机器M，使得对于每个i都有一个τi的长度为ni，M（τi）↓=σi，且M（ρ）↑，除非对某个i，ρ=τi。如果我们放弃MA的定义域是反链的条件，我们得到一个类似的概念，称为简单柯尔莫哥洛夫复杂度，用C表示。因此，CA（y）将表示使用oracleA的y的最短描述的长度，当我们没有对域的限制时二进制机器是一个部分递归函数M：{0，1}×{0，1}›→{0，1}个。 LetU是一个二元单值函数，即，U∈（0d1σ，x）=M∈d（σ，x），其中（M∈d）d∈N是两个变元的所有部分逆函数的集合.我们定义了简单的条件柯尔莫哥洛夫复杂度C（y|x）作为使用U的短序列描述的长度，其中字符串x作为序列参数，I.E. C（y|x）=min{|σ|：U∈（σ，x）=y}.让tstr：N→{0，1}表示字符串的标准计数。字符串str（n）是二进制序列b0b1.二进制数1b0b1. m的值为n + 1。因此，str（0）=λ，str（1）= 0，str（2）=1，str（3）= 00，str（4）= 01等等。3强跳跃跟踪回想一下，一个R. E。集合A是迅速单的，如果A是余无限的，并且存在递归 函 数 p 和 A 的 有 效 逼 近 （ As ） s∈N ， 使 得 对 于 eache ，if|We|=∞then<$s<$x[x∈We，s\We，s<$x∈Ap（s）\Ap（s）−1]. 在本节中，我们引入了一个更强的跳跃可追溯性版本，并证明了有一个迅速简单的（因此非递归的）强跳跃可追踪的集合。我们还证明了，没有最大阶作为界的跳跃可溯性。定义3.1函数h：N→N+是一个递归函数，其中h（x）≤h（x + 1）和limx→∞h（x）= ∞.注意，任何归约函数都是一个阶。定义3.2一个集合A对每一阶h都是强跳可迹的，A是通过h跳可迹的。显然，强跳跃可溯性意味着跳跃可溯性，并且不难看出，强跳跃可溯性在图灵约简下是向下封闭的。S. Figueira等人/理论计算机科学电子笔记143（2006）4549注意，如果A是递归的，那么A是强跳跃可追踪的，因为如果J A（e）↓，我们可以通过Te={J A（e）}来追踪跳跃，否则Te={ J A（e）}。下面的定理3.4为了证明这一点，我们需要下面的引理，它说明存在一个函数的增长速度比所有阶都慢，并且从上面递归逼近。引理3.3存在g：N→N使得(i) 其中g（s，x）=gs（x）是递归的且gs（x）≥（x，x）;(ii) limx→∞g（x）=∞;(iii) 对于所有的阶h，g（x）≤h（x），几乎对所有的x。证据定义Gs（x）= x +max {xe，s（y）：xe，s（y）↓ xe≤xx xy≤x}。显然，G（s，x）=Gs（x）是递归的，并且很容易看出，对所有x，Gs（x）≤Gs+1（x），对所有s，Gs（x）Gs（x+ 1）。<对所有的e≤x，也有Gs（x）≥εe，s（x）.让我们定义G= lims→∞Gs。则G比任何递归函数都增长得快，也就是说，如果定义了εe（x），则对所有e≤x，G（x）≥εe（x）。现在让我们定义 由于Gs是递归的且在x上单调递增，因此gs是递归的且gs≥gs+1。这证明（一）。G是无限的，因为G是。（2）满足。对于（iii），设h为任意阶。函数H（x）= min {y：h（y）≥x}是递归的，因为h是无界的。然后，有e使得H=e。通过G的构造，证明了<$x[x≥e<$G（x）≥H（x）]. 我们将证明g（y）= max{x：G（x）≤y} ≤h（y），对所有y≥G（e）和g（y）≥e.固定y≥G（e），并假设x≥e且G（x）≤y。因为h是单调的，所以h（G（x））≤h（y），并且因为H在G之下超过e，所以h（H（x））≤h（G（x））。通过H的定义，h（H（x））≥x，从而最终得到x≤h（y）。Q定理3.4存在迅速简单的强跳可迹集。证据 我们分阶段构造了一个迅速简单集A，Pe：|We|=∞<$$>s<$x[x∈We，s\We，s−1<$x∈As\As−1]。在构造过程中，Pe可以在阶段s破坏JA（k），但条件是e gs（k）.A.A. 设gs是引理3.3中定义的。阶段0：设置A0= 0。阶段s+ 1：选择最小的e≤s，使得• Pe尚未满足;50S. Figueira等人/理论计算机科学电子笔记143（2006）450• 存在x，使得x∈We，s+1\We，s，x >2e，且对所有k，gs（k）≤e，如果定义了JA（k）[s]，则x大于JA（k）[s]的使用如果这样的e存在，把e的最小x放入As+1。我们说Pe在阶段s+ 1受到注意，并宣布Pe满足。否则，As+1=As。最后，定义A=sAs。核实。显然，Pe最多只受到一次关注。所以我们可以在下面使用这样一个事实，即每个需求最多只枚举A一次。为了证明A是强跳跃可追踪的，固定一个递归阶h。我们将证明存在一个r. e。如定义1.1中的JA跟踪T。设h为任意秩序根据引理3.3，存在k0使得对所有k≥k0，g（k）≤h（k）.定义递归函数f（k）= min{s：gs（k）≤h（k）}，如果k≥k0，否则f（k）= 0。对于k≥k0和s≥f（k），gs（k）将低于h（k），因此JA（k）可能会改变，因为Pe受到关注，对于egs（k）≤h（k）。<以来每个Pe最多接收一次注意，JA（k）在阶段f（k）之后最多可以改变h（k）所以. {JA（k）[s]：JA（k）[s]↓<$s≥f（k）}如果k≥k;Tk={JA（k）}如果JA（k）↓<$k k0;否则的话。是必需的。确定e，使得We是无限的，让我们看看Pe是满足的。 让我们这样做，k[g（k）≤ SJ使得对于所有k，其中gt（k）≤ e，如果JA（k）收敛，则计算从阶段t开 始 是 稳 定 的 。设tJ≥tsuc，则 存 在x∈We ，tJ+1\We，tJ，x>2e，且x大于所有k的全体收敛JA（k）的使用，其中tJ（k）≤e.现在，要么Pe已经满足，要么Pe在阶段tJ+1受到关注。在任何一种情况下，Pe都满足。Q研究了跳跃可溯性的一个极大界的存在性给定一个阶h，是否总是有可能找到一个跳可迹集A，使得h太小而不能成为A的跳的任何迹的界？下一个定理肯定地回答了这个问题。理论m3.5F或任何其他理论都是一种理论。 设A和一个或一个h，即A是通过h跳到的，但不是通过h跳到的。等证据我们将定义一个辅助函数f，并使用α，f的归约函数（即对于所有X和e，fX（e）=JX（α（e））），这是由递归定理预先确定的。同时，我们将定义一个r.e.。集合A和迹S. Figueira等人/理论计算机科学电子笔记143（2006）4551T为JA。最后，我们将证明，有一个没有秩序的障碍。设T（0），T（1），. 是具有界h的所有迹的枚举，使得T（e）={T（e）0，T（e）1，. . }，第e个这样的迹，如定义1.1所示。要求Pe试图表明JA不能通过具有边界h的迹T（e）来追踪，即，Pe：<$x<$A（x）∈/T（e）α（x）而要求Ne试图在跳跃被定义时使其稳定，即Ne：[∞s JA（e）[s] ↓] ⇒JA（e）↓.单个过程Pe的策略由初始动作和可能的后续动作组成。阶段s+ 1的初始行动：• 选择一个新的候选项xe=ne， n nn，其中n是Pe已初始化。 定义A（xe）[s+ 1] = 0，有很大的用途。阶段s+ 1的行动：• 设xe= xe，nn n是当前候选项。 将y代入As+1，其中y是定义的函数A（xe）[s]的用法。请注意，由于y的选择，此操作将不会对i e执行检查JA（i）[s];• 定义A（xe）[s+ 1] =A（xe）[s]+ 1，其中使用yJ> y，并且大于对i e使用JA（i）[s+ 1]的所有定义的计算。如果JA（e）[s]是第一次被定义，我们说Pe在s+ 1阶段需要注意，如果JA（e）[s]∈T（e）α（xe）[s我们定义T={T0，T1， . . . 我知道了。Ti的第s个阶段将被表示为b y Ti[s]. 对于所有i，我们从A0=和Ti[0]=开始。 Atsages+1we考虑过程Nj，j≤s，Pj，js，Peacts和ches改变了T（xe）α（xe）的 定义，使T（xe）α（xeSince|T（e）α（xe）|≤h（α（xe）），则有SJ>s满足T（e）α（xe）[SJ]=T（e）α（xe）.通过构造，证明了σA（xe）[SJ+1]∈/T（e）α（xe）和σA（xe）[SJ+1]是成立的.我们说Ne在阶段s+1受伤，如果我们把y放进As+1，并且y≤JA（e）[s]的用法我们将cP（k）定义为Pr的初始化次数的界，其中r≤k;将cN（k）定义为Nr的损伤次数的界，其中r≤k。由于P0只初始化一次，并且在A中最多进行h（<$0，0 <$）次改变，因此cP（0）= 1和cN（0）= h（<$0，0 <$）。初始化Pk+1的次数受Nr作用的次数限制，对于r≤k，因此cP（k+ 1）=cP（k）+cN（k）。每当Nr受到伤害时，对于r≤k，则Nk+1也可能受到伤害;此外，每当Pk+1改变A时，Nk+1也可能受到伤害。 对 于 Pk+1的初始化，最后发生在m=h（k+1，i）处。亨斯cN（k +1）= 2 cN（k）+i≤cP（k+1）h（k =k + 1，i= k）.当JA（e）↓ 时，nJA（e）∈T∈e，则ceNe不再受损。 如果JA（k）的变化次数至多等于Ne的损伤次数，则对于迹（T_i）i∈N ， 定 义 了 周 期 为零的函数h_i（e）=c_N（e）.Q它仍然是开放的，如果没有最小限度的跳跃可追溯性，即。是如果给定一个未知数，则存在一个集合A和一个未知数，该集合A和未知数是通过路径可跟踪的跳变，而不是通过路径可跟踪的跳变。4跳跃的良好逼近性使得A是加强了超低性的概念，研究了超低性与强跳迹的关系。定义4.1一个集合A对每一阶b都是良好可逼近的，A是ω-r. e。 viaB.显然，如果AJ是良好可逼近的，那么A是超低的，并且不难看出良好可逼近性在图灵约简下向下闭合。然后我们证明，如果A是r.e.则A是强跳可追踪的i且AJ是良好可逼近的。我们首先需要以下引理。引理4.2设f和f∈是阶，使得对几乎所有x，f（x）≤ f∈（x）。(i) 如果A是通过f可跳迹的，则A是通过f可跳迹的;(ii) 如果A通过f是良好可逼近的，则A通过f是良好可逼近的。引理4.3存在一个递归γ，使得对所有的r. e. 答：(i) 如果A是通过订单h跳可追踪的，则A是通过订单b（x）= 2h（γ（x））+2;S. Figueira等人/理论计算机科学电子笔记143（2006）4553222(ii) 如果A通过订单b是超低的，则A通过订单是跳跃可追踪的h（x）=[1b（γ（x））].证据遵循[9，定理4.1]的证明，连同引理4.3。Q定理4.4设A是r.e.集 则以下是等价的：(i) A是强跳跃可追踪的;(ii)J是很好的近似。证据（i）第（ii）款。给定一个阶b，我们证明A通过b是超低的。根据引理4.3的第i部分，它可以定义一个阶h，使得对于所有x，2h（γ（x））+ 2≤b（x）。 如果b（x）≥4，则定义h（γ（x））=[ b（x）−2]，如果b（x）4，则定义h（γ（x））= 1。<由于γ可以取严格单调，所以上述定义是正确的，我们可以将它完善，使h成为一个序。（ii）第（i）款。给定一个阶h，我们将证明A通过h是跳可迹的。根据引理4.3的第ii部分，它可以定义一个阶b，使得对几乎所有的x，[1b（γ（x））<$≤h（x）。这个论点与前一个案例相似。Q稍后，在推论5.4中，我们将改进这个结果，并且我们将看到，实际上，蕴涵（ii）<$（i）对任何A都成立。我们通过证明一个良好可逼近集A的前缀ATn具有n阶对数的低柯尔莫哥洛夫复杂度来结束这一节。因此，A不是随机的Martin-L？，而且，E的Hausdor维数为0。后者相当于说不存在c >0使得cn是ATn的无前缀柯尔莫哥洛夫复杂度的线性下界，几乎对所有n。定理4.5若A是好逼近的，则对几乎所有的n，K（ATn）≤4 |n|.证据设A（n）= lims→∞g（n，s），其中g是递归的，至多变化n次. 给定n，存在唯一的s和某个m n，使得g（m，s）g（m+ 1，s），但对所有t > s和q n，g（q，t）=g（q，t+ 1）。也就是说，s是g收敛到n以下的时间，m是最后一次变化发生的地方。 阶段s可以从m和数量kg（m，t+1）g（m，t）.所以我们可以从m，n，k计算出ATn。由于k，m≤n，所以对于几乎所有的n，可以用4中的无前缀方式对m，n，k进行编码。|n|很多比特。 这是通过使用一个前缀的形式1q0后接2q表示n的2个比特、表示m的2个q比特和表示k的2个q比特作为二进制数;这里q仅仅是使得2个q比特足够的最小数 由于k，m ≤ n，且由于2 q ≤ |n|+ c对于某个常数c，并且由于将上述表示变换为针对U的程序所需的额外必要的编码由常数限制，因此存在常数d，使得54S. Figueira等人/理论计算机科学电子笔记143（2006）45XXnK（ATn）≤ 3 |n|+的|n|/2+ d，则关系K（ATn）≤ 4 |n|几乎所有的n都成立。事实上，使用二进制记法来存储q而不是1 q 0，它甚至会给出K（A Tn）≤ 3（|n|+ log（|n|））对于几乎所有的n。Q5可追踪性和简单的Kolmogorov复杂度我们用简单的Kol- mogorov复杂性给出了强跳可溯性的一个刻画，并证明了：如果AJ是良好可逼近的，则对任意集合A，A都是强跳可溯的.定理5.1若AJ是好逼近的，则对任意阶h和几乎所有x，C（x）≤CA（x）+h（CA（x））.证据 对于任何函数f，定义f∈（y）= y+ f（y），对所有y。设A（m，n，q）是一个泛函，它做以下事情：(i) 计算x=UA（q）。如果UA（q）↑，则<$A（m，n，q）↑;(ii) 找到第一个程序psuchthat|p|=n且U∈（p，q）=x. 如果e不是这样的p，则<$A（m，n，q）↑;(iii) Incasem∈/[1，n]then<$A（m，n，q）↑.如果p的第m个比特为1，则<$A（m，n，q）↓，否则<$A（m，n，q）↑。设α是一个约化函数，使得JA（α（m，n，q））=<$A（m，n，q），h0是一个n阶约化函数. 由于h=[h0/2]也是一个阶，所以有一个关于h C（x）≤h∈（CA（x））+c的常数c对于所有的mostx，这意味着对于所有的mos t x，C（x）≤h∈0（CA（x））. n（n，n，q）=n（|Q|）对于所有n，q.设 qx 是x 的 极小 A-规 划， 即 UA （ qx ） = x ， |Qx|= CA （ x ） 。设 nx= C（x|qx）。则n = A（m，nx，qx）↓ i = p x的第m位为1，其中px是第一个程序集such，|px|=nx且U∈（px，qx）=x.由于AJ是ω-r.e.通过b，px= AJ（α（1，nx，qx））. AJ（α（nx，nx，qx））变化最大nxmax {b（α（m，nx，qx））：1 ≤ m ≤ nx}≤ nxb（α（nx，nx，qx））≤ n2h（|Qx|）我有很多次。 由于U_j（p_x，q_x）=x，我们可以将p_x与h_n_x，q_x以及A_J（α（1，n_x，q_x））. AJ（α（nx，nx，qx）），我们有（1）nx= C（x|qx）≤ 2 |nx|+的|2019 - 02 -22 00：00：00 |Qx|）|+O（1）≤4 |nx|+的|（|Qx|）|+O（1）。为了完成，让我们证明几乎对所有x，nx≤ 2|（|Qx|）|+O（1）。以来C（x）≤|Qx| O（1），O（2），O（1），O（2），O（3），O（4）C（x）≤|Qx|+h（|Qx|） +O（1）=h（CA（x））S. Figueira等人/理论计算机科学电子笔记143（2006）4555+O（1），56S. Figueira等人/理论计算机科学电子笔记143（2006）45对于几乎所有的x，正如我们所希望的。因 此 ，让我们看到nx≤ 2|（|Qx|）|+O（1）对于几乎所有的x。存在一个常数N，使得对于所有n≥N，|n| ≤n。我们知道，对于几乎所有的x，qx满足|（|Qx|）|≥ N。 假设x 有 这 个 性质。当 nx≤| （ |Qx| ） | 或 4|nx|≤nx/2 。在 这 个 例 子 中 ，dcasenx−4|nx|≥nx/2andby（1），nx/2≤|（|Qx|）|+O（1）。因此，在 另一个例子中，我们有nx≤ 2|（|Qx|）|+O（1）。Q给我5分。2对于allx∈{0，1}n且d∈N，|≤O（d 4 2 d）.| ≤ O (d4 2 d).定理5.3下列等式等价：(i) A是强跳跃可追踪的;(ii) 对任意阶h和几乎任意x，C（x）≤CA（x）+h（CA（x））.证据（ii）第（i）款。 因为最多有2个长度为

下载后可阅读完整内容，剩余1页未读，立即下载