Ordinary Interactive Small-Step Algorithms, III
- Yuri Gurevich
ACM Transactions on Computational Logic |
This is the third in a series of three papers extending the proof of the Abstract State Machine Thesis — that arbitrary algorithms are behaviorally equivalent to abstract state machines — to algorithms that can interact with their environments during a step rather than only between steps. The first two papers are “Ordinary Interactive Small-Step Algorithms, I” and “Ordinary Interactive Small-Step Algorithms, II” As in the first two papers of the series, we are concerned here with ordinary, small-step, interactive algorithms. This means that the algorithms:
- proceed in discrete, global steps,
- perform only a bounded amount of work in each step,
- use only such information from the environment as can be regarded as answers to queries, and
- never complete a step until all queries from that step have been answered.
After reviewing the previous papers’ definitions of such algorithms, of behavioral equivalence, and of abstract state machines (ASMs), we prove the main result: Every ordinary, interactive, small-step algorithm is behaviorally equivalent to an ASM. We also discuss some possible variations of and additions to the ASM semantics.
The work of the first author was partially supported by NSF grant DMS{0070723 and by a grant from Microsoft Research. Much of this paper was written during visits to Microsoft Research. Permission to make digital/hard copy of all or part of this material without fee for personal or classroom use provided that the copies are not made or distributed for profit or commercial advantage, the ACM copyright/server notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists requires prior specific permission and/or a fee. © 2007 ACM 1529-3785/07/0600-0001.