Formalization of Interactive Computing

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


Computer technology has shifted from mainframes to locally networked
workstations and now to mobile internet-based personal clients.  Software 
engineering has evolved from procedure-oriented to object-oriented and 
component-based systems.  AI has refocused from logical reasoning and search 
algorithms to agent-oriented and distributed behaviors.  These parallel 
changes exemplify a conceptual paradigm shift from algorithms to interaction.

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 consists of accepting a predefined input and 
transforming it into output.  Though interaction is an intuitively obvious 
idea, there has been no domain-independent formalization of interactive models 
of computation.

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 system expressiveness.

In this talk, we define sequential and multi-agent interaction machines, 
providing the semantics of their behavior in terms of non-well-founded sets 
and coinductive reasoning.  We formulate observation-based notions of system 
equivalence and computational expressiveness, and apply them to demonstrate 
that interaction machines are more powerful than Turing machines.

This is joint work with Peter Wegner, Brown University
-------------------------------------------------------------------


Dina Q Goldin is an Assistant Professor of Computer Science at the University 
of Massachusetts in Boston, specializing in Theory of Systems.  She obtained 
her B.S. in Math/CS at Yale University, her M.S. and Ph.D. in CS at Brown 
University,