Unbounded nondeterminism

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.

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 {{mono|merge(S, T)}}, assuming it to be a monotone function. Then he argued that {{mono|merge(⊥,1^ω)⊆ merge(0,1^ω)}}, where {{mono|⊥}} is the empty stream. Now {{mono|merge(⊥,1^ω) {{=}} {1^ω}}}, so it must be that {{mono|1^ω}} is an element of {{mono|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.{{refn|name=clinger81|{{cite tech report|last=Clinger|first=William D.|author-link=William Clinger (computer scientist)|title=Foundations of Actor Semantics|type=AI Technical Report|issue=633|institution=Massachusetts Institute of Technology|date=May 1, 1981|hdl=1721.1/6935}}}}

Edsger Dijkstra argued that it is impossible to implement systems with unbounded nondeterminism.{{refn|name=dijkstra76|{{cite book|last=Dijkstra|first=Edsger|author-link=Edsger W. Dijkstra|date=1976|title=A Discipline of Programming|series=Prentice-Hall Series in Automatic Computation|publisher=Prentice-Hall|isbn=9780613924115}}}} For this reason, Tony Hoare suggested that "an efficient implementation should try to be reasonably fair."{{refn|name=hoare78|{{cite journal|last=Hoare|first=C. A. R.|author-link=Tony Hoare|date=August 1978|title=Communicating Sequential Processes|journal=Communications of the ACM|volume=21|issue=8|pages=666–677|doi=10.1145/359576.359585|s2cid=849342 |doi-access=free}}}}

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.{{r|name=dijkstra76}} 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 {{mono|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 {{mono|P}} terminates, then there are only finitely many execution sequences. So if an output set of {{mono|P}} is infinite, it must contain [a nonterminating computation].{{refn|name=plotkin76|{{cite journal|last=Plotkin|first=Gordon|author-link=Gordon Plotkin|date=September 1976|title=A powerdomain construction|journal=SIAM Journal on Computing|volume=5|issue=3|pages=452–487|doi=10.1137/0205035}}}}

William Clinger provided the following analysis of the above proof:

:This proof depends upon the premise that if every node {{mono|x}} of a certain infinite branch can be reached by some computation {{mono|c}}, then there exists a computation {{mono|c}} that visits every node {{mono|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.{{refn|name=clinger81}}

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:{{refn|name=spaanetc89|{{cite journal|last1=Spaan|first1=Edith|last2=Torenvliet|first2=Leen|last3=van Emde Boas|first3=Peter|author-link3=Peter van Emde Boas|title=Nondeterminism, Fairness and a Fundamental Analogy|date=February 1989|journal=Bulletin of the EATCS|volume=37|pages=186–193}}}}

1. 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 (indicating "it halts"); if not, it rejects ("it has not halted").
2. 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.

If the Turing machine halts after a finite number of steps—for example, 50—the algorithm has a path where the second part selects 50 or more, allowing the first part to detect the halt and accept. If the machine never halts, the first part rejects for any finite number chosen, since no fixed run can confirm an infinite process. Unbounded nondeterminism enables the second part to explore every possible number across infinite time, and fairness ensures a choice is made, implying all possibilities are evaluated. This suggests the algorithm could decide the halting problem, though it relies on an infinite process—a theoretical construct that uses unbounded steps to assess unbounded behavior, distinguishing it from the finite capabilities of standard Turing machines and linking it to noncomputability.

Clinger and Carl Hewitt {{Citation needed|date=September 2009}} have developed a model (known as the Actor model) of concurrent computation with the property of unbounded nondeterminism built in [Clinger 1981; {{refn|name=hewitt85|{{cite magazine|last=Hewitt|first=Carl|author-link=Carl Hewitt|title=The Challenge of Open Systems|date=April 1985|magazine=BYTE|publisher=McGraw Hill|pages=223–242|issn=0360-5280}} Reprinted as {{cite book|last=Hewitt|first=Carl|author-link=Carl Hewitt|editor-last1=Partridge|editor-first1=Derek|editor-last2=Wilks|editor-first2=Yorick|editor-link2=Yorick Wilks

|title=The Foundations of Artificial Intelligence: A Sourcebook|publisher=Cambridge University Press|date=April 1990|pages=383–395|chapter=The Challenge of Open Systems|isbn=9780521359443}}}}; {{refn|name=hewittagha91|{{cite conference|last1=Hewitt|first1=Carl|author-link1=Carl Hewitt|last2=Agha|first2=Gul|author-link2=Gul Agha (computer scientist)|title=Guarded Horn clause languages: are they deductive and logical?|date=1988|book-title=Proceedings of the International Conference on Fifth Generation Computer Systems|pages=650–657|location=Tokyo, Japan|publisher=OHMSHA Ltd. Tokyo and Springer-Verlag|conference=FGCS 1988|isbn=3540195580}} Also as {{cite book|last1=Hewitt|first1=Carl|author-link1=Carl Hewitt|last2=Agha|first2=Gul|author-link2=Gul Agha (computer scientist)|editor-last1=Winston|editor-first1=Patrick Henry|editor-link1=Patrick Henry Winston|editor-last2=Shellard|editor-first2=Sarah Alexandra|title=Artificial Intelligence at MIT: Expanding Frontiers|publisher=MIT Press|chapter=Guarded Horn clause languages: are they deductive and logical?|date=June 1991|pages=582–593|isbn=9780262231503}}

}}; {{refn|name=hewitt06b|{{cite conference|last=Hewitt|first=Carl|author-link=Carl Hewitt|title=What Is Commitment? Physical, Organizational, and Social|book-title=Coordination, Organizations, Institutions, and Norms in Agent Systems II|date=May 2006|conference=AAMAS 2006 International Workshop, COIN|publisher=Springer Berlin Heidelberg|place=Hakodate, Japan|pages=293–307|doi=10.1007/978-3-540-74459-7_19}}}}]; this allows computations that cannot be implemented by Turing Machines, as seen above. However, these researchers emphasize that their model of concurrent computations {{Citation needed span|text=cannot implement any functions that are outside the class of recursive functions|date=July 2017|reason=WP link doesn't support this claim}} defined by Church, Kleene, Turing, etc. (See Indeterminacy in concurrent computation.)

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 (see metastability in electronics). 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.{{refn|name=hewitt06|{{cite conference|last=Hewitt|first=Carl|author-link=Carl Hewitt|title=The Repeated Demise of Logic Programming and Why It Will Be Reincarnated|book-title=What Went Wrong and Why: Lessons from AI Research and Applications|date=March 2006|conference=2006 AAAI Spring Symposium|type=Technical Report|id=SS-06-08|publisher=AAAI|place=Stanford, California|pages=2–9|url=http://www.aaai.org/Library/Symposia/Spring/2006/ss06-08-003.php|access-date=March 10, 2022}}}}

Hewitt argued that issues in fairness derive in part from the global state point of view. The oldest models of computation (e.g.. Turing machines, Post productions, the lambda calculus, etc.) 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 (nondeterminism) 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.

{{reflist}}

• {{cite conference|last1=Hewitt|first1=Carl|author-link1=Carl Hewitt|last2=Bishop|first2=Peter|last3=Steiger|first3=Richard|title=A universal modular ACTOR formalism for artificial intelligence|book-title=Proceedings of the 3rd international joint conference on Artificial intelligence|date=August 1973|conference=IJCAI'73|publisher=Morgan Kaufmann|place=Stanford|pages=235–245}}
• {{cite conference|last=Milner|first=Robin|author-link=Robin Milner|title=Processes: a mathematical model of computing agents|book-title=Proceedings of the Logic Colloquium|date=1973|conference=Logic Colloquium '73|publisher=North Holland|place=Bristol|pages=157–173}}
• {{cite conference|last1=Hewitt|first1=Carl|author-link1=Carl Hewitt|last2=Bishop|first2=Peter|last3=Greif|first3=Irene|author-link3=Irene Greif|last4=Smith|first4=Brian|last5=Matson|first5=Todd|last6=Steiger|first6=Richard|title=Actor Induction and Meta-evaluation|book-title=Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages|date=October 1973|conference=POPL'73|publisher=Association for Computing Machinery|place=Boston, Massachusetts|pages=153–168|doi=10.1145/512927.512942}}
• {{cite conference|last1=Hewitt|first1=Carl|author-link1=Carl Hewitt|last2=Bishop|first2=Peter|last3=Steiger|first3=Richard|last4=Greif|first4=Irene|author-link4=Irene Greif|last5=Smith|first5=Brian|last6=Matson|first6=Todd|last7=Hale|first7=Roger|editor-last=Robinet|editor-first=B.|title=Behavioral semantics of nonrecursive control structures|book-title=Proceedings of Colloque sur la programmation|date=April 1974|conference=Programming Symposium|publisher=Springer Berlin Heidelberg|place=Paris|pages=385–407|doi=10.1007/3-540-06859-7_147|isbn=9783540378198}}
• {{cite thesis|last=Greif|first=Irene|author-link=Irene Greif|title=Semantics of communicating parallel processes|degree=PhD|publisher=Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science|date=August 1975|hdl=1721.1/57710}}
• {{cite conference|last1=Hewitt|first1=Carl|author-link1=Carl Hewitt|last2=Baker|first2=Henry|author-link2=Henry Baker (computer scientist)|editor-last1=Neuhold|editor-first1=Erich J.|title=Actors and Continuous Functionals|book-title=Proceedings of the IFIP Working Conference on Formal Description of Programming Concepts|date=August 1977|conference=IFIP'78|publisher=North-Holland|place=St. Andrews, N.B., Canada|isbn=9780444851079}}
• {{cite tech report|last1=Kahn|first1=Gilles|author-link1=Gilles Kahn|last2=MacQueen|first2=David|title=Coroutines and Networks of Parallel Processes|type=Research Report|date=1976|url=https://hal.inria.fr/inria-00306565|access-date=March 9, 2022}}
• {{cite thesis|last=Baker|first=Henry|author-link=Henry Baker (computer scientist)|title=Actor Systems for Real-Time Computation|degree=PhD|publisher=Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science|date=January 1978}}
• {{cite journal|last=Smyth|first=Michael|title=Power domains|journal=Journal of Computer and System Sciences|volume=16|pages=23–36|date=1978|doi=10.1016/0022-0000(78)90048-X|doi-access=free}}
• {{cite journal|last1=Milne|first1=George|last2=Milner|first2=Robin|author-link2=Robin Milner|title=Concurrent processes and their syntax|journal=Journal of the ACM|volume=6|issue=2|date=April 1979|pages=302–321|doi=10.1145/322123.322134|s2cid=16565064 |doi-access=free}}
• {{cite journal|last1=Francez|first1=Nissim|author-link1=Nissim Francez|last2=Hoare|first2=C. A. R.|author-link2=Tony Hoare|last3=Lehmann|first3=Daniel J.|last4=de Roever|first4=Willem P.|title=Semantics of nondeterminism, concurrency, and communication|journal=Journal of Computer and System Sciences|volume=19|issue=3|pages=290–308|date=December 1979|doi=10.1016/0022-0000(79)90006-0|doi-access=free}}
• {{cite conference|last1=Lynch|first1=Nancy A.|author-link1=Nancy Lynch|last2=Fischer|first2=Michael J.|author-link2=Michael J. Fischer|editor-last=Kahn|editor-first=Gilles|editor-link=Gilles Kahn|title=On describing the behavior and implementation of distributed systems|book-title=Proceedings of the International Symposium on Semantics of Concurrent Computation|date=July 1979|conference=Semantics of Concurrent Computation|publisher=Springer-Verlag|place=Evian, France|pages=147–171|doi=10.1007/BFb0022468|isbn=9783540351634}}
• {{cite conference|last=Schwartz|first=Jerald S.|editor-last=Kahn|editor-first=Gilles|editor-link=Gilles Kahn|title=Denotational semantics of parallelism|book-title=Proceedings of the International Symposium on Semantics of Concurrent Computation|date=July 1979|conference=Semantics of Concurrent Computation|publisher=Springer-Verlag|place=Evian, France|pages=191–202|doi=10.1007/BFb0022470|isbn=9783540351634}}
• {{cite conference|last=Wadge|first=William W.|editor-last=Kahn|editor-first=Gilles|editor-link=Gilles Kahn|title=An extensional treatment of dataflow deadlock|book-title=Proceedings of the International Symposium on Semantics of Concurrent Computation|date=July 1979|conference=Semantics of Concurrent Computation|publisher=Springer-Verlag|place=Evian, France|pages=285–299|doi=10.1007/BFb0022475|isbn=9783540351634}}
• {{cite conference|last=Back|first=Ralph-Johan|author-link=Ralph-Johan Back|editor-last1=de Bakker|editor-first1=Jaco|editor-link1=Jaco de Bakker|editor-last2=van Leeuwen|editor-first2=Jan|editor-link2=Jan van Leeuwen|title=Semantics of unbounded nondeterminism|book-title=Seventh Colloquium on Automata, Languages and Programming|date=July 1980|conference=International Colloquium on Automata, Languages, and Programming|publisher=Springer-Verlag Berlin Heidelberg|place=Noordwijkerhout, the Netherlands|pages=51–63|doi=10.1007/3-540-10003-2_59}}
• {{cite conference|last=Park|first=David|author-link=David Park (computer scientist)|editor-last=Bjørner|editor-first=Dines|editor-link=Dines Bjørner|title=On the semantics of fair parallelism|book-title=Abstract Software Specifications|date=1979|conference=1979 Copenhagen Winter School|publisher=Springer-Verlag Berlin Heidelberg|place=Copenhagen|pages=504–526|doi=10.1007/3-540-10007-5_47}}

• Dana Scott. What is Denotational Semantics? MIT Laboratory for Computer Science Distinguished Lecture Series. April 17, 1980.

• {{cite conference|last=Clinger|first=William|author-link=William Clinger (computer scientist)|editor-last1=Park|editor-first1=David M. R.|editor-last2=Friedman|editor-first2=Daniel P.|editor-link2=Daniel P. Friedman|title=Nondeterministic call by need is neither lazy nor by name|book-title=Proceedings of the 1982 ACM symposium on LISP and functional programming|date=August 1982|conference=LFP'82|publisher=Association for Computing Machinery|place=Pittsburgh, Pennsylvania|pages=226–234|doi=10.1145/800068.802154}}
• {{cite journal|last1=Brookes|first1=S. D.|last2=Hoare|first2=C. A. R.|author-link2=Tony Hoare|last3=Roscoe|first3=A. W.|author-link3=Bill Roscoe|title=A Theory of Communicating Sequential Processes|journal=Journal of the ACM|volume=31|issue=3|date=July 1984|pages=560–599|doi=10.1145/828.833|s2cid=488666 |doi-access=free}}
• {{cite tech report|last=Roscoe|first=A. W.|author-link=Bill Roscoe|title=Two Papers on CSP|type=Technical monograph|date=January 1988|publisher=Oxford University Computing Laboratory|chapter=Unbounded nondeterminism in CSP|id=PRG67|url=http://www.cs.ox.ac.uk/files/3388/PRG67.pdf|access-date=March 10, 2022}}
• {{cite book|last=Roscoe|first=A. W.|author-link=Bill Roscoe|title=The Theory and Practice of Concurrency|publisher=Prentice-Hall|isbn=9780136744092|date=November 10, 1997}}
• {{cite book|last=Schmidt|first=David A.|title=The Structure of Typed Programming Languages|publisher=The MIT Press|isbn=9780262193498|date=March 1994}}
• {{cite journal|last1=Butler|first1=Michael|author-link1=Michael Butler (computer scientist)|last2=Morgan|first2=Carroll|author-link2=Carroll Morgan (computer scientist)|title=Action Systems, Unbounded Nondeterminism, and Infinite Traces|journal=Formal Aspects of Computing|volume=7|issue=1|date=January 1995|pages=37–53|doi=10.1007/BF01214622|s2cid=2135743 |doi-access=free}}
• {{cite book|last=Sudkamp|first=Thomas A.|title=Languages and Machines: An Introduction to the Theory of Computer Science|edition=2nd|publisher=Addison-Wesley|date=January 3, 1997|isbn=9780201821369}}
• {{cite conference|editor-last1=Aceto|editor-first1=Luca|editor-last2=Gordon|editor-first2=Andrew D.|editor-link2=Andrew D. Gordon|book-title=Algebraic Process Calculi: The First Twenty Five Years and Beyond|date=August 2005|conference=PA'05|publisher=BRICS|place=University of Bologna Residential Center Bertinoro (Forlì), Italy}}
• {{cite conference|last=Brookes|first=Stephen|editor-last1=Aceto|editor-first1=Luca|editor-last2=Gordon|editor-first2=Andrew D.|editor-link2=Andrew D. Gordon|title=Retracing CSP|book-title=Algebraic Process Calculi: The First Twenty Five Years and Beyond|date=August 2005|conference=PA'05|publisher=BRICS|place=University of Bologna Residential Center Bertinoro (Forlì), Italy|pages=75–80|url=https://www.brics.dk/NS/05/3/BRICS-NS-05-3.pdf|access-date=March 10, 2022}}

{{DEFAULTSORT:Unbounded Nondeterminism}}

Category:Actor model (computer science)

Category:Concurrency (computer science)

Category:Models of computation

Category:Process calculi

Category:Denotational semantics