The Quest for Randomness
americanscientist.org
americanscientist.org
http://marknelson.us/2012/10/09/the-random-compression-chall...
First you would have to extract the original digits. Since log(10) * 10^6 / log(256) = 415241.01, and the binary file contains 415241 bytes, I assume that the binary file is produced by converting a million digit number to binary.
EDIT: would this be an appropriate place to suggest my ideas for solutions?
I too love Aaronson's writing style, so my work is no substitute for his insights.
I love Scott Aaronson's writing and way of explaining things though. I was thinking how well this article was written before I looked at the author.
Randomness is a subject that fascinates me, as I've been studying how it relates to quantum mechanics. I've arrived at the conclusion that a more useful word that "random" is "unpredictable".
I tend to believe in free will myself and I hate the above argument because I don't know of any way to refute it. As far as I know, the question of free-will vs determinism is unanswered. Even tests of randomness using Bell inequalities requires an assumption of free choice. It's... disquieting.
As far as I know you are correct; there is no way to distinguish if I actually have free will or not.
What I consider as me, my consciousness, is getting fooled in so many ways to think it made decisions it pretty much just observered... that particles making up my grey matter can go this way or that way, randomly, without "me" actually taking any conscious influence on them, doesn't really make a difference to me. It's like the difference between a truly random random number generator, and one that just spits out a pre-determined list; "I" don't get to pick the numbers either way.
When I was younger, I tried to "see where my thoughts come from", and it always seems like they come around some corner, out of some blind spot. I never meditated but I, but I always liked the phrase "watching thoughts arise", because that's how it seems, they come into view of my inner eye so to speak, but the inner eye does not make them, not originally. I can add 2+2, but I can't make me get the idea to add 2+2. Well, actually, I can make myself get the idea to add 2+2, but I can't make myself get the idea to make myself get the idea to add 2+2... and so on. Is it possible to talk about these things without it sounding like esoteric gibberish?
Anyway, I kinda don't think we have free will, not to the degree we like to believe, anyway - but I can't help treating myself and others as if we did. I think life would seem kind of pointless otherwise, certainly anything beyond bacteria and plants, so it might be a necessary illusion for us "higher" life forms.
Why?
Because a truly random one could self-kill, become one where will not exist anymore (of any kind), self-nullify itself, randomly chaos to laws and everything else.
Have a stable "layer" for the universe is not (IMHO) a problem from a designed universe + free will, because the laws that make "free will" need to be stable to make sense and work!
Now, if you are suggesting that my thoughts are somehow outside of the physical world... well, it still wouldn't work with a deterministic world.
If the universe is 'deterministic', that means that given the current state of the universe, there is only a single path the universe can progress down. Every future state of the world is 'determined' by the current state. For example, the location of the water bottle on my desk could be 'determined' if we had perfect knowledge of the state of the universe. However, if I had free will, I could choose to move that water bottle to somewhere else. The universe is no longer deterministic.
The freedom of move the bottle is DEPENDENT of have a location for it, and have a certainty that a)Move exist, and the laws of it can be trusted b) Will move to the location you want to.
So I think that a chaotic universe is more problematic for this problem that a ordered one. Also, I think is possible to have "static" laws but "dynamic" actions, specially because a each step, could exist a limited set of possible outcomes (ie: You can't move to anywhere in the universe the bootle) but the summation of each step provide a path where you are not totally tied, ie, each step is bounded, but the final outcome is random (or random enough) to still make free will the reality.
we don't know if the variables are random and have no way to tell - definitely - if they are independent or identically distributed.
i was always confused when cryptography textbooks only talk about pseudorandomness. probably `import random` is not sufficient for them
and I was also confused by ergodic theory textbooks, which qualify levels of randomness like "equidistributed" or "3-fold mixing" but we can find dynamical systems which only go so far.
that would be an interesting experiment to see what happens to the law of large numbers if the randomness bits are correlated.
Not really related, but I thought it was an interesting connection.
Why is that the case? This just means that the digits are uniformly distributed. Why can't they have a different distribution and still be "random"?
But you're right, you can draw randomly according to a different distribution. However, if you allow any distribution in your definition of "random" then you get the constant distributions. It's not very intuitively random anymore. So the question becomes, how do you pick which distributions are allowed and which aren't?
"The overall Kolmogorov complexity of a string is thus defined as K(x)=|p| where p is the shortest program string for language L such that L(p)=x and we consider all programming languages."
is clearly wrong. You cannot take the minimum over all languages, or over all universal languages, because that leaves K() equal to a constant function.
You really need to fix L. I tried to define the simplest possible language on which to base Kolmogorov complexity and ended up with http://en.wikipedia.org/wiki/Binary_lambda_calculus
Compare to the situation with algorithm complexity. We usually don't attempt to talk about the running time of merge sort by fixing a reference machine on which to do an instruction count. We instead introduce Big-Oh and agree to ignore the differences in constants.
Unless you're Knuth!
The definition of Kolmogorov complexity is not with regard to whatever machine you want. You fix one and only one universal Turing machine U at the beginning, and then you measure the Kolmogorov complexity of a string using a different language with respect to U. Using your notation, K(x) is defined as K_U(x), and you can relate it to K_perl(x) by K_perl(x) + |perl interpreter written in U| = K_U(x). If you wanted to redefine all of Kolmogorov complexity using your L_{perl, i} language, you could do that just fine, but then it's your bad definition that makes the interpretation silly.
Besides, if you pick an otherwise "random" string and single it out as being special, doesn't that intuitively make it no longer random?