Object-transactional models of programs in algorithmic languages

This paper is devoted to the issue of representability of programs written in algorithmic languages using formalisms based on the idea of using marginal partially transactional memory, including a single transactional cell and many ordinary cells. It is assumed that such formalisms are based on the concept of a network of objects representing both the main and auxiliary elements of the solving problem. Objects function in memory of the specified type, executing methods containing exclusively branching code devoid of cycles. Cycles in this approach are replaced by multiple special object network renegotiation, similar to that implemented in classical transactional memory. Based on the most general ideas about the process of solving a problem in a certain subject area, the concept of an object-transactional model is introduced for the first time and their basic properties are formulated. The methods of discrete mathematics and the theory of algorithms are used in the formulation of the structure and basic principles of the functioning of object-transactional models. The concept of marginal partially transactional memory containing a single transactional cell with a special agreement is introduced. The features of matching such memory in the context of the proposed models are described. A hypothesis is put forward about the feasibility of arbitrary algorithms using object-transactional models. The basic principles of the functioning of such models are described, and their basic properties are formulated. The concepts of marginal non-parallel and parallel models are introduced. It is proved that the limiting nonparallel model is capable of executing an arbitrary Turing-solvable algorithm. It is proved that the limiting parallel model of K+2 nodes is equivalent to a system of K parallel running Turing machines and, accordingly, is capable of executing an arbitrary Turing-solvable algorithm implying the presence of K parallel branches. Thus, the hypothesis put forward in the paper on the feasibility of arbitrary algorithms has been proved.

sequential algorithm, program's model, transactional memory, special reconciliation, limit theorems, object-transaction model, Turing machine, theory, parallel algorithm, feasibility of algorithms