3 ms·

Ask HN: Does Unpredictability Exist?

1 points by cj 16y ago

Is it possible to have a program whose output is completely unpredictable, even if the complete list of initial conditions is known (all of the program's input, code, algorithms, random number list, etc)?

cj 16y ago
I ask this question for how it relates to http://en.wikipedia.org/wiki/Digital_physics http://en.wikipedia.org/wiki/Digital_physics ..and how it would be possible for a universe, if wholly deterministic, to be practically and theoretically unpredictable.
memetichazard 16y ago
First define unpredictable. From your comment below, it seems to me you're saying that deterministic != predictable. Also, the halting theorem may apply.
limmeau 16y ago
If by "program", you mean something computable in the usual Turing-equivalent sense, and without access to a physical random number generator, then the output is always trivially predictable by recreating the initial conditions somewhere and running the program. However, the prediction may take as long to compute as the real output. There is no general faster way to predict the result (see halting problem).
jimrandomh 16y ago
Strictly speaking, no. However, that "no" comes with caveats. First, it's easy to accidentally have some inputs you haven't accounted for, which can be turned into pseudorandom number generators. For example, if the program is multithreaded, then the exact relative timings of instructions on each thread matter. And second, the thing you care about might not actually be the output, but only a subset of the output. For example, under the many-worlds interpretation of quantum mechanics, the laws of physics are implemented by a computer program that computes every possible final state, but only one of those final states is observed; and the selection of which final state gets observed depends on which observer you are, which is "random" but in a philosophically tricky way, since every result has a corresponding observer.

3 ms·

Ask HN: Does Unpredictability Exist?

1 points by cj 16y ago

cj 16y ago
I ask this question for how it relates to http://en.wikipedia.org/wiki/Digital_physics http://en.wikipedia.org/wiki/Digital_physics ..and how it would be possible for a universe, if wholly deterministic, to be practically and theoretically unpredictable.
memetichazard 16y ago
First define unpredictable. From your comment below, it seems to me you're saying that deterministic != predictable. Also, the halting theorem may apply.
limmeau 16y ago
If by "program", you mean something computable in the usual Turing-equivalent sense, and without access to a physical random number generator, then the output is always trivially predictable by recreating the initial conditions somewhere and running the program. However, the prediction may take as long to compute as the real output. There is no general faster way to predict the result (see halting problem).
jimrandomh 16y ago
Strictly speaking, no. However, that "no" comes with caveats. First, it's easy to accidentally have some inputs you haven't accounted for, which can be turned into pseudorandom number generators. For example, if the program is multithreaded, then the exact relative timings of instructions on each thread matter. And second, the thing you care about might not actually be the output, but only a subset of the output. For example, under the many-worlds interpretation of quantum mechanics, the laws of physics are implemented by a computer program that computes every possible final state, but only one of those final states is observed; and the selection of which final state gets observed depends on which observer you are, which is "random" but in a philosophically tricky way, since every result has a corresponding observer.