Mathematical Models of Interactive Computing

                        Dina Q Goldin
                Math/CS Dept, U. Mass / Boston


Interactive computational processes allow for input and output to
take place during the computation, in contrast to the traditional
models such as Turing machines where computation accepts predefined
input and transforms it into output.  Recent developments of set
theory and algebra provide a formal foundation for interactive models
of computation, allowing us to conclude that the interactive paradigm
pulls computer science out of the "Turing tarpit".

The key to formalization of interaction is a mathematical paradigm
shift from inductive (linear) to coinductive (circular) methods
for definition and reasoning:

 * non-well-founded sets, for a denotational semantics of interactive
        behavior;

 * coalgebras, for modeling the process of interactive computation;

 * bisimulation, for determining equivalence of interactive systems;

 * observational equivalence relations, for comparing expressiveness of
        these systems.

We will present a tutorial account of the mathematics of interaction.
We will also examine applications of our work to areas such as sequential
and distributed interactive systems, the Turing test, empirical models,
and Church's thesis.  We hope to demonstrate that this work enables
us to provide a bridge between formal models and empirical systems.

This is joint work with Peter Wegner, Brown University