Persistent Turing Machines as a Model of Interactive Computation

Persistent Turing Machines (PTMs) are multitape machines with a persistent worktape preserved between interactions, whose inputs and outputs are dynamically generated streams of tokens (strings). They are a minimal extension of Turing Machines (TMs) that express interactive behavior. They provide a natural model for sequential interactive computation such as single-user databases and intelligent agents.

PTM behavior is characterized observationally, by input-output streams; the notions of equivalence and expressiveness for PTMs are defined relative to its behavior. Four different models of PTM behavior are examined: language-based, automaton-based, function-based, and environment-based. A number of special subclasses of PTMs are identified; several expressiveness results are obtained, both for the general class of all PTMs and for the special subclasses, proving the conjecture in We2 that interactive computing devices are more expressive than TMs.

The methods and tools for formalizing PTM computation developed in this paper can serve as a basis for a more comprehensive theory of interactive computation.