It is commonly recognized that today's computing applications, such as
web services, intelligent agents, operating systems, and graphical
user interfaces, cannot be modeled by Turing machines and algorithms,
which view computation as a closed box transformation of inputs to
outputs.
According to the interactive view of computation, communication
(input/output) happens during the computation, not before or after it.
This approach, distinct from either the theory of computation or
concurrency theory, represents a paradigm shift that changes our
understanding of what computation is and how it is modeled, promising to
bridge these two fields. It had been conjectured (Wegner 1997) that
"interaction is more powerful than algorithms".
We present one model of interactive computation, Persistent Turing
Machines (PTMs). PTMs extend Turing machines with dynamic streams and
persistence to capture sequential interaction, which is a limited form
of concurrency. They allow us to prove Wegner's conjecture and to
formulate the Sequential Interaction Thesis, going beyond the
expressiveness of the Church-Turing thesis.
The result that interaction machines are more expressive than Turing
machines seems to fly in the face of accepted dogma. In particular, the
Church-Turing thesis is commonly interpreted to imply that Turing
machines model all computation. We conclude by discussing the historical
reasons for this common, but incorrect, interpretation.
Speaker Bio
Dina Q. Goldin is a faculty member in Computer Science & Engineering at
the University of Connecticut and an adjunct faculty member in Computer
Science at Brown University. Dr. Goldin obtained her B.S. in Mathematics
and Computer Science at Yale University, and her M.S. and Ph.D. in
Computer Science at Brown University. Her current topics of research are
models of interaction and data models and query languages.