Bounded nondeterminism means that there is a bound determined by initial input for the number of possibilities that a system can explore given that it must al

Bounded nondeterminism means that there is a bound determined by initial input for the number of possibilities that a system can explore given that it must always come back with an answer. A Nondeterministic Turing Machine has the property of bounded nondeterminism because it starts in a global state and from each state there are finitely many possible successor states. Because the machine must always produce an answer, each path must be finite and consequently the total number of states that can be explored is finite. In the development of a theory of concurrent computation, Dijkstra remained committed to a global state model of computation. This commitment gave rise to the “unbounded nondeterminism” controversy. Digital systems can be physically indeterminate by making use of arbiters in order to resolve reception order in communication between systems. Because of physical indeterminacy, a digital system can have the property of unbounded nondeterminism in that no bound exists when it is started on the number of possibilities that an always-responding digital system can explore. Consequently, there are digital computations that cannot be performed by a nondeterministic Turing Machine. Being restricted to bounded nondeterminism is one the reasons that the lambda calculus and Turing Machines models are inadequate for digital computation.