The Dr. Alan Mekler Memorial Endowment was established at Simon Fraser University by colleagues, friends and family in memory of Dr. Mekler. Dr. Mekler was a member of the Mathematics Department from 1980 until his death from cancer in 1992. During his life he was known to us as a juggler, birder, mathematician and lover of life. A valuable colleague, he was recognized internationally for his work in the applications of set theory and model theory to algebraic systems. He had an appreciation for an understanding of much diverse mathematics.

Yuri Gurevich (research.microsoft.com/~gurevich) heads the Foundations of Software Engineering group at Microsoft Research in Redmond, WA. He is Professor Emeritus of Electrical Engineering and Computer Science at the University of Michigan. He started his career as an algebraist. Then he became a logician. Finally he moved to computer science, where his main projects have been Abstract State Machines, Average Case Computational Complexity, and Finite Model Theory. Dr. Gurevich has been honored as a Dr. Honoris Causa of the University of Limburg, Belgium (1998), as a Fellow of the Association for Computing Machinery (1996), as well as a Fellow of the John Simon Guggenheim Memorial Foundation (1995).

Abstract: One may think that the title problem was solved long ago by Church and Turing. It wasn't; there is more to an algorithm than the function it computes. (Besides, what function does an operating system compute? The term algorithm is understood broadly here.) The interest to the problem is not only theoretical. Applications include modeling, specification, verification, design and testing of software and hardware systems. The first part of the talk will be devoted to the sequential abstract state machine (ASM) thesis: every sequential algorithm is behaviorally equivalent to a sequential ASM. The thesis was proved recently (ACM Transactions on Computational Logic 1, no. 1, July 2000) from first principles. The remainder of the talk will be devoted to extensions of the thesis to general computations and to the current applications of ASMs in Microsoft and elsewhere.