How “random” is “randomness”?

[Schneibster]

Tried to edit and hit some weird bug that wouldn't let me save. If it completes the save, this may be repetitious.

Just so everyone's clear, the fact that Turing was able to prove that we cannot construct a general algorithm that can tell whether another algorithm will halt or not means that we cannot use finite computation (that is, computation in which each step takes a finite amount of time) to determine that a program will produce infinite output; in other words, to find out in a finite period if a computer program can generate infinite Kolmogorov complexity, we would have to use the Turing halting program, which we already have proven cannot exist. It is therefore obvious that the shortest way to find out is to run the program and examine its output to see if it's infinite; which, equally obviously, being a finite computation, takes an infinite amount of time.

 

[cyborg]

You do realize, cyborg, that the Kolmgorov complexity of a string is not computable, right?

The Kolmogorov complexity for any finite string will have a finite upper bound - namely the string itself copied to the output. The issue here is with infinite strings.

A function that could compute Kolmgorov complexity would be the Turing equivalent of the halting function- one that can compute whether another function yields a terminating or non-terminating result. This is a relatively well-known result based on the same characteristic of computation that Godel's theorem rests upon.

What the halting problem tells us is that the only general solution to determining if a program will stop or not is to run it - we cannot determine that by inspecting the program alone.

The problem here is that whilst computing a string given a machine is trivial it is not possible to take an arbitrary infinite string and generate a machine that will generate it - the problem being that one would need to inspect every item in the string. Clearly that would take an infinite amount of time to do.

Your statement therefore boils down to whether it is possible to define a finite machine that can produce an infinite string that is not describable in shorter terms (for example, an infinite string of the character "3" endlessly repeated obviously has a low Kolmgorov complexity).

Not quite: I am trying to differentiate between classes of strings and label them with the appropriate properties:

Finite strings have a finite Kolmogorov complexity and are computable.
Infinite strings with a finite Kolmogorov complexity are computable.
Infinite strings with an infinite Kolmogorov complexity are uncomputable.

As far as randomness goes the last set of strings represents ones which we would have to consider truly random.

We can never know by computation whether randomness exists or not.

If one could prove that strings with infinite Kolmogorov complexity exist this would prove randomness exists - the string would literally be uncomputable.

 

[Ivor the Engineer]

Which World do we wind up in? The answer looks pretty random to me.

Yes, but doesn't it then become a limit on what we can know, rather that it being non-deterministic?

What interpretation of QM do you prefer, if any?

Technically, there aren't any loopholes in Bell's Theorem; either locality is true, or local realism is true. There are various loopholes in the actual tests done. I would not state definitively at this time that all these loopholes are closed in a single experiment; it appears to be the considered opinion of most physicists that closing various loopholes in different experiments is sufficient to decide the matter, and actually that it was really decided by Aspect, and I have to say that I agree. There are bigger and better fish to fry.

That's the impression I got from what I've read too.

 

[Schneibster]

Not quite: I am trying to differentiate between classes of strings and label them with the appropriate properties:

Finite strings have a finite Kolmogorov complexity and are computable.
Infinite strings with a finite Kolmogorov complexity are computable.
Infinite strings with an infinite Kolmogorov complexity are uncomputable.

As far as randomness goes the last set of strings represents ones which we would have to consider truly random.

Problem is, we could never prove they were. At least not by computation.

If one could prove that strings with infinite Kolmogorov complexity exist this would prove randomness exists - the string would literally be uncomputable.

Right, but proving that strings with infinite Kolmogorov complexity exist sounds like a very difficult problem- certainly you can't do it with a computer program.

 

[fls]

OK, here you go:

http://findarticles.com/p/articles/mi_m1200/is_n14_v138/ai_8986262

This discusses how, in classically chaotic situations like rolling dice, the uncertainty of the underlying quantum description of the system increases to permit the chaotic behavior.

Thanks, that's what I was looking for.

Linda

 

[Schneibster]

Yes, but doesn't it then become a limit on what we can know, rather that it being non-deterministic?

All you've done is shift the question back one level; is the observed quantum behavior a random pick from its probability matrix, or is the universe we perceive ourselves as continuing in random? This has always been my problem with MWI. Beyond that, it's not minimal- and nature seems to go in for minimal a lot.

What interpretation of QM do you prefer, if any?

Decoherent histories, also known as consistent histories. Jack Cramer's TI is interesting. The problem with the interpretations is that it's probable we'll never be able to distinguish among them.

 

[cyborg]

Problem is, we could never prove they were. At least not by computation.

I don't see how you could prove they were full-stop.

Right, but proving that strings with infinite Kolmogorov complexity exist sounds like a very difficult problem- certainly you can't do it with a computer program.

I didn't say it would be easy; just that it would be the best description that we can really define for what it means for something to be random.