I don’t completely understand what you mean (in particular, I would really like you to be more specific about what you mean by “noisy” and “indistinguishable”), but this looks like it shouldn’t be true on cardinality grounds. There should be uncountably many possible distinguishable noisy behaviors of a dynamical system.
By “indistinguishable” I mean some sort of bound on the advantage) of any algorithm trying to tell the two apart. I think if I try to answer on “noisy” without knowing more about what you need specified I won’t answer your question—I’m thinking of some sort of continuous equivalent to the role that noise plays in a Kalman filter.
The cardinality thing is a big problem—if the “system” is a single uncomputable real number that doesn’t change, from which we take multiple noisy readings, then for any program that tries to emulate it, there is a distinguishing program whose advantage approaches 1 as the number of readings go up.
It still feels like there must be something like this that we can prove!
Uncountability doesn’t seem like a big deal to me. Just give the Turing machine an auxiliary tape containing the real parameter.
A related question is whether a Turing machine can fully simulate the dynamical system, that is, whether it can compute the state at any future time to any precision using only finitely many bits from the starting parameters.
I think the answer to that differential equations with initial conditions a computable real number can evolve to an uncomputable real number. But if the initial random number is not arbitrary, but guaranteed random, maybe it is computable. (That is, maybe the inputs with computable futures have full measure.)
Uncountability doesn’t seem like a big deal to me. Just give the Turing machine an auxiliary tape containing the real parameter.
I can’t work out whether this works or not. Here’s a really simple example system: each output is 0 or 1, drawn with a fixed probability. If the probability is an uncomputable number, then no algorithm with a finite initial state can generate output with exactly that probability; there has to be a rational number inbetween the real probability and the simulated one, which means there’s an attacker that can distinguish the two given enough outputs.
If instead the simulator can read the real probability on an infinite tape… obviously it can’t read the whole tape before producing an output. So it has to read, then output, then read, then output. It seems intuitive that with this strategy, it can place an absolute limit on the advantage that any attacker can achieve, but I don’t have a proof of that yet.
A related question is whether a Turing machine can fully simulate the dynamical system, that is, whether it can compute the state at any future time to any precision using only finitely many bits from the starting parameters.
Obviously if this can be done then what I ask can be done. I had thought this impossible, which is why I wanted to substitute an easier question about distinguishability.
I think the answer to that differential equations with initial conditions a computable real number can evolve to an uncomputable real number. But if the initial random number is not arbitrary, but guaranteed random, maybe it is computable. (That is, maybe the inputs with computable futures have full measure.)
Well that’s clearly true, if the dynamical system is that when t = 0 then y = 0 and dy/dt = 1, then y will pass through lots of uncomputable values at uncomputable times. Some kind of computable uncertainty about the initial state may address the cardinality issue, but I’m not sure how to formalise that.
If instead the simulator can read the real probability on an infinite tape… obviously it can’t read the whole tape before producing an output. So it has to read, then output, then read, then output. It seems intuitive that with this strategy, it can place an absolute limit on the advantage that any attacker can achieve, but I don’t have a proof of that yet.
In this model, a simulator can exactly match the desired probability in O(1) expected time per sample. (The distribution of possible running times extends to arbitrarily large values, but the L1-norm of the distribution is finite. If this were a decision problem rather than a sampling problem, I’d call it ZPP.)
Algorithm:
Start with an empty string S.
Flip a coin and append it to S.
If S is exactly equal to the corresponding-length prefix of your probability tape P, then goto 2.
Well that’s clearly true, if the dynamical system is that when t = 0 then y = 0 and dy/dt = 1, then y will pass through lots of uncomputable values at uncomputable times.
That’s silly. You should only ask what the state of the system is at a specified time (yet another auxiliary tape).
I don’t completely understand what you mean (in particular, I would really like you to be more specific about what you mean by “noisy” and “indistinguishable”), but this looks like it shouldn’t be true on cardinality grounds. There should be uncountably many possible distinguishable noisy behaviors of a dynamical system.
By “indistinguishable” I mean some sort of bound on the advantage) of any algorithm trying to tell the two apart. I think if I try to answer on “noisy” without knowing more about what you need specified I won’t answer your question—I’m thinking of some sort of continuous equivalent to the role that noise plays in a Kalman filter.
The cardinality thing is a big problem—if the “system” is a single uncomputable real number that doesn’t change, from which we take multiple noisy readings, then for any program that tries to emulate it, there is a distinguishing program whose advantage approaches 1 as the number of readings go up.
It still feels like there must be something like this that we can prove!
Uncountability doesn’t seem like a big deal to me. Just give the Turing machine an auxiliary tape containing the real parameter.
A related question is whether a Turing machine can fully simulate the dynamical system, that is, whether it can compute the state at any future time to any precision using only finitely many bits from the starting parameters.
I think the answer to that differential equations with initial conditions a computable real number can evolve to an uncomputable real number. But if the initial random number is not arbitrary, but guaranteed random, maybe it is computable. (That is, maybe the inputs with computable futures have full measure.)
I can’t work out whether this works or not. Here’s a really simple example system: each output is 0 or 1, drawn with a fixed probability. If the probability is an uncomputable number, then no algorithm with a finite initial state can generate output with exactly that probability; there has to be a rational number inbetween the real probability and the simulated one, which means there’s an attacker that can distinguish the two given enough outputs.
If instead the simulator can read the real probability on an infinite tape… obviously it can’t read the whole tape before producing an output. So it has to read, then output, then read, then output. It seems intuitive that with this strategy, it can place an absolute limit on the advantage that any attacker can achieve, but I don’t have a proof of that yet.
Obviously if this can be done then what I ask can be done. I had thought this impossible, which is why I wanted to substitute an easier question about distinguishability.
Well that’s clearly true, if the dynamical system is that when t = 0 then y = 0 and dy/dt = 1, then y will pass through lots of uncomputable values at uncomputable times. Some kind of computable uncertainty about the initial state may address the cardinality issue, but I’m not sure how to formalise that.
In this model, a simulator can exactly match the desired probability in O(1) expected time per sample. (The distribution of possible running times extends to arbitrarily large values, but the L1-norm of the distribution is finite. If this were a decision problem rather than a sampling problem, I’d call it ZPP.)
Algorithm:
Start with an empty string S.
Flip a coin and append it to S.
If S is exactly equal to the corresponding-length prefix of your probability tape P, then goto 2.
Compare (S < P)
D’oh! Of course—thanks!
That’s silly. You should only ask what the state of the system is at a specified time (yet another auxiliary tape).