Re-posted from math.stackexchange as I did not get any answers [there](https://math.stackexchange.com/questions/4575919/why-do-almost-all-points-in-the-unit-interval-have-kolmogorov-complexity-1).


I am reading


* Jin-yi Cai, Juris Hartmanis, [On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line](https://doi.org/10.1016/S0022-0000(05)80073-X), 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.



Why do almost all points in the unit interval have Kolmogorov complexity 1?
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.


