22 November 2000, Computational Logic Seminar

22 November 2000, Computational Logic Seminar
Speaker: Yuri Gurevich ,Microsoft Research
Title: What is an Algorithm?
Date and Time: November 22, 2000, 13.15-15.00
Location: ILLC, Plantage Muidergracht 24, Amsterdam, room P.017

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 that 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.

For more information, see http://www.illc.uva.nl/~mdr/ACLG/Local/seminar00-2.html.