There's a challenge posted online to compress a file of one million presumably random digits, and it's been running for 10+ years without anyone claiming the prize:

http://marknelson.us/2012/10/09/the-random-compression-chall...

If it was generated by a physical process, it might be possible that the signal has lower entropy than a truly random signal. It would be interesting to look at n-gram frequencies.

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.

Oh dear, now you've got me started trying to compress that....

EDIT: would this be an appropriate place to suggest my ideas for solutions?

I wrote a more rigor-oriented article on Kolmogorov complexity a while back. HN readers might enjoy: http://jeremykun.com/2012/04/21/kolmogorov-complexity-a-prim...

I too love Aaronson's writing style, so my work is no substitute for his insights.

At an intellectual level I have accepted that quantum mechanics truly are random, but in a small corner of my mind I still believe that the universe is deterministic.

The article on Bell inequalities that Aaronson promised is coming should be of interest to you then. Determinism, free-choice, causality, and randomness all intertwine and could make appearances in that article. It's fascinating, but mind-raping stuff. I look forward to this article myself!

I think it's fair to say that's a reasonable coping mechanism for staying sane. QM notoriously has no everyday analog, whereas determinism holds up reasonably well in daily life!

I feel the opposite... determinism does NOT fit with my day to day observance, because my perception is that I have free will. If I accept determinism, I also have to accept that I actually don't have free will, and that seems contrary to my perception of myself.

So, what if some omnipotent trickster/adversary/god designed a deterministic universe specifically to fool you into thinking you have free will?

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.

My point wasn't that the world COULDN'T be deterministic BECAUSE I have free will... I was saying that the world NOT being deterministic fits better into my own perception of how the world works, since it appears to me that I have free will.

As far as I know you are correct; there is no way to distinguish if I actually have free will or not.

Not trying to tell you what you should think about your own free will, but here's what I think about mine:

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.

Following that line, a deterministic universe is a better vehicle for free will that a truly random one.

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!

I don't follow your logic... if the universe is deterministic, then I can't have free will; my behavior is 'determined' by the current state of the universe. I can't change that through any act of will, therefore I do not have free will. If I have free will, then the universe is necessarily not deterministic, since I could choose between (at least) 2 actions that would lead to different future states of the universe.

If the universe is deterministic than you can change the future obviously, since the future state of the universe depends on the actions you take in the present. If the universe is random then the future state doesn't depend on the current state. Existence is meaningless chaos and you have no control over anything, even your own actions. Your thoughts would be nothing more than meaningless dice rolls that have no correlation with reality, or anything.

Why you link your thinking with the sub-atoms? Why do you think that if the sub-atoms are deterministic your thinking can't decide?

Because all of my thoughts are represented someway in the physical world. My thoughts are just neurons interacting.

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.

I still don't see why hard link both. In a truly random universe, the location of the bottle is a nonsense answer (or more exactly: is random). You can ask that. The bootle could, suddenly, not be there, so you can't decide where move the bootle.

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.

Why does it matter? Your actions are either determined by random dice rolls or cause and effect.

Is the problem "free will", or "I" ?

I am not sure what you mean by 'problem'.

And then the question of religion fundamentally becomes "are quantum mechanical effects deterministic".

Isn't many-worlds an explanation for how the universe can be deterministic but appear random?

Darn, the article stopped right before it got to the interesting part in my opinion.

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".

Scott writes very well. And he writes some of the lengthiest technical posts I have read. I find writing one paragraph of technical writing akin to chewing diamonds. Don't know how he does it. I have been lurking on his blog for some time and I have learned a great deal.

And unpredictability depends on the information available to the observer. Thus randomness is objectively subjective.

I've done some work with monte carlo and discrete event simulation. The runs/iterations produced utilize psuedo-random number generation. Many discrete-event simulation software platforms reproduce exactly the same numbers on a given run. Also, monte carlo simulation software like @Risk and CrystalBall enable users to select psuedo-random number generation methods. For instance, utilizing the Latin Hypercube method will sample more evenly from a Gaussian distribution rather than pulling more from the peak and tails.

so much for i.i.d. random variables.

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.

I think the guy working on TempleOS is basing his concept on the idea that computers can provide some sense of "randomness".

Not really related, but I thought it was an interesting connection.

I think he is appealing to intuition here, where randomness means you can't predict the next drawn value with accuracy better than uniform.

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?

Kolmogorov complexity as a measure of randomness / information content has problems in my opinion: http://www.forwardscattering.org/post/7

Your claimed definition:

"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

That bias with a fixed L is present, but you already mentioned the answer in your article: the difference is bounded.

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.

> 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.

Unless you're Knuth!

The difference is not really bounded in a meaningful way. The bound is large enough that the complexity can go to zero in some language.

I think your contention (if you're the author of this post) is misguided. In particular, the "languages" you define have the string hard coded in their definition, and are hence at least as long as the string you want to encode. In other words, your additive constant is not universal.

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?

Hi, My overall point is that it matters which UTM you pick at the beginning.

Thanks for the detailed reply, I'll ponder upon it and reply in a bit :)