Tech Report CS-98-07
Persistence as a Form of Interaction
D. Goldin and P. Wegner
July 1998
Abstract:
D. Goldin, Univ. of Massachusetts - Boston
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)