Re:Is Probability Real?
by FartyMcFarter on Saturday November 28, 2020 @10:20AM
(#25238036)
> They are both programs with logarithmic Kolmogorov complexity
In the case of true random numbers, how is that so?
Very few random sequences can be generated by a logarithmic-sized program, since most strings are not significantly compressible [1]. A simple counting argument shows that: there are 2^n strings of n bits, but only 2^(lg n) = n logarithmic-sized strings, a much smaller number!
In the case of true random numbers, how is that so?
Very few random sequences can be generated by a logarithmic-sized program, since most strings are not significantly compressible [1]. A simple counting argument shows that: there are 2^n strings of n bits, but only 2^(lg n) = n logarithmic-sized strings, a much smaller number!
[1] http://theory.stanford.edu/~trevisan/cs154-12/kolcomplexity-...