In computer science, unbounded nondeterminism or unbounded indeterminacy refers to a behavior in concurrency (multiple tasks running at once) where a process may face unpredictable delays due to competition for shared resources—such as a printer or memory—or have infinitely many options to choose from at a given point. While these delays or choices can be arbitrarily large, the process is typically guaranteed to complete eventually under certain conditions (e.g., fairness in resource allocation). This concept, explored in abstract models rather than practical systems, became significant in developing mathematical descriptions of such systems (denotational semantics) and later contributed to research on advanced computing theories (hypercomputation).
Fairness Unbounded nondeterminism is often discussed alongside the concept of fairness. In this context, fairness means that if a system keeps returning to a certain state forever, it must eventually try every possible next step from that state. For example, if a task is waiting to use a shared tool—like a printer—it can’t be delayed forever; fairness ensures it gets its turn, even if the wait is unpredictable and long. This guarantee matters when a system runs indefinitely, preventing any option from being ignored over time. This idea of fairness isn’t like flipping a "fair" coin forever. With a coin, random chance means you’d eventually see both heads and tails, but there’s no rule forcing it—pure luck could delay one outcome for an arbitrarily long time. In unbounded nondeterminism, fairness isn’t about hoping every step happens; it’s a strict requirement that they do, regardless of chance.
Example An example of the role of fair or unbounded nondeterminism in the merging of strings was given by William D. Clinger, in his 1981 thesis. He defined a "fair merge" of two strings to be a third string in which each character of each string must occur eventually. He then considered the set of all fair merges of two strings merge(S, T), assuming it to be a monotone function. Then he argued that merge(⊥,1ω)⊆ merge(0,1ω), where ⊥ is the empty stream. Now merge(⊥,1ω) = {1ω}, so it must be that 1ω is an element of merge(0,1ω), a contradiction. He concluded that:
It appears that a fair merge cannot be written as a nondeterministic data flow program operating on streams.
Implementation Edsger Dijkstra argued that it is impossible to implement systems with unbounded nondeterminism. For this reason, Tony Hoare suggested that "an efficient implementation should try to be reasonably fair."
Nondeterministic automata Unlike systems with unbounded nondeterminism, nondeterministic Turing machines exhibit only bounded nondeterminism. This means their choices—such as which path to take at a decision point—are limited to a fixed number of options at each step, keeping delays predictable and finite. Similarly, sequential programs that use guarded commands (rules that pick one action from a set based on conditions) as their only source of nondeterminism also stay bounded, since the number of possible choices doesn’t grow without limit. In these cases, known as choice nondeterminism, the system’s behavior remains constrained. Mathematician Gordon Plotkin formalized this in his original paper on powerdomains, proving that such nondeterminism has clear limits, unlike the unbounded delays seen in concurrent systems:
Now the set of initial segments of execution sequences of a given nondeterministic program P, starting from a given state, will form a tree. The branching points will correspond to the choice points in the program. Since there are always only finitely many alternatives at each choice point, the branching factor of the tree is always finite. That is, the tree is finitary. Now Kőnig's lemma says that if every branch of a finitary tree is finite, then so is the tree itself. In the present case this means that if every execution sequence of P terminates, then there are only finitely many execution sequences. So if an output set of P is infinite, it must contain [a nonterminating computation].
Indeterminacy versus nondeterministic automata William Clinger provided the following analysis of the above proof:
This proof depends upon the premise that if every node x of a certain infinite branch can be reached by some computation c, then there exists a computation c that visits every node x on the branch. ... Clearly this premise follows not from logic but rather from the interpretation given to choice points. This premise fails for arrival nondeterminism [in the arrival of messages in the Actor model] because of finite delay [in the arrival of messages]. Though each node on an infinite branch must lie on a branch with a limit, the infinite branch need not itself have a limit. Thus the existence of an infinite branch does not necessarily imply a nonterminating computation.
Unbounded nondeterminism and noncomputability Spaan et al. have suggested that unbounded nondeterminism could theoretically solve the halting problem, a famous challenge in computability theory that asks whether a Turing machine will stop or continue forever on a given input—a problem proven unsolvable by standard machines. They propose an algorithm split into two parts:
… excerpt ends here. Continue reading the full article.
