Speaker: David Keil
Day:  Wednesday, 10/5/2005
Room: ITE 336
Time: 3:30pm
Title: Interaction, Direct and Indirect

Abstract:

Persistent Turing Machines (PTMs) are a new way of interpreting
Turing-machine computation, based on dynamic stream semantics. A PTM
is a Turing machine that performs an infinite sequence of Turing
machine computations that each read from an I/O tape and write back to
the tape. The PTM has an additional, persistent worktape, which
retains its content from one TM computation to the next. It is shown
that the class of PTMs is isomorphic to a general class of effective
transition systems called interactive transition systems; and that
PTMs without persistence (amnesic PTMs) are less expressive than PTMs.
As an analogue of the Church-Turing hypothesis, which relates Turing
machines to algorithmic computation, it is hypothesized that PTMs
capture the intuitive notion of sequential interactive computation.

Related to sequential interaction (modeled by PTMs) is multistream
interaction, which involves both direct (targeted) and indirect
(anonymous) communication. A major challenge for multiagent systems
research is to break out of the restricted framework that limits the
environment to the role of message transport. Current modeling of
concurrency uses a strictly message-passing notion of interaction. We
categorize environments along two dimensions: persistent versus
amnesic, and dynamic versus static. In dynamic persistent
environments, indirect interaction may occur. We formally define this
and show that it is essential to the power of multiagent systems. To
support research in multiagent systems and their environments, new
models are required that explicitly represent indirect interaction via
the environment.

 The research in indirect interaction is joint work with Dina Goldin.

 References:

 Dina Goldin, Scott Smolka, Paul Attie, Elaine Sonderegger.
 Turing Machines, Transition Systems, and Interaction.
 Information and Computation Journal, Volume 194, Issue 2, Nov. 2004
 (http://www.cse.uconn.edu/~dqg/papers/its.pdf)

David Keil, Dina Goldin. Adaptation and evolution in dynamic
 persistent environments. Presented at FInCo2005, Edinburgh, April
 2005.  (http://www.engr.uconn.edu/~dqg/papers/finco05_dpe.pdf)