Ordinary interactive small-step algorithms, II

ABSTRACT

This is the second in a series of three articles 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. As in the first article of the series, we are concerned here with ordinary, small-step, interactive algorithms. This means that the algorithms:

(1) proceed in discrete, global steps,

(2) perform only a bounded amount of work in each step,

(3) use only such information from the environment as can be regarded as answers to queries, and

(4) never complete a step until all queries from that step have been answered.

After reviewing the previous article's formal description of such algorithms and the definition of behavioral equivalence, we define ordinary, interactive, small-step abstract state machines (ASMs). Except for very minor modifications, these are the machines commonly used in the ASM literature. We define their semantics in the framework of ordinary algorithms and show that they satisfy the postulates for these algorithms.

This material lays the groundwork for the final article in the series, in which we shall prove the Abstract State Machine thesis for ordinary, intractive, small-step algorithms: All such algorithms are equivalent to ASMs.

REFERENCES

• 1: Asml. The AsmL webpage. http://research.microsoft.com/foundations/AsmL/.
• 2: Andreas Blass , Yuri Gurevich, Abstract state machines capture parallel algorithms, ACM Transactions on Computational Logic (TOCL), v.4 n.4, p.578-651, October 2003 [doi>10.1145/937555.937561]
• 3: Andreas Blass , Yuri Gurevich, Ordinary interactive small-step algorithms, I, ACM Transactions on Computational Logic (TOCL), v.7 n.2, p.363-419, April 2006 [doi>10.1145/1131313.1131320]
• 4: Andreas Blass , Yuri Gurevich, Ordinary interactive small-step algorithms, III, ACM Transactions on Computational Logic (TOCL), v.8 n.3, p.16-es, July 2007 [doi>10.1145/1243996.1243999]
• 5: Blass, A., Gurevich, Y., Rosenzweig, D., and Rossman, B. 2007a. General interactive small-step algorithms. In preparation.
• 6: Blass, A., Gurevich, Y., Rosenzweig, D., and Rossman, B. 2007b. Composite interactive algorithms (tentative title) In preparation.
• 7: Blass, A., Gurevich, Y., Rosenzweig, D., and Rossman, B. 2007c. Interactive wide-step algorithms (tentative title) In preparation.
• 8: Yuri Gurevich, Evolving algebras 1993: Lipari guide, Specification and validation methods, Oxford University Press, Inc., New York, NY, 1995
• 9: Gurevich, Y. 1997. ASM guide. Tech. Rep., University of Michigan. CSE-TR-336-97. http://eecs.umich.edu/gasm.
• 10: Yuri Gurevich, Sequential abstract-state machines capture sequential algorithms, ACM Transactions on Computational Logic (TOCL), v.1 n.1, p.77-111, July 2000 [doi>10.1145/343369.343384]
• 11: Huggins, J. K. ASM Michigan webpage. http://www.eecs.umich.edu/gasm.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

General Terms:
Algorithms, Theory

Keywords:
Sequential algorithms, abstract state machines, equivalence of algorithms, interaction, postulates