Chaos vs pseudo-random process

[Juan Largo]

Numbers generated by a pseudo-random process will eventually repeat, which is how PR processes can be differentiated from a truly "random" process. Some chaotic processes follow closed trajectories in state space; i.e., their attractors are periodic, so number sequences generated by those processes repeat. However, some chaotic processes have "strange attractors," with trajectories in state space that are fractals and never repeat.

So my questions are:

1. Suppose a series of numbers is generated by a deterministic chaotic process having a strange attractor. Can that series of numbers, which is deterministic but never never repeats, be differentiated from a series of numbers that is generated by a "random" process?

2. If a chaotic process cannot be differentiated from a "random" process, do random processes even exist, or are they all fundamentally deterministic, albeit unpredictable? In other words, is radioactive decay actually "programmed into" an atomic nucleus, even though the time of decay is apparently random and cannot be predicted analytically?

3. Is it possible to design a computer algorithm that simulates a chaotic process having a strange attractor (never repeats)? Computers are used to generate fractals, so this might be possible.

4. If it is possible to design such a computer algorithm, could the overall process be defined by a quantum wave function?

 

[mfb]

1. Suppose a series of numbers is generated by a deterministic chaotic process having a strange attractor. Can that series of numbers, which is deterministic but never never repeats, be differentiated from a series of numbers that is generated by a "random" process?

If you know, or guess, the procedure that created the deterministic numbers: sure. You can just check if a reproduction of that procedure gives the same sequence.

2. If a chaotic process cannot be differentiated from a "random" process, do random processes even exist, or are they all fundamentally deterministic, albeit unpredictable? In other words, is radioactive decay actually "programmed into" an atomic nucleus, even though the time of decay is apparently random and cannot be predicted analytically?

It can be shown that quantum mechanics has to have something related to true randomness. The laws of physics can be deterministic (we don't know), but even if they are, some processes have to look like true randomness to us. See Wikipedia: Hidden variable theory for an overview.

3. Is it possible to design a computer algorithm that simulates a chaotic process having a strange attractor (never repeats)? Computers are used to generate fractals, so this might be possible.

Everything deterministic you can implement in digital hardware with a finite storage has to repeat as the number of possible states of this hardware is limited.

4. If it is possible to design such a computer algorithm, could the overall process be defined by a quantum wave function?

"Defined by"? You can see the whole world as a wave-function. That's fine, and independent of any computers inside.

 

[Juan Largo]

Thank you for your insight.

If you know, or guess, the procedure that created the deterministic numbers: sure. You can just check if a reproduction of that procedure gives the same sequence.

Yes, but if all you have is the output sequence, is there a test for "randomness" versus "psueudo-randomness" (as long as the sequence doesn't repeat, of course)?

It can be shown that quantum mechanics has to have something related to true randomness.

But what is "true randomness" as opposed to "pseudo-randomness" if there's no way to tell the difference?

Everything deterministic you can implement in digital hardware with a finite storage has to repeat as the number of possible states of this hardware is limited.

That makes sense, and that's what I initially thought also. However, a Mandelbrot set generated by a computer -- even with limited hardware capabilities -- seems to go to deeper and deeper levels without repeating.

"Defined by"? You can see the whole world as a wave-function. That's fine, and independent of any computers inside.

In Schrodinger's Cat thought experiment, Schrodinger used a radioactive source to trigger the release of cyanide poison. He used that method because it was random and could be thought of as two superimposed wave functions. The trigger had a 50/50 chance of going off within 10 minutes; therefore, the cat was 50% alive and 50% dead during the whole 10 minutes (depending on your interpretation). But if Schrodinger had used a 5-minute timer to trigger the cyanide, the whole question would be moot because there would be no randomness. The cat would be 100% alive before 5 minutes and 100% dead after 5 minutes.

Thus, the existences of superimposed wave functions seem to depend on the randomness of the overall process: the radioactive decay trigger + geiger counter + cyanide + cat. Take away the randomness, and superposition doesn't make any sense. In other words, in a deterministic process, the wave-function "collapses" at every moment in time, not only when the box is opened after 10 minutes.

If things we assume to be random are actually chaotic (deterministic, yet entirely uncertain and unpredictable) instead, then would the wave-function still exist?

 

[nsaspook]

Yes, but if all you have is the output sequence, is there a test for "randomness" versus "psueudo-randomness" (as long as the sequence doesn't repeat, of course)?

But what is "true randomness" as opposed to "pseudo-randomness" if there's no way to tell the difference?

"true randomness" seems to be detectable.
http://arxiv.org/abs/1004.1521

In contrast with software-generated randomness (called pseudo-randomness), quantum randomness is provable incomputable, i.e.\ it is not exactly reproducible by any algorithm. We provide experimental evidence of incomputability --- an asymptotic property --- of quantum randomness by performing finite tests of randomness inspired by algorithmic information theory.

 

[mfb]

Yes, but if all you have is the output sequence, is there a test for "randomness" versus "psueudo-randomness" (as long as the sequence doesn't repeat, of course)?

Where is the difference?
Assuming the pseudo-RNG is perfect (satisfies every possible test on randomness), the difference is just the way the numbers are generated. If you don't know, you can still try to guess it.

That makes sense, and that's what I initially thought also. However, a Mandelbrot set generated by a computer -- even with limited hardware capabilities -- seems to go to deeper and deeper levels without repeating.

A desktop computer has a storage of the order of 1 TB = 2^43 bits, that allows 2^2^43 ≈ 10^2600000000000 different states. This is far beyond the number of total computation steps ever done by computers.

Thus, the existences of superimposed wave functions seem to depend on the randomness of the overall process: the radioactive decay trigger + geiger counter + cyanide + cat. Take away the randomness, and superposition doesn't make any sense.

No. You can still write the wavefunction as superposition, you just get an amplitude of 0 for one component. Why? Because there is no way this state can be reached.

Note that the cat is too active and heavy to make this experiment. Better use an atom.

In other words, in a deterministic process, the wave-function "collapses" at every moment in time, not only when the box is opened after 10 minutes.

No.

If things we assume to be random are actually chaotic (deterministic, yet entirely uncertain and unpredictable) instead, then would the wave-function still exist?

You can (but do not have to) always see the whole universe as a single wave-function.

 

[Juan Largo]

"true randomness" seems to be detectable.
http://arxiv.org/abs/1004.1521

In contrast with software-generated randomness (called pseudo-randomness), quantum randomness is provable incomputable, i.e.\ it is not exactly reproducible by any algorithm. We provide experimental evidence of incomputability --- an asymptotic property --- of quantum randomness by performing finite tests of randomness inspired by algorithmic information theory.

It is very interesting that the authors of the above article have succeeded in determining whether a string of numbers is computable. I'm willing to concede that a truly random sequence of numbers cannot be generated by any numerical algorithm. However, I don't agree that a string of numbers that is incomputable is necessarily random.

Fluid flow is defined by the Navier–Stokes equations, which are non-linear differential equations. When fluid flow becomes turbulent, the trajectory of the system in state space never intersects itself, which is why it is called a strange attractor. Thus, the overall state of the system never repeats and so it could never be produced by any numerical algorithm. Nevertheless, the Navier-Stokes equations still apply in turbulent flow, so the process is still fundamentally deterministic because the fluid's motion is still determined by the Navier-Stokes equations. The Navier-Stokes equations can be replicated by an analog computer. So in theory, we could build a machine that generates a series of states (or numbers) that are incomputable, yet deterministic.

 

[nsaspook]

So in theory, we could build a machine that generates a series of states (or numbers) that are incomputable, yet deterministic.

Sure, that's the basis of many modern digital crypto systems. A truly random key (changed daily or some other period) is used to generate a incomputable (in practical terms), yet deterministic string of pseudo-random code-text that is mixed (various hashing or substitution functions with sometimes embedded synchronization timing) with clear-text to generate the encrypted cipher-text and the process is reversed on the far end to recover the clear-text.

 

[Khashishi]

Computers can simulate chaotic systems up to some limit of precision. Normal computer math is done using 64 bit "double precision" floating point numbers. You can draw fractals with this precision, but if you zoom a few times, then the calculation will fail. Powerful fractal software uses arbitrary precision numerical libraries for deep zooming, which contains computer code that automatically allocates more memory to numbers as necessary to do the calculations. This let's you zoom much farther, but eventually, you could still run out of memory at some point (if you don't run out of patience first, as these calculations are very lengthy).

An ideal digital computer can't truly create arbitrarily long non-repeating sequences because a computer is a state machine, and the number of states is ultimately limited by the number of possible patterns that can be stored in memory, which is large but finite. Practically speaking, we never need sequences that long.

 

[Juan Largo]

An ideal digital computer can't truly create arbitrarily long non-repeating sequences because a computer is a state machine, and the number of states is ultimately limited by the number of possible patterns that can be stored in memory, which is large but finite. Practically speaking, we never need sequences that long.

Excellent point. The authors of the paper linked in a previous post by nsaspook make two claims: a) it is possible to examine a numerical sequence and determine whether it is computable, and b) if the sequence is computable, it isn't random. The first claim is possible in theory only because the computer is a state machine with limited patterns in memory, as you pointed out above.

Until the computer does run out of memory, however, I maintain it is possible to design a computer algorithm that generates a finite string of zeros and ones that doesn't repeat and is indistinguishable from a finite string of zeros and ones generated by a truly random process, such as radioactive decay. In fact, there is a trivial case that proves this:

Generate a string of zeros and ones by some random process, such as radioactive decay, and store that string in a computer's memory. The "algorithm" is as follows: read the string of numbers from memory and add zero to each number. I can repeat that "algorithm" as many times as I want and get exactly the same result. Therefore, the string is deterministic and computable, even though the computation is rather trivial. Since the computed string is the same as the randomly-generated string, there is no valid test we can perform on that string that can show that those numbers are computable. If the test actually did show that, it would also show that the original randomly-generated string is computable, which is a contradiction. The only way that test can be valid is if the string is much larger than the computer's memory.

Some people speculate that everything we observe in the universe consists of data that are generated by some kind of state machine. The memory of the state machine can be made arbitrarily large by expanding the universe. Therefore every random quantum number could actually be generated by an algorithm.

 

[nsaspook]

Generate a string of zeros and ones by some random process, such as radioactive decay, and store that string in a computer's memory. The "algorithm" is as follows: read the string of numbers from memory and add zero to each number. I can repeat that "algorithm" as many times as I want and get exactly the same result. Therefore, the string is deterministic and computable, even though the computation is rather trivial. Since the computed string is the same as the randomly-generated string, there is no valid test we can perform on that string that can show that those numbers are computable. If the test actually did show that, it would also show that the original randomly-generated string is computable, which is a contradiction. The only way that test can be valid is if the string is much larger than the computer's memory.

Your "algorithm" is not a PRNG or any type of random number generator, it's just a mixing function of observed random data similar to a One Time Pad.

 

[Khashishi]

JL, that makes sense but it is unreasonable. The point of physics or science is to figure out simple underlying laws that explain or predict reality. If the predictions are the same, a simple model is better than a complex one, which is why Ptolemy's model of geocentrism is considered wrong. If simple (enough for humans to understand) laws for the universe don't exist, we might as well give up on physics. In mainstream quantum mechanics, randomness does exist, because this is the simplest way to explain things that is consistent with our experiments. We could certainly go with some nonlocal hidden variable theory, but until we find some good reason for it, we should treat it like the theory of geocentrism.

It's implied that a pseudorandom number generator should generate a string of random numbers longer than the program itself, otherwise there's no point.