Algorithms vs. Machines

Citation: Andreas Blass and Yuri Gurevich, "Algorithms vs. Machines." Bulletin of EATCS, number 77, June 2002, 96-118.
Summary: A response to a paper of Moschovakis claiming that no state machine describes mergesort at its natural abstraction level. A natural recursive ASM for mergesort is given.
Subjects: ASM Extensions
Download: From Yuri Gurevich's home page in PDF.
Notes: Uses definitions of recursive ASMs.