Research On Interactive Computability And Its Topological Approaches

The traditional theory of computability is based on Turing machines. However, contemporary computing goes beyond the capability of Turing machines because of its properties of interaction, infinity, and evolution, among which interaction is fundamental, so it's necessary to establish interactive computability theory, i.e. a theory of computability dedicated to interactive computing.Interaction is defined to be the input and output operations of a system during its computation, and such a system is called an interactive one. Multiple interactive systems constitute a composed system if some interaction mechanism is provided.In one word, the task of interactive computability theory is to determine the computing capability of interactive systems and interaction mechanisms. The task leads to the following four problems: how to formalize interactive computing, what's the measure of the capability of interactive systems and interaction mechanisms, what can and what can't be solved by interactive computing, and how to measure the complexity of interactive computing.With the motivation from VEGA Grid project, this paper is focused on the latter two questions. The main contributions are listed below.1. Sequentialâ…¡-style interactive systems are studied in terms of their computational capabilities. The paradigm ofâ…¡-style interaction is proposed in the project of VEGA Grid, which means through interaction not only data but also the control (i.e. program) of a system can be dynamically modified.â…¡-style interaction may be useful in many scenarios such as service computing and remote coordination. Sequentialâ…¡-style interactive systems are modeled by PRASPs which are RASPs equipped with a persistent memory, and are proved to be equivalent to persistent Turing machines. The contribution to interactive computability theory is that the capability of sequentialâ…¡-style interactive systems is totally determined, while related work mainly focuses on that of sequentialâ… -style interactive systems.2. The capability of interaction product is studied. To reduce services, applications, and infrastructure of grids to basic and simple forms simultaneously, an interaction mechanism, namely interaction product, is designed, a class of finite state automata, namely generalized finite state automata (GFAs), is identified, and it's proved that any Turing machines is equivalent to the interaction product of certain three GFAs. Since both interaction product and GFAs are almost as simple as possible and easy to be implemented, our result has in some...