JUCS - Journal of Universal Computer Science 3(4): 279-303, doi: 10.3217/jucs-003-04-0279
Gurevich Abstract State Machines and Schoenhage Storage Modification Machines
expand article infoScott Dexter‡, Patrick Doyle§, Yuri Gurevich‡
‡ University of Michigan, United States of America§ Stanford University, United States of America

Corresponding author: Scott Dexter ( sdexter@eecs.umich.edu )

© Scott Dexter, Patrick Doyle, Yuri Gurevich.
This article is freely available under the J.UCS Open Content License.
Citation: Dexter S, Doyle P, Gurevich Y (1997) Gurevich Abstract State Machines and Schoenhage Storage Modification Machines. JUCS - Journal of Universal Computer Science 3(4): 279-303. https://doi.org/10.3217/jucs-003-04-0279
Open Access
Abstract
We demonstrate that Schoenhage storage modification machines are equivalent, in a strong sense, to unary abstract state machines. We also show that if one extends the Schoenhage model with a pairing function and removes the unary restriction, then equivalence between the two machine models survives.