Tech Report CS-98-07

Persistence as a Form of Interaction

Abstract:

D. Goldin, Univ. of Massachusetts - Boston P. Wegner, Brown University

This paper establishes a relation between {\em interaction} and {\em persistence}. Interactive computation is characterized by Interaction Machines (IMs), with a restricted subclass of {\em Sequential Interaction Machines} (SIMs) controlled by a single sequential stream of interactions, modeling transducers and simple data abstractions.

{\em Persistent Turing Machines} (PTMs) are introduced by extending Turing Machines (TMs) with a persistent working tape. It is shown that SIMs and PTMs are expressively equivalent but more expressive than TMs where, following Milner, {\em expressiveness} is defined in terms of observerability of system behavior.

This work is part of a larger effort towards a more comprehensive formalization of interactive computation, with the aim of characterizing empirical computation by interaction.

(complete text in pdf or gzipped postscript)