News for hackers. Stuff that matters.
Re:The enigma of the Ford paradox by Strilanc on Thursday March 07, 2013 @07:35AM (#5337277)
Summary of the Ford paradox (which the post takes forever to actually get to): Quantum mechanics has only periodic orbits, but chaotic systems aren't periodic. How do we reconcile this with the existence of, say, double pendulums?

My guess: because the abstract double pendulum is a model that only approximates real double pendulums. Analogously, computers based on Turing Machines exist despite Turing Machines requiring an infinite amount of space.

---

Also, a minor nitpick: the post seems to equate 'not periodic' or 'chaotic' with 'is random', which I think is misleading. Pseudo-random, I guess, but the output of a simulation of a chaotic system is highly compressible and thus not random in the information theoretic sense.

Re:The enigma of the Ford paradox by Fargren on Thursday March 07, 2013 @08:21AM (#5337420)
Thank you; your minor nitpick doesn't seem minor at all. It was keeping me from noticing I don't see what the problem is. The movement here is deterministic, it's just hard to predict. I don't see the paradox at all.
Re:The enigma of the Ford paradox by codeulike on Thursday March 07, 2013 @08:34AM (#5337477)
Exactly. Chaos can be deterministic. Its sensitive dependence on initial conditions (among other things) that makes it chaotic.
Re:The enigma of the Ford paradox by DougBTX on Thursday March 07, 2013 @08:45AM (#5337513)
When simulating a chaotic system, using different rounding for the floating point values will affect the simulation by a small amount, which a chaotic system is liable to amplify. Quantisation of reality seems to be analogous to rounding floats, in the sense that it affects the precision of the measurements. I'd be interested to know whether that affects the "running" of the system like with floats in a simulation, or if it only puts a limit on how well the initial conditions can be defined.
Re:The enigma of the Ford paradox by arjie on Thursday March 07, 2013 @01:21PM (#5339180)
Doesn't the traditional definition _require_ it to be deterministic? I recall James Gleick describing it that way.
Re:The enigma of the Ford paradox by Kapura on Thursday March 07, 2013 @03:33PM (#5340017)
Chaos is deterministic, but I'm always told that some quantum things are NOT deterministic, i.e. a single photon being exposed to two slits in a paper. My understanding is that the opening it goes through is random; how can that be reconciled with deterministic models of the universe?
Re:The enigma of the Ford paradox by codeulike on Thursday March 07, 2013 @05:38PM (#5340845)
Re:The enigma of the Ford paradox by Xcelerate on Thursday March 07, 2013 @10:18AM (#5338039)
> My guess: because the abstract double pendulum is a model that only approximates real double pendulums.

This subject is somewhat outside of my area of knowledge, but if I had to guess, this is what resolves the paradox. An abstract mathematical chaotic system is different than a real-life one, and it is my guess that if we performed the experiment, we would find the orbits would be different.

QM has withstood every test thrown at it so far, and while it's always possible that a correction to it will be found, I think it will be a very rare event should it happen.

Re:The enigma of the Ford paradox by vannevar on Thursday March 07, 2013 @09:19AM (#5337651)
...the output of a simulation of a chaotic system is highly compressible...

Is that really true? Losslessly? Do you mean the entire phase space, or the sequence generated on any given run? Because I was under the impression that what distinguishes a chaotic system is that the output cannot be predicted in any way other than running the simulation (the article uses the word 'random', but it might be better to say 'unpredictable'). Compressibility relies on exploiting regularities, and regularity is predictability, isn't it?

Re:The enigma of the Ford paradox by Strilanc on Thursday March 07, 2013 @09:30AM (#5337703)
See: Kolmogorov Complexity ( http://en.wikipedia.org/wiki/Kolmogorov_complexity )

The program that simulates the chaotic system is shorter than the unbounded amount of output being generated, and counts as a compression of the output.

Re:The enigma of the Ford paradox by vannevar on Thursday March 07, 2013 @05:14PM (#5340712)
That seems like another way of wording what I said, which is that there is no way to predict the output other than by running the algorithm that generates it. If you are presented only with the string representing the unbounded output, is there any way to reconstruct the algorithm from it? If not, then I would say that the string itself is incompressible; in that case only the string plus the algorithm is compressible in the way you describe.
Re:The enigma of the Ford paradox by Gravityloss on Thursday March 07, 2013 @11:34AM (#5338524)
Sure, but that is kind of circular.

I guess in other words, the more interesting question is this: can we generate hard to compress pseudorandom sequences with simple algorithms - if the algorithm description by itself can not be used as "compression"?

Re:The enigma of the Ford paradox by Fargren on Thursday March 07, 2013 @11:45AM (#5338580)
No. We can't. If the algorithm that generates the sequence is simple, lets call it algorithm X, then a concise way of expressing the string is "the output of algorithm X". That expression losslesly compresses the output, and it's just a few characters longer than the algorithm itself. Randomness theory and information theory study such things.

If you add a rule such as not using Algorithm X, it's trivial to create an Algorithm Y that generates the same output and it's barely any longer than X. For example, by adding any meaningless instruction at the start of algorithm X.

Of course, discovering what the shortest expression for a given sequence is is not a computable problem. So we can't always know if we've found the best form of compression for a sequence, we can only find an upper bound.

Re:The enigma of the Ford paradox by Dylan16807 on Thursday March 07, 2013 @02:11PM (#5339488)
What's a 'simple' algorithm? You can fit a brainfuck interpreter into a single tweet, and from there use the data to handle any other computation.

Or does 'simple' mean like an extractor for a standard archive file? Did you know that RAR is turing complete?

Maybe 'simple' has to be defined by limiting how much execution time you have per output byte?

Re:The enigma of the Ford paradox by MostAwesomeDude on Thursday March 07, 2013 @11:43AM (#5338567)
Absolutely. Consider any number which can be expressed as a patterned continued fraction, like pi or e. pi's digits are such that it is very hard to compress, but it is absolutely trivial to generate. (http://en.wikipedia.org/wiki/Continued_fraction)
Re:The enigma of the Ford paradox by AnthonyMouse on Thursday March 07, 2013 @02:43PM (#5339693)
>Consider any number which can be expressed as a patterned continued fraction, like pi or e. pi's digits are such that it is very hard to compress, but it is absolutely trivial to generate.

You're confusing theoretical compressibility with the actual compression ratios you get when you put a string through typical compression functions.

Here's a different example. Suppose you have ASCII text encrypted with AES with the AES decryption key appended to it. Run that through gzip and you'll probably get output which is larger than the input. But here's a different compression algorithm that will work much better: Decrypt the encrypted data with the key and then compress the plaintext with gzip.

It isn't that the original string is of the sort that can't be compressed, it's that you need a compression function which is suited to the input. Pi is like that.

Compare this to other strings, like the output of an environmental hardware random number generator, which will almost always be totally incompressible whatsoever.

Re:The enigma of the Ford paradox by Fargren on Thursday March 07, 2013 @11:51AM (#5338619)
How is the algorithm that generates the digits of pi a compressed form of pi? It gives me all the information about the number in finite amount of time.

In randomness theory, the definition of the most compressed form of a sequence S is, given a computer C, the shortest program with output S in C.

So the program that generates the output of the simulation of the pendulums is a compression of it's output. Since it's and infinite sequence that can be compressed into a finite program, it is not random from the perspective of information theory or randomness theory.

Re:The enigma of the Ford paradox by yk on Thursday March 07, 2013 @09:47AM (#5337823)
The difference between an chaotic and an non chaotic system is, how small perturbations propagate. In a regular system, you get essentially the same result, even if you start from slightly different initial conditions. In a chaotic one, small perturbations will amplify and therefore the system will end up in a very different state from nearly the same initial conditions. ( And if there is an experimental error, then the final state is essentially random.)