I am reading
- Jin-yi Cai, Juris Hartmanis, On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, Journal of Computer and System Sciences, Volume 49, Issue 3, December 1994.
and I am having a difficult time figuring out an argument they say is obvious.
Define a function $K(x)$ on the unit interval to be $$K(x)=\liminf_{n \to \infty} K(x_n)/n,$$ where $K(x_n)$ is the information constant of $x_n$, the first $n$ bits of $x$ (i.e., the size in bits of the smallest program which will cause a fixed universal Turing machine to produce $x_n$). They make the claim that the set of $x \in \mathbb{R}$ such that $K(x)=1$ has full measure. Why is this? I see that by translation/scaling invariance by rational numbers, it either must have full or zero measure, but I can't make an argument why it must have positive measure. They say it is by a "simple counting argument," which I don't understand.
Note: I re-posted this question to MathOverflow here, where I got a satisfactory answer thanks to Ronnie Pavlov.