随机性对比超可加速性

《Information and Computation》：Randomness versus superspeedability

　　

一个实数是左可计算的（left-computable），当且仅当它能被从下方有效逼近。一个实数是可加速的（speedable），当且仅当它拥有这样的逼近，其误差能被某个常数因子无限次加速；它是超可加速的（superspeedable），当且仅当它能被任意因子一致地加速。研究人员回答了Barmpalias提出的一个问题，将可加速实数与超可加速实数分离开来。后两种实数类型融入了近年来日益增长研究中被考察的左可计算实数子类的一个层级结构中。研究人员通过将这一层级与已被充分研究的算法随机性（algorithmic randomness）概念层级并列，为这些研究增添了新视角，并证明存在一个是Schnorr随机（Schnorr random）的超可加速实数。

研究背景与问题由来

在理论计算机科学中，随机性与计算速度及其相互作用占据核心地位。一方面，复杂度理论中P与BPP是否相等这一开放问题，体现了随机源对算法的影响；另一方面，算法随机性（algorithmic randomness）与算法信息论关注随机对象是否可被有效逼近。已有研究建立了左可计算实数（left-computable real）的逼近速度层级，包括可加速（speedable）与超可加速（superspeedable）子类，同时算法随机性也形成了由测试抵抗强度决定的层级，如Martin-L?f随机（Martin-L?f random）与较弱的Schnorr随机（Schnorr random）。Barmpalias曾提出问题：可加速与超可加速实数是否同一？此外，随机性层级与逼近速度层级之间的关系尚未被系统对照。因此，研究人员在《Information and Computation》上发表工作，旨在分离speedable与superspeedable，并将逼近速度层级与算法随机性层级并列，探寻两者交集。

主要关键技术方法

研究人员采用可计算分析中的左逼近（left-approximation）框架：定义左可计算实数为严格递增二进有理数序列之极限；引入速度商ρ(n)=(x_n+1?x_n)/(x?x_n)刻画逼近加速行为。speedable要求lim sup_n→∞ ρ(n)>0（即存在常数因子无限次加速），superspeedable要求可被任意加速因子一致加速。随机性侧使用Martin-L?f测试（测度≤2^?n）与Schnorr测试（测度恒等于2^?n）定义相应随机实数。核心构造方法包括在左可计算实数子类中递归地设计逼近序列，利用停机问题相对化与有效开集测度控制，以及将随机性测试与逼近速度商进行对角化构造，从而分离两类并嵌入Schnorr随机实例。本文无生物样本或队列来源。

研究结果

1. 1.
   Introduction
   引言部分给出左可计算、speedable、superspeedable及Martin-L?f/Schnorr随机的形式定义，明确speedable与superspeedable均属左可计算实数子类，且Schnorr随机严格弱于Martin-L?f随机。研究人员指出先前文献已建立逼近速度层级，但未与随机性层级对照，且Barmpalias问题未解。
2. 2.
   左可计算实数的速度层级（对应原文Left-computable speed hierarchy节）
   通过速度商ρ(n)定义，研究人员证明speedable类严格包含于superspeedable类之并？不，结论恰相反：研究人员构造出属于speedable但不属于superspeedable的左可计算实数，从而分离两概念。具体而言，可设计左逼近使ρ(n)无限次超过固定常数但无法被任意预先指定函数一致加速；而superspeedable要求对任意可计算增长函数g，存在一致机制使误差以g(n)倍加速。
3. 3.
   与算法随机性层级的对置（对应原文Juxtaposition with randomness节）
   研究人员将速度层级（left-computable ? speedable ? superspeedable）与随机性层级（ML-random ? Schnorr-random ? computable-from-random等）并列。关键结果为：存在超可加速实数同时也是Schnorr随机。该构造通过对Schnorr测试开集测度进行精确2^?n控制，并在左逼近中编码加速函数，使实例逃避Martin-L?f测试（非ML随机）但满足Schnorr测试抵抗，从而落于Schnorr随机∩superspeedable。
4. 4.
   分离定理与构造细节（对应原文Separation与Construction节）
   形式化证明分两步：先给speedable\superspeedable实例，利用对角线法使加速因子有界；再给superspeedable∩Schnorr-random实例，在逼近序列中植入可计算函数枚举，保证对任意加速请求k(n)能及时跳步，同时左逼近下界避开Schnorr测试覆盖集（测度总和∑2^?n但单级恰2^?n）。由此回答Barmpalias问题并补全两层级交叠图。

讨论与结论翻译

讨论部分指出，speedable与superspeedable的分离表明逼近速度内部仍有精细结构，不能由“可常数加速”直接推出“可任意一致加速”。将速度层级与算法随机性层级并列后，研究发现随机性并不排斥极高加速能力：Schnorr随机中可容纳superspeedable实数，说明随机对象的不可压缩性与其从左逼近的可加速性非互斥。该结论深化了 computable analysis 与 algorithmic randomness 的桥接，为后续考察ML随机是否含speedable、以及速度层级在相对化计算下形态提供基础。研究人员在结论中写明：本文肯定了Barmpalias所问两类的真包含关系不成立（二者分离），并首次给出Schnorr随机且superspeedable的左可计算实数，确立了随机性-可计算性谱系中的新交点。