Ordinary interactive small-step algorithms, III
Authors:
Open Access
- 1 July 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 8 (3) , 16
Abstract
This is the third 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 two articles 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 articles' 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.Keywords
This publication has 5 references indexed in Scilit:
- Interactive Small-Step Algorithms I: AxiomatizationLogical Methods in Computer Science, 2007
- Ordinary interactive small-step algorithms, IIACM Transactions on Computational Logic, 2007
- Ordinary interactive small-step algorithms, IACM Transactions on Computational Logic, 2006
- Abstract state machines capture parallel algorithmsACM Transactions on Computational Logic, 2003
- Sequential abstract-state machines capture sequential algorithmsACM Transactions on Computational Logic, 2000