In earlier work, the Abstract State Machine Thesis -- that arbitrary algorithms are behaviorally equivalent to abstract state machines -- was established for several classes of algorithms, including ordinary, interactive, small-step algorithms. This was accomplished on the basis of axiomatizations of these classes of algorithms. Here we extend the axiomatization and, in a companion paper, the proof, to cover interactive small-step algorithms that are not necessarily ordinary. This means that the algorithms (1) can complete a step without necessarily waiting for replies to all queries from that step and (2) can use not only the environment's replies but also the order in which the replies were received.
The says that an algorithm defines a deterministic transition system, a (not necessarily finite-state) automaton. More explicitly, the algorithm determines a nonempty collection of states, a nonempty subcollection of initial states, and a state-transition function. The algorithm is presumed to be deterministic. Nondeterministic choices involve interaction with the environment; see @cite_15 @cite_12 @cite_27 for discussion. The term state is used in a comprehensive way. For example, in case of a Turing machine, a state would include not only the control state but also the head position and the tape contents.
@cite_27 @cite_15 @cite_12
197061278 1969402593 1998333922
In earlier work, the Abstract State Machine Thesis — that arbitrary algorithms are behaviorally equivalent to abstract state machines — was established for several classes of algorithms, including ordinary, interactive, small-step algorithms. This was accomplished on the basis of axiomatizations of these classes of algorithms. Here we extend the axiomatization and the proof to cover interactive smallstep algorithms that are not necessarily ordinary. This means that the algorithms (1) can complete a step without necessarily waiting for replies to all queries from that step and (2) can use not only the environment’s replies but also the order in which the replies were received. In order to prove the thesis for algorithms of this generality, we extend the definition of abstract state machines to incorporate explicit attention to the relative timing of replies and to the possible absence of replies. ∗Partially supported by NSF grant DMS–0070723 and by a grant from Microsoft Research. Address: Mathematics Department, University of Michigan, Ann Arbor, MI 48109–1043, U.S.A., ablass@umich.edu. Much of this paper was written during a visit to Microsoft Research. †Microsoft Research, One Microsoft Way, Redmond, WA 98052, U.S.A. gurevich@microsoft.com ‡Microsoft Research; and University of Zagreb, FSB, I. Lucica 5, 10000 Zagreb, Croatia, dean@math.hr §Microsoft Research; current address: Computer Science Dept., M.I.T., Cambridge, MA 02139, U.S.A., brossman@mit.edu 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 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.