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.