1.11 Complexity Characterizations of Algorithmic Randomness

1.11.1 Algorithmic Discrepancies¶

We fix some notation for the quantitative discrepancy between a finitary object’s algorithmic entropy and its mass according to some premeasure.

When $\rho = \rho_s$ , simply write $\operatorname{\Delta M}_s$ and $\operatorname{\Delta P}_s$ .

1.11.2 Complexity Characterizations of Algorithmic Randomness¶

It turns out that these algorithmic discrepancies characterize the various $s$ -dimensional randomness notions defined above.

Theorem 1.11.2

Let $s \geq 0$ be left-c.e. and $x \in 2^\omega$ . Then $x$ is:

ML- $s$ -random $\iff$ $x$ is weak Chaitin- $s$ -random: $\operatorname{\Delta P}_s(\restrict{x}{r}) \geq O(1)$ , Tadaki, 2002;
Solovay- $s$ -random $\iff$ $x$ is strong Chaitin- $s$ -random: $\operatorname{\Delta P}_s(\restrict{x}{r}) \to \infty$ , Tadaki, 2002Calude et al., 2006;
Strong ML- $s$ -random $\iff$ $\operatorname{\Delta M}_s(\restrict{x}{r}) \geq O(1)$ , Calude et al., 2006;
Vehement ML- $s$ -random $\iff$ $x$ is strong ML- $s$ -random;
Strong Solovay- $s$ -random $\iff$ $\operatorname{\Delta M}_s(\restrict{x}{r}) \to \infty$ , Miller & Reimann, 2024.

In light of these characterizations, one may argue on the level of discrete or continuous semimeasures rather than covers in order to effectivize results on Hausdorff dimension.

References¶

Tadaki, K. (2002). A generalization of Chaitin’s halting probability Ω and halting self-similar sets. Hokkaido Math. J., 31(1), 219–253. 10.14492/hokmj/1350911778
Calude, C. S., Staiger, L., & Terwijn, S. A. (2006). On partial randomness. Annals of Pure and Applied Logic, 138(1), 20–30. https://doi.org/10.1016/j.apal.2005.06.004
Miller, J. S., & Reimann, J. (2024).