The Sequential ASM Thesis.
Yuri G. Gurevich · 1999
state machines (ASMs) used to be called evolving algebras. The sequential ASM thesis and its extensions [Gurevich 1995] inspired diverse applications of ASMs. The early applications were driven, at least partially, by the desire to test the thesis. Di#erent programming languages were the obvious challenges: Modula-2 [Gurevich and Morris 1987], Prolog [Borger 1990a, 1990b, 1992], C [Gurevich and Huggins 1992], etc. (A programming language L can be viewed as an algorithm that runs a given L program on given data.) From there, applications of (not necessarily sequential) ASMs spread into many directions; see the recent bibliography [Borger and Huggins 1998] and the ASM websites [ASM Michigan, ASM Paderborn]. So far, the accumulated experimental evidence seems to support the sequential thesis. There is also a speculative philosophical justification of the thesis. It was barely sketched in the literature, but it was discussed at much greater l...