Usefulness Of Non Determinism

From InteractiveComputationIsMorePowerfulThanNonInteractive:

"Nondeterminism" is in practice used to refer to any unpredictability in the outcome of a process. IOW, we as observers cannot predict the outcome given our current knowledge. There are several factors that can lead to this:

Ignorance of initial conditions.
Ignorance of inputs.
Model error. Our best known model of the process may be inaccurate.
Physical nondeterminism. The usual interpretations of quantum theory hold that physical events would be inherently unpredictable even given perfect knowledge of initial conditions, inputs, and model.

In attempting to predict something like the weather, for instance, all of these factors apply. They also apply to computer systems: for instance, the spinning of a disk drive (and therefore its observable response time) is subject to air turbulence, which again involves all of these factors.

In sequential computation, the nondeterminism that is always present in the implementation of the computer system can be easily hidden. In most forms of concurrent computation (excluding DeclarativeConcurrency), it cannot be hidden. It really is not usually the case that we know some details of the computation -- such as the message interarrival times in the ActorsModel -- and even if we did know them, we would not want to have to rely on that knowledge.

A model of computation is a specification for a computer system. There is another kind of unpredictability that applies only to specifications: the spec may intentionally allow multiple outcomes from a given initial or intermediate state (this is sometimes called "don't care" or specification nondeterminism).

There are two main reasons for introducing specification nondeterminism:

to model hardware that is actually unpredictable, or to allow such hardware to be used.
to allow the model to be useful despite partial knowledge of the system. If two processes do not have any necessary dependency on each other, we do not want the model to introduce an artificial dependency. For that reason concurrency models do not specify details of scheduling, since it would introduce many artificial dependencies and make the model all but useless.

So in a sense, "ignorance of determinism" is a form of nondeterminism.

Some people dispute the above explanation. For instance:

The first two factors (ignorance) don't produce non-determinism. -- EricHodges

Do you consider the outcome of rolling a well-shaken die to be nondeterministic? That is unpredictable due to precisely the same factors.

No, I don't. Complexity doesn't negate determinism. No matter how well ActorsModel shakes its dice, the dice behave deterministically.

Well, I submit that you have an unconventional view of nondeterminism.

Refusing to predict an event doesn't make the event unpredictable. Model error is an error and can be corrected. If the ActorsModel mandated amplification of quantum effects so that they decided which message won the race, then that would produce non-deterministic output. But it doesn't.

[...] Run any "program" (the same tape) twice (or in parallel on two TMs) you'll always get the same output. The capability of running the same program and getting distinct output is non-determinism. That's something TM do not have. Therefore you cannot ever "model" a non-deterministic machine inside a TM, because you'd have to be able to run the same program twice and be able to obtain distinct results. The ActorsModel is non-deterministic by definition, it has nothing to do with QM or whatever, it's a mathematical abstraction -- not a description of physical phenomena.

I'm not saying you can model a non-deterministic machine inside a TM. I'm saying using the ActorsModel doesn't make a machine non-deterministic. It isn't non-deterministic by definition. ...

Correct, using the ActorsModel does not make a machine nondeterministic. It models the nondeterminism that is present in the machine for other reasons.
- And to add to this point, ActorsModel is not physical. It is a mathematical abstraction. It is non-deterministic by definition. You won't get the same output because the mathematical machines are specified not to make deterministic choices. End of discussion. Whether you like it or not that's what it is. Arguing against that is arguing against a definition. The fact that you cannot imagine any physical machines to implement that has no bearing on the main point [of InteractiveComputationIsMorePowerfulThanNonInteractive].
- [A deterministic implementation of the ActorsModel is acceptable, but is not necessary.]
Although the fact that such machines do exist has a bearing on the utility of the ActorsModel (and other nondeterministic ModelsOfComputation).
- Correct, that's why we need to have a separate discussion on the UsefulnessOfNonDeterminism. [We also need to] acknowledge that discussing the practical utility of a mathematical theory is separate from discussing the theory itself. There's not only one imaginable category of physical implementations for a theory, and even if we accept for the sake of discussion that the universe is strictly deterministic -- a philosophical claim in essence that is beyond our concern, but dear to Eric, nevertheless -- non-deterministic theories can still be practically useful. It's the same story with the axiom of the parallels or the axiomatic construction of reals. It may turn out that we can't correlate an axiomatic line with any "physical" line, and the same can be said about the axiomatic construction of real and complex numbers, it may turn out that we live in an entirely discrete universe, I really do not care, the practical utility of mathematical theory is not decided by the question whether the theory "admits" a "physical" model or not.

Well, the ActorsModel is perhaps a special case, because it was explicitly designed to reflect physical implementability and to be motivated by physical constraints on computation. For instance, quoting from the abstract of "Actors and Continuous Functionals" <http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-194.pdf>:

This paper presents precise versions of some "laws" that must be satisfied by computations involving communicating parallel processes. The laws take the form of stating plausible restrictions on the histories of computations that are physically realizable. The laws are very general in that they are obeyed by parallel processes executing on a time varying number of distributed physical processors. For example, some of the processors might be in orbiting satellites. The laws are justified by appeal to physical intuition and are to be regarded as falsifiable assertions about the kinds of computations that occur in nature rather than as proved theorems in mathematics. The laws are intended to be used to analyze the mechanisms by which multiple processes can communicate to work effectively together.

Also, in Section VII:

We would like to formalize the physical intuition that computation is local and there can be no "action at a distance". The laws of locality presented in this section are intended to capture these intuitions.

OTOH, some aspects of the actor model may specify stronger constraints on computation than physical reality. For example, it is a theorem proven in "Foundations of Actor Semantics" <http://www.cypherpunks.to/erights/history/actors/AITR-633.pdf> that there exists a global ordering consistent with the partial event ordering specified by the actor laws. It is not obvious, and probably not true that the corresponding property holds physically in either GeneralRelativity or QuantumMechanics.

Can't speak for quantum mechanics, but it holds for GeneralRelativity. It helps to invert your perspective and think of time in terms of signals/messages and observations thereof (rather than the other way around). Messages B delivered in reaction to message A being received will be, in the global partial order (and, therefore, in global time), after message A. Any observed clock is just one source of messages for this overall partial order. There will always be a global ordering of messages consistent with this constraint... but this global ordering will very rarely be unique (i.e. for any N messages you'll have exactly a set of partial ordering constraints and between 1 and N! global orderings consistent with these constraints).

OTOH^2, it may be that the ActorsModel is more useful as a result of not quite reflecting the physical realities that it was intended to reflect. A model that tried to allow all of the phenomena permitted by quantum mechanics could be quite confusing!

An example of an entire branch of computation that depends critically on nondeterminism is cryptography. Key generation and many other cryptographic operations require an unpredictable source of randomness, which cannot be replaced by any pseudorandom approximation.

Is the test for "usefulness" also non-deterministic? :-)

See NonDeterministic

CategoryMath CategoryConcurrency CategoryPhysics