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.