News for hackers. Stuff that matters.
Re:Don't forget randomness is still just a hypothesis (2006) by Retric on Sunday August 11, 2019 @10:02PM (#20671866)
> Kolmogorov random if, for a given universal Turing machine, there is no program shorter than the string that produces the string.

That’s not a definition of unbiased randomness. A true unbiased random number could be all 0’s. Nothing about an unbiased random number demonstrates it’s random, otherwise whatever that distinction is would be a bias in it’s generation.

Kolmogorov complexity is it’s own thing, and sequences that seem very complex can have extremely low complexity. Such as long sequences of hashes of hashes.

Re:Don't forget randomness is still just a hypothesis (2006) by Xcelerate on Sunday August 11, 2019 @10:33PM (#20671964)
I'm not sure what unbiased randomness is. I haven't heard that phrase before. For Kolmogorov randomness, I was using Wikipedia's description of it (https://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogor...), although there are more technical descriptions available.
Re:Don't forget randomness is still just a hypothesis (2006) by Retric on Sunday August 11, 2019 @10:59PM (#20672046)
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.

Re:Don't forget randomness is still just a hypothesis (2006) by xornox on Monday August 12, 2019 @06:56AM (#20674271)
If 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.

Re:Don't forget randomness is still just a hypothesis (2006) by Retric on Monday August 12, 2019 @12:07PM (#20676723)
Kolmogorov 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.

Re:Don't forget randomness is still just a hypothesis (2006) by rerefreshment on Sunday August 11, 2019 @11:58PM (#20672302)
I haven’t really heard much talk about “Kolmogorov randomness” before, and so I’m wondering if you might be running up against the limits of the Wikipedia paradigm when it comes to pioneering scholarship.

The citation for that paragraph is a peer-reviewed journal article covering Kolmogorov complexity and randomness. It’s actually a really good article, by someone pretty famous named Per Martin-Löf. Which is all great, except that paper is from 1966, and in 2019 a more studied concept is something called “Martin-Löf randomness” :)

Re:Don't forget randomness is still just a hypothesis (2006) by cameldrv on Sunday August 11, 2019 @11:06PM (#20672072)
Well they're related. There is a slightly circular argument that, since it's impossible to determine for sure what the Kolmogorov entropy of a sequence is, the only way to generate a long sequence with high Kolmogorov entropy with high probability would be to use truly random numbers. Any pseudorandom shortcut has by definition lower Kolmogorov entropy as long as the generating program is shorter than the sequence.
Re:Don't forget randomness is still just a hypothesis (2006) by pron on Monday August 12, 2019 @04:55AM (#20673682)
A random string, in this case, is a string whose bits (or characters) are random, and the definition talks about the process that produces those bits. A string of all zeros (i.e., in this perspective, a process that produces only zero bits) is not random, but a short subsequence of a random string could be all zeros.