26 ms·
Crypto cares a lot about unbiased randomness. X bits of entropy is kind of a measurement of this. Anyway, I suggest you reread the end of that paragraph: “A
by Retric 7y ago
Crypto cares a lot about unbiased randomness. X bits of entropy is kind of a measurement of this.
Anyway, I suggest you reread the end of that paragraph:
“A counting argument is used to show that, for any universal computer, there is at least one algorithmically random string of each length. Whether any particular string is random, however, depends on the specific universal computer that is chosen.”
Kolmogorov complexity is really referring to the fact you can’t have lossless compression of arbitrary bit strings. You can’t encode every possible N+1 bit string using an N bit string. The computer chosen can make an arbitrary 1:1 mapping for any input though. So, it’s got nothing to do with randomness in the context of coin flipping as the mapping is predefined.
Just remember, you’re choosing the computer and at that point any input can be mapped to any output. But, after that point limits show up.
- deleted 7y ago[deleted]
- xornox 7y agoIf all "randomness" of the universe rises from a one extremely long bit string which has been created once from the source of true randomness, the bit string could contain unimaginable number of zeros only and it would be still random. For example, Lotto numbers 1,2,3,4,5,6,7 may be completely random. Kolmogorov complexity works only if we have a big sample of random numbers, but we do not know if we have such in this universe or not.
- Retric 7y agoKolmogorov complexity is only meaningful for a specific architecture. Without access to the architecture of the machine the universe runs on you can’t tell if the initial random string would be one bit or nigh infinite bits.