Modeling Interaction with Persistent Turing Machines

                                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 "algorithmic" models 
of computation which transform a predefined input into output.  Though 
interaction is an intuitively obvious idea, there has been no domain-
independent formalization of interactive models of computation.  In this
talk, we explore fundamental models of interaction, relating them to the
notion of persistence.

Persistent Turing Machines (PTMs) are multitape TMs where the internal tape
is persistent between TM computations.  We discuss the stream-based
semantics of PTM computations, using PTMs as a model for sequential
interaction.  We formalize interactive computation by shifting from 
inductive (linear) to coinductive (circular) methods for definition and 
reasoning.  We formulate observation-based notions of system equivalence 
and computational expressiveness, and apply them to demonstrate that 
PTMs are more powerful than Turing machines.

-------------------------------------------------------------------


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.