Evolving Multialgebras Unify All Usual Sequential Computation Models

Serge Grigorieff & Pierre Valarcher
It is well-known that Abstract State Machines (ASMs) can simulate step-by-step" any type of machines (Turing machines, RAMs, etc.). We aim to overcome two facts: 1) simulation is not identification, 2) the ASMs simulating machines of some type do not constitute a natural class among all ASMs. We modify Gurevich's notion of ASM to that of EMA (Evolving MultiAlgebra") by replacing the program (which is a syntactic object) by a semantic object: a functional which...