# Jerusalem Mathematics Colloquium

Thursday, 29th April 2004, 4:00 pm

Mathematics Building, Lecture Hall 2

##

Professor Yuri Gurevich

(Microsoft Research)

"What is an Algorithm?"

** Abstract: **
One may think that the title problem was solved long ago by Church and
Turing but it wasn't; there is more to an algorithm that the function
it computes. (Besides, what function does an operating system compute?)
The interest to the problem is not only theoretical; applications include
specification and verification of software and hardware.

In the main part of the talk, we formalize the notion of sequential
algorithm, recall the definition of sequential abstract state machines
(ASMs), and then state precisely the Sequential Characterization
Theorem according to which, for every sequential algorithm A, there exists a
sequential ASM B indistinguishable from A as far as behavior is
concerned; in particular B simulates A step-for-step. The full proof of the
theorem is found in the ACM Transactions on Computational Logic 1:1 (2000) or
on the author's webpage (article 141).

If time allows, we will also discuss generalizations of the
Sequential Characterization Theorem to parallel and distributed algorithms,
and the applications of the ASM approach at Microsoft.

Light refreshments will be served in the faculty lounge at 3:30.

List of talks, 2003-04

List of talks, 2002-03

List of talks, 2001-02

List of talks, 2000-01

List of talks, 1998-99

List of talks, 1997-98