Simulating reversible computation with reaction systems
- PDF / 1,768,615 Bytes
- 15 Pages / 595.276 x 790.866 pts Page_size
- 41 Downloads / 180 Views
REGULAR PAPER
Simulating reversible computation with reaction systems Attila Bagossy1 · György Vaszil1 Received: 14 March 2020 / Accepted: 19 August 2020 © The Author(s) 2020
Abstract Reaction systems are a formal model of computation providing a framework for investigating biochemical reactions inside living cells. We look at the functioning of these systems as a process producing a series of different possible sets of entities representing states which can be changed by the application of reactions, and we study reversibility and its simulation in this framework. Our goal is to establish an Undo-Redo-Do-like semantics of reversibility with environmental control over the direction of the computation following a so-called no-memory approach, that is, without introducing modifications to the model of reaction systems itself. We first establish requirements the systems must satisfy in order to produce processes consisting of states with unique predecessors, then define reversible reaction systems in terms of reversible interactive processes. For such reversible systems, we also construct simulator systems that can traverse between the states of reversible interactive processes back and forth based on the input of a special “rollback” symbol from the environment. Keywords Reaction Systems · Natural computing · Reversible computing
1 Introduction Natural computing is a research area concerned with computational models which may be either inspired by some natural phenomenon, or designed to help us better understand natural processes in terms of information processing [16, 29]. Reversible computation is a paradigm extending the standard notion of the forwards-only mode of computation with the ability to be executed also in the reverse direction, such that computations can run backwards as naturally as they can run forwards.[20, 22, 30]. In this paper, we study reversibility and its simulation in the framework of reaction systems, a natural computational model by Ehrenfeucht and Rozenberg [12] aiming to provide a formal framework for investigating the biochemical reactions inside living cells. Computation in this model goes forward by applying reactions to a set of entities (called a state), * György Vaszil [email protected] Attila Bagossy [email protected] 1
creating a new set (a new state). The way this model works is also interactive in the sense that each state may also incorporate input, capturing the idea that living cells do not act in isolation but always operate in some environment which may influence their behavior (and thus, the computation). In contrast to previous results, such as those in [5], we aim to investigate how to introduce reversibility in reaction systems without losing its openness (its ability to incorporate input from the enclosing environment), and without making modifications on the model itself. The rest of the paper is organized as follows. In Sect. 2 we discuss the main paradigms concerning the implementation of reversibility in the context of computational mod
Data Loading...
