COLLOQUIUM
             Computer Science Department, Boston University

Speaker: Yuri Gurevich
         Microsoft Research

Date:  Monday, May 16
Time:  11:00
Place: Room MCS 135, 111 Cummington Street 
       (for directions, see www.cs.bu.edu/colloquium)

Title: Intra-Step Interaction

Abstract:

A nondeterministic algorithm is a contradiction in terms.  How can an
algorithm be nondeterminstic?  By definition, an algorithm just follows
instructions; no creative solutions are expected.  Imagine that you are an
algorithm, and they tell you to write either 0 or 1 without giving you any
instructions how to perform the choice.  What should you do?  You are just
an algorithm.  Of course, an algorithm can be instructed to solicit help.
And that is exactly what happens in practice.  A nondeterministic choice
is performed by means of an intra-step query that algorithm poses to its
environment.  Creating a new object by an object-oriented program in a
conventional language is another example of an intra-step query.  Again,
the algorithm has no means to create a new object.  The NEW command is a
cry for help directed to the environment.  In the talk, we will report on
our analysis and formalization of intra-step interaction.  

This is joint work with Andreas Blass, Benjamin Rossman and Dean
Rosenzweig partially reflected in articles 166, 170 and 171 at the
author's website.

Host: Leonid Levin