A behavioural theory consists of machine-independent postulates characterizing a particular class of algorithms or systems, an abstract machine model that provably satisfies these postulates, and a rigorous proof that any algorithm or system stipulated by the postulates is captured by the abstract machine model. The class of interest in this article is that of (synchronous) parallel algorithms. For this class a behavioural theory has already been developed by Blass and Gurevich, which unfortunately, though mathematically correct, fails to be convincing, as it is not intuitively clear that the postulates really capture the essence of (synchronous) parallel algorithms.In this article we present a much simpler (and presumably more convincing) set of four postulates for (synchronous) parallel algorithms, which are rather close to those used in Gurevich's celebrated sequential ASM thesis, i.e. the behavioural theory of sequential algorithms. The key difference is made by an extension of the bounded exploration postulate using multiset comprehension terms instead of ground terms formulated over the signature of the states. In addition, all implicit assumptions are made explicit, which amounts to considering states of a parallel algorithm to be represented by meta-finite first-order structures.The article first provides the necessary evidence that the axiomatization presented in this article characterizes indeed the whole class of (synchronous) parallel algorithms, then formally proves that parallel algorithms are captured by Abstract State Machines (ASMs). The proof requires some recourse to methods from finite model theory, by means of which it can be shown that if a critical tuple defines an update in some update set, then also every other tuple that is logically indistinguishable defines an update in that update set.
The seminal work of Gurevich @cite_8 on Abstract State Machines (ASMs, formerly called evolving algebras'') aimed to find a precise formal definition of the notion of algorithm. The major discovery was that all computing formalisms were bound to a specific abstraction level, which implied that almost always encodings were required @cite_1 @cite_18 , so the major breakthrough of ASMs was due to the abstract notion of state, which is defined by general Tarski structures.
@cite_18 @cite_1 @cite_8
2140718089 1998333922 1969402593
How can one possibly analyze computation in general? The task seems daunting if not impossible. There are too many different kinds of computation, and the notion of general computation seems too amorphous. As in quicksand, one needs a rescue point, a fulcrum. In computation analysis, a fulcrum is a particular viewpoint on computation that clarifies and simplifies things to the point that analysis becomes possible. We review from that point of view the few foundational analyses of general computation in the literature: Turing's analysis of human computations, Gandy's analysis of mechanical computations, Kolmogorov's analysis of bit-level computation, and our own analysis of computation on the arbitrary abstraction level. We examine sequential algorithms and formulate a sequential-time postulate, an abstract-state postulate, and a bounded-exploration postulate . Analysis of the postulates leads us to the notion of sequential abstract-state machine and to the theorem in the title. First we treat sequential algorithms that are deterministic and noninteractive. Then we consider sequential algorithms that may be nondeterministic and that may interact with their environments. 2 Static Algebras and Updates 4 2.1 Static Algebras: Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Vocabularies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Definition of Static Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4 Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.5 Locations and Updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.6 Update Sets and Families of Update Sets . . . . . . . . . . . . . . . . . . . . . . . . 6 2.7 Conservative Determinism vs. Local Nondeterminism . . . . . . . . . . . . . . . . . . 7