Unbounded nondeterminism
In computer science, unbounded nondeterminism or unbounded indeterminacy refers to a behavior in concurrency 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.
This concept, explored in abstract models rather than practical systems, became significant in developing mathematical descriptions of such systems and later contributed to research on advanced computing theories.
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, assuming it to be a monotone function. Then he argued that, where is the empty stream. Now, so it must be that is an element of, a contradiction. He concluded that: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 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:Indeterminacy versus nondeterministic automata
William Clinger provided the following analysis of the above proof: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:- The first part requests the second part for a natural number, then runs the Turing machine for exactly that many steps. If the machine halts within those steps, the algorithm accepts ; if not, it rejects.
- The second part nondeterministically picks a natural number when requested, starting at 0. It repeatedly chooses between two actions: increase the number by 1 or return the current number to the first part. The fairness constraint ensures it eventually sends the number, avoiding an endless loop of just increasing it.
Arguments for dealing with unbounded nondeterminism
Clinger and Carl Hewitt have developed a model of concurrent computation with the property of unbounded nondeterminism built in ; this allows computations that cannot be implemented by Turing Machines, as seen above. However, these researchers emphasize that their model of concurrent computations defined by Church, Kleene, Turing, etc.Hewitt justified his use of unbounded nondeterminism by arguing that there is no bound that can be placed on how long it takes a computational circuit called an arbiter to settle. Arbiters are used in computers to deal with the circumstance that computer clocks operate asynchronously with input from outside, e.g.., keyboard input, disk access, network input, etc. So it could take an unbounded time for a message sent to a computer to be received and in the meantime the computer could traverse an unbounded number of states.
He further argued that Electronic mail enables unbounded nondeterminism since mail can be stored on servers indefinitely before being delivered, and that data links to servers on the Internet can likewise be out of service indefinitely. This gave rise to the unbounded nondeterminism controversy.
Hewitt's analysis of fairness
Hewitt argued that issues in fairness derive in part from the global state point of view. The oldest models of computation are based on mathematics that makes use of a global state to represent a computational step. Each computational step is from one global state of the computation to the next global state. The global state approach was continued in automata theory for finite-state machines and push down stack machines including their nondeterministic versions. All of these models have the property of bounded nondeterminism: if a machine always halts when started in its initial state, then there is a bound on the number of states in which it can halt.Hewitt argued that there is a fundamental difference between choices in global state nondeterminism and the arrival order indeterminacy of his Actor model. In global state nondeterminism, a "choice" is made for the "next" global state. In arrival order indeterminacy, arbitration locally decides each arrival order in an unbounded amount of time. While a local arbitration is proceeding, unbounded activity can take place elsewhere. There is no global state and consequently no "choice" to be made as to the "next" global state.