| Indeterminacy In Computation |
Article Index for Indeterminacy |
Website Links For Indeterminacy |
Information AboutIndeterminacy In Computation |
|
Indeterminacy in computation is concerned with the effects of Indeterminacy in Concurrent Computation . Computation is an area in which indeterminacy is becoming increasingly important because of the massive increase in concurrency due to networking and the advent of many-core computer architectures. These computer systems make use of Arbiters which give rise to Indeterminacy . A LIMITATION OF LOGIC PROGRAMMING Patrick Hayes {Link without Title} argued that the "usual sharp distinction that is made between the processes of computation and deduction, is misleading". Robert Kowalski developed the thesis that ''computation could be subsumed by deduction'' and quoted with approval "Computation is controlled deduction." which he attributed to Hayes in his 1988 paper on the early history of Prolog. Contrary to Kowalski and Hayes, Carl Hewitt claimed that logical deduction was incapable of carrying out concurrent computation in open systems. Hewitt Hewitt and Agha [1991 , and other published work argued that mathematical models of concurrency did not determine particular concurrent computations as follows: The Actor model makes use of arbitration for determining which message is next in the Arrival Ordering of an Actor that is sent multiple messages concurrently. For example Arbiters can be used in the implementation of the arrival ordering of an Actor which are subject to Indeterminacy in the arrival order. Since the arrival orderings are indeterminate, they cannot be deduced from prior information by mathematical logic alone. Therefore mathematical logic can not implement concurrent computation in open systems. Note that although mathematical logic cannot implement general concurrency it can implement some special cases of current computation, ''e.g.,'' sequential computation and some kinds of Parallel computation including the Lambda Calculus . ARRIVAL ORDER INDETERMINACY According to Hewitt {Link without Title} , in concrete terms for Actor systems, typically we cannot observe the details by which the arrival order of messages for an Actor is determined. Attempting to do so affects the results and can even push the indeterminacy elsewhere. e.g., see Metastability In Electronics and Arbiters . Instead of observing the internals of arbitration processes of Actor computations, we await outcomes. Indeterminacy in arbiters produces indeterminacy in Actors. The reason that we await outcomes is that we have no alternative because of indeterminacy. It is important to be clear about the basis for the published claim about the limitation of mathematical logic. It was not just that Actors could not in general be implemented in mathematical logic. The published claim was that because of the indeterminacy of the physical basis of the Actor model, that no kind of deductive mathematical logic could escape the limitation. This became important later when researchers attempted to extend Prolog (which had some basis in Logic Programming ) to concurrent computation using message passing. (See the section below). What does the mathematical theory of Actors have to say about this? A ''closed'' system is defined to be one which does not communicate with the outside. Actor Model Theory provides the means to characterize all the possible computations of a closed Actor system. So mathematical logic can characterize (as opposed to implement) all the possible computations of a closed Actor system. Other models of concurrent systems, ''e.g.,'' Process Calculi , can sometimes be used to characterize closed concurrent computations. A LIMITATION OF LOGIC DUE TO LACK OF INFORMATION An open Actor system S is one in which the addresses of outside Actors can be passed into S in the middle of computations so that S can communicate with these outside Actors. These outside Actors can then in turn communicate with Actors internal to S using addresses supplied to them by S. It is impossible for mathematical logic even to characterize the behavior of such an open Actor system because how the outside Actors will communicate cannot be deduced. Furthermore due to limitation of the inability to deduce arrival orderings, even knowledge of what messages are sent from outside would not enable the response of S to be deduced. Other models of concurrent systems, ''e.g.,'' Process Calculi , can sometimes be used to implement open systems. PROLOG-LIKE CONCURRENT SYSTEMS WERE CLAIMED TO BE BASED ON MATHEMATICAL LOGIC Keith Clark , Herve Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. developed a family of Prolog -like concurrent message passing systems using unification of shared variables and data structure streams for messages. Claims were made that these systems were based on mathematical logic. This kind systems was used as the basis of the Japanese Fifth Generation Project (ICOT) . Like the Actor model, the Prolog-like concurrent systems were based on message passing and consequently were subject to the same indeterminacy. This was the basis of the argument in Carl Hewitt and Gul Agha {Link without Title} that the Prolog-like concurrent systems were neither deductive nor logical. LOGICAL OPERATIONS AND SYSTEM EFFICIENCY Hewitt maintained that a basic lesson can be learned from Prolog and the Prolog-like concurrent systems: a universal model of concurrent computation is limited by having any mandatory overhead in the basic communication mechanisms. This is an argument against including pattern-directed invocation using unification and extraction of messages from data structure streams as fundamental primitives. But compare Shapiro's survey of Prolog-like concurrent programming languages for arguments for inclusion. INDETERMINACY IN OTHER MODELS OF COMPUTATION Arbitration is the basis of the indeterminacy in the Actor Model of concurrent computation (see Actor Model Early History and Actor Model Theory ). It may also play a role in other models of concurrent systems such as Process Calculi . REFERENCES
SEE ALSO |
|
|