Why do almost all points in the unit interval have Kolmogorov complexity 1? Re-posted from math.stackexchange as I did not get any answers there.
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.
 A: I'm not an expert on Kolmogorov complexity, but this does seem like a counting argument: for any fixed $\epsilon > 0$, there are only $\sum_{i = 1}^{(1-\epsilon)n} 2^i < 2^{(1-\epsilon)n+1}$ programs of length less than or equal to $(1-\epsilon)n$, and so fewer than $2^{(1-\epsilon)n+1}$ strings of $n$ bits can be described by such a program. So, if we define $S_{n,\epsilon} = \{x \in [0,1] \ : \ K(x_n) \leq (1-\epsilon)n\}$, then $m(S_{n,\epsilon}) < 2^{-n\epsilon+1}$.
But then $\sum_{n \geq 1} m(S_{n,\epsilon}) < \infty$, so by Borel-Cantelli almost every $x \in [0,1]$ is in only finitely many $S_{n,\epsilon}$. Therefore, for $m$-a.e. $x \in [0,1]$, $K(x) \geq 1-\epsilon$. Now your result follows by applying this to every $\epsilon$ of the form $1/k$ and using the fact that the union of countably many zero measure sets has zero measure.
A: By the Point-to-Set principle (Lutz & Lutz 2018), for any $\varepsilon$ the set of real numbers with Kolmogorov complexity at most $\varepsilon$ has Hausdorff dimension $\varepsilon$. As $\mathbb{R}$ has Hausdorff dimension $1$, any set subset with Hausdorff dimension $\varepsilon < 0$ has to have measure $0$.
The set of all reals with Kolmogorov complexity less than $1$ is then a countably union of null sets, and thus itself null. It's Hausdorff dimension is $1$ though.
This is not the argument Cai and Hartmanis will have had in mind, but I believe this is a very convenient way to reason about such matters.
Lutz & Lutz 2018: https://doi.org/10.1145/3201783
