Upper bound on some hightness notions

DOI10.1112/BLMS.12458arXiv2001.09709MaRDI QIDQ6333547

Lu Liu

Publication date: 27 January 2020

Abstract: 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) $le{q}_{mathsfCR}$ does not imply $le{q}_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.

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

This page was built for publication: Upper bound on some hightness notions