Persistent Turing machines as a model of interactive computation.

*(English)*Zbl 0961.68048
Schewe, Klaus-Dieter (ed.) et al., Foundations of information and knowledge systems. 1st international symposium, FoIKS 2000, Burg, Germany, February 14-17, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1762, 116-135 (2000).

Summary: 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 by P. Wegner [Theor. Comput. Sci. 192, No. 2, 315-351 (1998; Zbl 0897.68041)] 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.

For the entire collection see [Zbl 0933.00048].

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 by P. Wegner [Theor. Comput. Sci. 192, No. 2, 315-351 (1998; Zbl 0897.68041)] 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.

For the entire collection see [Zbl 0933.00048].

##### MSC:

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |