Five Kinds of Nondeterminism

Reminds me a lot of thermodynamics. Microstates and transition probabilities are a more “fundamental” description, but when you hit the metal, temperature and pressure are more useful in practice to human engineers

Interesting point. It's almost a form of "design by verifiability" – prioritizing architectures that lend themselves to easier reasoning, even if other architectures might offer marginal performance gains.

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.

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.

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.

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."

Maybe I'm missing something here, but the last type matches 2 pretty well. For example,

> None of that mattered at the scope we were modeling, so we abstracted it all away: "on receiving message, nondeterministically enter state A, B, or C."

That sounds like the author is describing an NFA.

> whereby we execute all the future possibilities... e.g. "amb" operator

Isn't "execute all possibilities" closer to the dual of amb than it is to amb? At least in terms of how the denotation of amb is operationalized.

But it is a good point that sometimes you want to give an actual operational meaning to a literal non-determinism operator.

And then then the different kinds of the latter: angelic (locally or globally) and demonic.

The non-determinism of Rust's HashMap/HashSet is because the default hasher seeds itself using the operating system's RNG facilities. You can use the with_hasher() function to replace the default hasher with a PRNG that is deterministically seeded.

It is deterministic, but if it's absurdly hard to prove, you just say it isn't deterministic.

Imagine a program that uses JSON and depends on the order of keys in an object. If you input the same object, but with different key order, you'll get different results.

The program is deterministic, but it looks non-deterministic to a naïve observer.

That's just a very simple example, in a more complex system there could be all kinds of uncommon behaviours that are less simple to trace. So when modeling the system, they just box it as "there be dragons" and move on.

The example is really bad for this because it doesn't say the result is non-deterministic, just complex and treated as a black box which only makes the result hard to reason about when abstracted rather than truly non-deterministic.

A common example from my domain is making floating point math deterministic. This is fairly straightforward for a single operating system/piece of hardware combination but as soon as you need cross-platform determinism is full of gotchas. In particular because the abstraction in this case is often the programming language, the specific compiler used (sometimes even version) and standard library. This also gets as subtle as not being able to use certain instructions like fused multiply-add and SIMD intrinsics where the implementation can differ between pieces of hardware.

The article wasn't bad, but the examples felt a bit thin; almost like the author was reaching a bit to hit that magic number of 5.

And you're definitely not wrong on the abstract subsection. I mean, essentially all he says is that "there's a mechanism in our system which is so complicated/convoluted that we decided not to model it with TLA, so instead we chose to simply call it non-deterministic, and therefore it is now abstract non-determinism." Hmm. If we're truly being abstract, that's not really all that different from the PRNG and user input examples, except, you know, it's actually still completely deterministic code.

Also, I have to say- 5 different types of non-determinism, and not one mention of quantum systems?

I took issue with #4 too. If your code consumes API endpoints that are non-deterministic, that strikes me as something you should take up with your vendor. An error condition on a network call is not non-determinism. It's just reality from time to time.

I think you're splitting hairs here. Not sure what definition or context of determinism you are using, but in most scientific fields not only is probability the de-facto example of non-determinism, but in fact the words are often used interchangeably.

By definition, if your outcome is a random draw from a probability distribution (known or unknown), you cannot guarantee the outcome in a deterministic manner; you can only guarantee that in the limit, a large number of random draws will follow that distribution (known or unknown). But that's not what one would typically call determinism.