Abstract

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.

Keywords

Cite this article

@article{cai-1307,
  author  = {Wolfgang Reisig},
  title   = {The Expressive Power of Abstract-State Machines},
  journal = {Computing and Informatics},
  volume  = {22},
  number  = {3-4},
  pages   = {209--219},
  year    = {2003},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2003/3-4/the-expressive-power-of-abstract-state-machines/}
}
Download .bib