Uniform measure of algorithmically random strings

15 Views Asked by At

Def. $1$-randomness [Def. 6.1.1 in Downey & Hirschfeldt] An (infinite) string $w$ is $1$-random if there exists some $c \in \mathbb{N}$ s.t. for all $n \in \mathbb{N}$ it holds that $\operatorname{K}(w_1,...w_n) \geq n-c$ where $\operatorname{K}$ is the (prefix-free) Kolmogorov complexity relative to some universal Turing machine. Let $R_{\exists c} := \{x | x \text{ is 1-random}\}$ be the set of 1-random strings.

Corollary 6.2.6 in [Downey & Hirschfeldt] says that the uniform measure $\mu(R_{\exists c})$ is $1$.

If we change the definition of $1$-randomness to have universal $c=0$ (w.l.o.g.) with the set $R_0$, then it seems that $\mu(R_0) < 1$. For some $n_0 \in \mathbb{N}$ the prefix $0^{n_0}$ has complexity $\operatorname{K}(0^{n_0}) < n_0$, thus each string with prefix $0^{n_0}$ is not in $R_0$. Hence $\mu(R_0) \leq 1-2^{-n_0}$.

Is the uniform measure $\mu(R_0)$ of $1$-random strings with universal $c$ (e.g. $c=0$) equal to $0$ or greater than $0$?