3 ms·

On top of that, you can easily emulate non-determinism in deterministic systems and vice versa. So why would it even matter?

by Retra 7y ago

winter_blue 7y ago
It’s impossible to have actual non-determinism in a deterministic system. Non-determinism is emulated in software using random number generators. If you know the seed (the ‘x’) and the definition of the random function (the ‘f’), you can predict all outputs, analogous to my f(..(x)..) universe above. There’s no programmatic random number generator that is truly random. (I mean random in the sense that it’s entirely unpredictable; not in the sense that the distribution of the random number generator covers all possibilities uniformly over many calls.) Hardware random number generators are truly random (like the RDRAND instruction in x86 CPUs which is seeded by an on-chip entropy source). But if you’re relying on physical entropy, it’s not a deterministic system anymore. You simply can’t emulate non-determinism in a deterministic system.
- Retra 7y ago
  Why do you say 'actual'? I can emulate a chemical reaction in a computer, but that does not mean I have produced an 'actual' chemical reaction.
dtech 7y ago
How can you create non-determinism in a deterministic system without a source of randomness/non-determinism?
- Retra 7y ago
  You compute every possibility in parallel, and defer the selection of the 'true' result to some time-at-infinity. Once you've done this, realize that there's no difference within this system between selecting the 'true' result at random or using an algorithm, because the system would consider this result selection to be equally arbitrary in either case. (I.e., there's no way to prove that you've selected a specific result non-deterministically.) A deterministic system emulates a non-deterministic one using (computational or data-) parallelism, and a non-deterministic system emulates a deterministic one using (temporal or spacial) aggregation. We typically use random numbers to model non-determinism because it is computationally infeasable to track every possibility, but that is not the only way to do it, and nature doesn't appear to have this problem.
  - winter_blue 7y ago
    > there's no difference within this system between selecting the 'true' result at random or using an algorithm, because the system would consider this result selection to be equally arbitrary This makes zero sense. Choices matter. Selecting one path could potentially result in the suffering of billions of people, and another path could result in the joy of the same billions. > We typically use random numbers to model non-determinism because it is computationally infeasable to track every possibility First, tracking every possibility has absolutely nothing to do with random selection. I don't know how you're mixing these two. We use pseudorandom number generators precisely because it is impossible to have true randomness within a deterministic system. > You compute every possibility in parallel I think you're alluding to some sort of multiverse theory -- and implying that since every possibility exists in parallel, choices are meaningless and nothing matters. Except, we don't live in a multiverse -- a gobbledygook theory if ever there was one. Choices matter.
    - Retra 7y ago
      >This makes zero sense. Choices matter. Not in models that don't contain them. >We use pseudorandom number generators precisely because it is impossible to have true randomness within a deterministic system. "Nondeterminism" and "true randomness" can be modeled in deterministic systems. Your ability to deterministically construct those notions in your own brain is a weak proof of that. If I say "elephant", and you imagine an elephant, then you've modeled an elephant. You have not created an elephant, I'm not claiming you will, and I'm not claiming that you will get true randomness from a deterministic machine. I'm saying you can model it, and thus reason about it. >I think you're alluding to some sort of multiverse theory. I am not. I am alluding to parallelism being a computational feature which usefully serves as a model of nondeterministic processes. I'm not talking about choices, meaningless or otherwise, I'm talking about modeling the concept that is invoked by your use of the word "nondeterminism." (Though you can also model nondeterministic choices as parallel thunks.) My point is that for every nondeterministic function, there exists a deterministic function which will produce exactly the same outputs. Thus one cannot argue that nondeterminism offers any additional capabilities (beyond computational efficiency.) This is effectively the same as saying that every parallel computation can be executed sequentially, or that every strict computation can be computed lazily.

On top of that, you can easily emulate non-determinism in deterministic systems and vice versa. So why would it even matter?

by Retra 7y ago

On top of that, you can easily emulate non-determinism in deterministic systems and vice versa. So why would it even matter?

winter_blue 7y ago

It’s impossible to have actual non-determinism in a deterministic system. Non-determinism is emulated in software using random number generators. If you know the seed (the ‘x’) and the definition of the random function (the ‘f’), you can predict all outputs, analogous to my f(..(x)..) universe above. There’s no programmatic random number generator that is truly random. (I mean random in the sense that it’s entirely unpredictable; not in the sense that the distribution of the random number generator covers all possibilities uniformly over many calls.) Hardware random number generators are truly random (like the RDRAND instruction in x86 CPUs which is seeded by an on-chip entropy source). But if you’re relying on physical entropy, it’s not a deterministic system anymore. You simply can’t emulate non-determinism in a deterministic system.

Retra 7y ago
Why do you say 'actual'? I can emulate a chemical reaction in a computer, but that does not mean I have produced an 'actual' chemical reaction.

dtech 7y ago

How can you create non-determinism in a deterministic system without a source of randomness/non-determinism?

Retra 7y ago
You compute every possibility in parallel, and defer the selection of the 'true' result to some time-at-infinity. Once you've done this, realize that there's no difference within this system between selecting the 'true' result at random or using an algorithm, because the system would consider this result selection to be equally arbitrary in either case. (I.e., there's no way to prove that you've selected a specific result non-deterministically.) A deterministic system emulates a non-deterministic one using (computational or data-) parallelism, and a non-deterministic system emulates a deterministic one using (temporal or spacial) aggregation. We typically use random numbers to model non-determinism because it is computationally infeasable to track every possibility, but that is not the only way to do it, and nature doesn't appear to have this problem.
- winter_blue 7y ago
  > there's no difference within this system between selecting the 'true' result at random or using an algorithm, because the system would consider this result selection to be equally arbitrary This makes zero sense. Choices matter. Selecting one path could potentially result in the suffering of billions of people, and another path could result in the joy of the same billions. > We typically use random numbers to model non-determinism because it is computationally infeasable to track every possibility First, tracking every possibility has absolutely nothing to do with random selection. I don't know how you're mixing these two. We use pseudorandom number generators precisely because it is impossible to have true randomness within a deterministic system. > You compute every possibility in parallel I think you're alluding to some sort of multiverse theory -- and implying that since every possibility exists in parallel, choices are meaningless and nothing matters. Except, we don't live in a multiverse -- a gobbledygook theory if ever there was one. Choices matter.
  - Retra 7y ago
    >This makes zero sense. Choices matter. Not in models that don't contain them. >We use pseudorandom number generators precisely because it is impossible to have true randomness within a deterministic system. "Nondeterminism" and "true randomness" can be modeled in deterministic systems. Your ability to deterministically construct those notions in your own brain is a weak proof of that. If I say "elephant", and you imagine an elephant, then you've modeled an elephant. You have not created an elephant, I'm not claiming you will, and I'm not claiming that you will get true randomness from a deterministic machine. I'm saying you can model it, and thus reason about it. >I think you're alluding to some sort of multiverse theory. I am not. I am alluding to parallelism being a computational feature which usefully serves as a model of nondeterministic processes. I'm not talking about choices, meaningless or otherwise, I'm talking about modeling the concept that is invoked by your use of the word "nondeterminism." (Though you can also model nondeterministic choices as parallel thunks.) My point is that for every nondeterministic function, there exists a deterministic function which will produce exactly the same outputs. Thus one cannot argue that nondeterminism offers any additional capabilities (beyond computational efficiency.) This is effectively the same as saying that every parallel computation can be executed sequentially, or that every strict computation can be computed lazily.