According to the interactive view of computation, communication happens during the computation, not before or after it. This approach, distinct from concurrency theory and the theory of computation, represents a paradigm shift that changes our understanding of what is computation and how it is modeled. Interaction machines extend Turing machines with interaction to capture the behavior of concurrent systems, promising to bridge these two fields.
In the November 2004 issue of "Information and Computation", the Principal Investigator and others presented persistent Turing machines (PTMs), an extension to the Turing machine model that is both interactive and persistent. A PTM is a nondeterministic 3-tape Turing machine with a read-only input tape, a read/write work tape, and a write-only output tape. A PTM performs persistent computations in the sense that a notion of ``memory'' (work-tape contents) is maintained from one interaction (computation) step to the next. PTM computations are shown to be more expressive than Turing machine computations. As an analogue of the Church-Turing Thesis, it is hypothesized that PTMs capture the intuitive notion of sequential interactive computation; that is, any sequential interactive computation can be performed by a persistent Turing machine.
Intellectual Merit. PTMs capture sequential interaction, which is a limited form of concurrency. This proposal seeks to build on the PTM work, by developing the Theory of Sequential Interactive Computation. In particular, we believe that Sequential Interactive Computation is as robust a notion of computation as the traditional one based on Turing machines, admitting notions analogous to computational complexity, logic, and recursive functions.
Specifically, we propose to develop complexity measures for PTM computations. For each associated PTM complexity class, we plan to identify sample interactive computations that characterize the class and determine if any of the identified computations are complete for their class. In this manner, we will round out the theory of sequential interactive computation, corresponding to PTM computations, by supplementing its automata-theoretic and transition-system approaches with a complexity-based approach.
Broader Impact. It is time to recognize that today's computing applications, such as web services, intelligent agents, operating systems, and graphical user interfaces, cannot be modeled by Turing machines; alternative models are needed.
The resulting theory of interactive computation will bridge the gap between the historically disjoint fields of the theory of computation and concurrency theory. By identifying the salient features of interaction, our work will enable interactive applications to be written more quickly and more reliably.
Our findings will be submitted for publication in a timely fashion and presented in seminars in the United States and abroad. Graduate and undergraduate students at the University of Connecticut will be engaged in the research activity.
