Unbounded Nondeterminism - Arguments For Dealing With Unbounded Nondeterminism

Arguments For Dealing With Unbounded Nondeterminism

Clinger and Carl Hewitt have developed a model (known as the Actor 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 cannot implement any functions that are outside the class of recursive functions 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 Communication links to servers on the Internet can likewise be out of service indefinitely. This gave rise to the Unbounded nondeterminism controversy