论文标题
上界的某些高度概念
Upper bound on some hightness notions
论文作者
论文摘要
我们为计算随机性理论中的几种殿堂特性提供了上限。首先，我们证明，离散的覆盖属性并不意味着计算1随机真实的能力，回答了格林伯格，米勒和尼斯的问题。这也意味着一组无限的不可压缩字符串并不一定会提取1随机的真实。其次，我们证明，鉴于一棵均匀的二进制树，该树不承认无限的可计算路径，这是一系列有界的玛特宁格（Martingale），其初始资本往往为零，因此存在一个无限的Martingale $ s $，以至于它们中的任何一个都不是$ s $都不会计算一棵树的无限路径。这意味着1）高（CR，MLR）并不意味着PA的完整性，回答了Miller的问题； 2）$ \ leq _ {\ mathsf {cr}} $并不意味着$ \ leq_t $，回答了NIE的问题。第二个结果的证据表明，通用C.E.的编码能力Martingale在于其无限差异。
We give upper bound for several highness properties in computability randomness theory. First, we prove that discrete covering property does not imply the ability to compute a 1-random real, answering a question of Greenberg, Miller and Nies. This also implies that an infinite set of incompressible strings does not necessarily extract a 1-random real. Second, we prove that given a homogeneous binary tree that does not admit an infinite computable path, a sequence of bounded martingale whose initial capital tends to zero, there exists a martingale $S$ majorizing infinitely any of them such that $S$ does not compute an infinite path of the tree. This implies that 1) High(CR,MLR) does not imply PA-completeness, answering a question of Miller; 2) $\leq_{\mathsf{CR}}$ does not imply $\leq_T$, answering a question of Nies. The proof of the second result suggests that the coding power of the universal c.e. martingale lies in its infinite variance.
