Comment by saghm
2 days ago
I expected this to be about different meanings of the word "nondeterminism" rather than different causes of a single meaning. Back in college, I remember someone once pointing out to me that the word was used for fairly different concepts in different classes; in our theory classes, "nondeterministic" was used for stuff like finite automata and Turing machine models of computation (like the "N" in "NP" compared to just "P"), whereas in some other classes it might get used the way it's used in this article (e.g. for an AI algorithm that wouldn't always produce the same results). Maybe someone more educated than me might be able to connect why the same word is used for both of those, but as far as I'm able to tell, they seem entirely unrelated.
A deterministic program follows a single path of execution, always producing the same result.
A nondeterministic_1 program follows a single path of execution, but at certain points, it randomly chooses how to proceed, therefore producing different results for different runs.
A nondeterministic_2 program follows multiple paths of execution, at certain points _splitting_ its execution to follow two (or more) paths instead of one, producing a set of results at the end.
A nondeterministic_1 program follows a randomly sampled path from a nondeterministic_2 program, and produces a randomly sampled result from a nondeterministic_2 program.
> A deterministic program follows a single path of execution, always producing the same result.
Looking at a whole program as D/ND isn't too useful for me since it's too big to analyse and constantly being patched by multiple contributors.
Does this definition of deterministic work for smaller things, like a method?
You can transform a function `f: (Rng, args...) -> A` into a function `f: (args...) -> Set<A>` with very little machinery. Some programming languages allow writing functions that are _generic_ over whether they're random or nondeterministic, such as in this Haskell package: https://hackage.haskell.org/package/nondeterminism-1.5/docs/...
They are related and the reason is the last point of the OP article: Abstraction. Things can be "physically" deterministic, but can be abstracted as non-deterministic. This seems strange at first but it actually makes a lot of sense, as long as you're not modelling physics itself, it's irrelevant that there is a theory in which your non-model is deterministic. Machine learning algorithms like ChatGPT can be good examples, given the exact same input+random seed, of course, they'll return the same exact output, but the situation is so computationally complex that modeling that system as deterministic is less useful than modelling it as if it's non-deterministic. This is the same way your computer RAM is not "infinite"--it's like trillions of bits-- but in CS we model it as if it's infinite because the practical difference is not the focus of the discussion. If the discussion really was "can we fit a pigeon in every bit of my computer" or "can we manufacture every bit of this RAM in finite amount of time" then yes, it would be relevant to argue that RAM isn't actually infinite. But given that we're interested in models of computation that get exponentially larger and larger as memory grows, even 10 bits can be an intractibly large space (cf. Busy Beaver numbers) so you might as well solve the problem as if it's infinite.
I couldn't tell you the historical connections, but they "feel" related to me. This comment got me speculating about how to explain this connection; disclaimer I'm writing completely this off the cuff.
First off, NFAs and Nondet Turing Machines (NTM) would be "deterministic" with the OP definition I gave, since they always give the same decision for the same input. Their nondeterminism is a capability they have, an aspect of their process that helps reach a decision. If we need to distinguish "deterministic result" and "deterministic process", I've seen the term Observationally Deterministic used to exclusively mean the former.
A critical theorem in automata theory is that NFAs and NTMs are no more powerful than DFAs or TMs: the former cannot recognize any languages the latter cannot. This is why nondeterministic algorithms (ie, algorithms with a deterministic capability) cannot "solve more problems" than deterministic algorithms, just (probably) solve them faster (NP vs P).
(Interestingly, nondeterministic pushdown automata ARE more powerful than regular PDAs. Only NPDAs can recognize all context-free languages.)
So what does it mean for "nondeterminism" to be a capability of the process? I see the "automata/computation" and the "formal methods" as being the same idea, except with opposite outcomes. When deciding to see if a problem is in NP, we allow the algorithm to make nondeterministic choices, and accept the construction if any choice leads to valid outcome. When deciding to see if a system is satisfies required properties, we allow the model to make nondeterministic choices, and reject if any lead to an invalid outcome.
(Even more handwavy part: I've heard the terms "angelic" and "demonic" choice to distinguish the two. I think from the perspective of complexity, FM's demonic nondeterminism kinda looks like angelic choice in the co-complexity class. From the perspective of FM, complexity's angelic nondeterminism kinda looks like checking a reachability property, as opposed to a safety or liveness property.)
In either case, both are essentially abstractions over concrete implementation details. Just as I cannot physically implement "nondeterministically enter state A, B, or C", I cannot implement "nondeterministically match the regex `A|B|C`". I have to instead find a deterministic implementation, like "try to match A, and if that fails, backtrack and match B, etc."
https://cstheory.stackexchange.com/questions/632/what-is-the...
Determinism is relative. "Non-deterministic" means that an observer, to the best of their ability, cannot predict the result even with full knowledge of all inputs.
This can be used as an abstraction for a theoretically deterministic system that is too complex to handle.
But even if you take "ability" and "knowledge" (of all inputs and the inner workings of the system) serious, there is always the possibility that there are factors you simply don't know. Maybe your model is incomplete. Maybe there are as-yet-unknown physics that make even radioactive decay predictable. So really, it's always an abstraction.