Gurevich Abstract State Machines and Schoenhage Storage Modification Machines

Scott Dexter (University of Michigan, USA)

Patrick Doyle (Stanford University, USA)

Yuri Gurevich (University of Michigan, USA)

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.