Reversible computation in nature inspired rule-based systems
- PDF / 1,283,112 Bytes
- 9 Pages / 595.276 x 790.866 pts Page_size
- 92 Downloads / 165 Views
REGULAR PAPER
Reversible computation in nature inspired rule‑based systems Bogdan Aman1,2 · Gabriel Ciobanu1,2 Received: 15 June 2020 / Accepted: 1 October 2020 © Springer Nature Singapore Pte Ltd. 2020
Abstract Since reversibility is an inherent property of many natural phenomena, it makes sense to investigate reversibility in natural computing. More exactly, to study reversible computation in rule-based systems inspired by living cells. Thus, we consider systems working with rules over multisets of objects which are evolving in a maximal parallel manner. After defining what reversibility means in these rule-based systems, we explore their properties that are fully reversible. Some specific properties for reversible computation are presented. Keywords Reversibility · Bio-inspired computing · Maximal parallelism
1 Introduction Reversibility means the capability of a system to evolve both forward and backward. Reversibility is presented early in school when we learn about the chemical reactions; it is denoted by double arrows or bidirectional harpoons. Reversibility appears also in molecular biology, where each step of a catalytic cycle must be reversible; forward and reverse reactions must pass through the same transition state. In physics, the microscopic laws are reversible in the sense that are invariant under time-reversal. How does reversibility appear in computer science? A first step was done by Landauer in 1961 indicating the lower theoretical limit for energy consumption of computation, result known as Landauer’s Principle [20]. This physical principle is used in 1973 by Bennett to reveal the relation between reversibility in physics and reversibility in computing [5]. Then, Feynman presented reversible computing machines from the standpoint of physics in his course on computation at Caltech [16]. Later, Bennett studied the reversible computing from a thermodynamic viewpoint [6]. Thus, for a long time much consideration has been given * Gabriel Ciobanu [email protected] Bogdan Aman [email protected]‑is.ro 1
Romanian Academy, Institute of Computer Science, Iasi, Romania
Alexandru Ioan Cuza University of Iaşi, Iasi, Romania
2
to the reversible computing machines. Several aspects of reversible computing are presented now together in [22], including reversible logic, reversible Turing machines and reversible cellular automata. It is worth noting that ‘computing’ refers to machines performing calculations automatically; on the other hand, ‘computation’ is the act of computing. In this paper we deal with the reversible computation paradigm, in which the standard forwards-only mode of computation is extended with the ability to execute in reverse. This extension allows to execute backward computations as naturally as executing forward computations. Understanding reversible computation could lead to design of novel software systems able to enhance the traditional computation with reversibility [29]. Thus, the potential benefits would include new conceptual ideas and frameworks, new p
Data Loading...
