The Expressive Power of Abstract-State Machines

keywords: Specification technique, expressive power, computation models, sequential algorithms, transition systems, Abstract State Machines
Conventional computation models assume symbolic representations of states and actions. Gurevich's ``Abstract-State Machine'' model takes a more liberal position: Any mathematical structure may serve as a state. This results in ``a computational model that is more powerful and more universal than standard computation models'' citeGur85. We characterize the Abstract-State Machine model as a special class of transition systems that widely extends the class of ``computable'' transition systems. This characterization is based on a fundamental Theorem of Y. Gurevich.
reference: Vol. 22, 2003, No. 3-4, pp. 209–219