Reversible computing and cellular automata -- a survey

DOI10.1016/j.tcs.2008.01.041zbMath1145.68036OpenAlexW1998896169MaRDI QIDQ924686

Kenichi Morita

Publication date: 19 May 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.01.041

zbMATH Keywords

reversible Turing machinereversible logic elementreversible cellular automatacomputation-universality

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cellular automata (computational aspects) (68Q80)

Related Items

Reversibility in the higher-order \(\pi\)-calculus ⋮ One-way reversible multi-head finite automata ⋮ Characterization of random fluctuation-based computation in cellular automata ⋮ Reversible top-down syntax analysis ⋮ From reversible programming languages to reversible metalanguages ⋮ On reversible Turing machines and their function universality ⋮ One-Way Reversible Multi-head Finite Automata ⋮ Garbageless Reversible Implementation of Integer Linear Transformations ⋮ Designing nanoscale counter using reversible gate based on quantum-dot cellular automata ⋮ The Degree of Irreversibility in Deterministic Finite Automata ⋮ Aspects of Reversibility for Classical Automata ⋮ How Can We Construct Reversible Machines Out of Reversible Logic Element with Memory? ⋮ Reversible Limited Automata ⋮ Reversible and Irreversible Computations of Deterministic Finite-State Devices ⋮ The complexity of translationally invariant spin chains with low local dimension ⋮ On the image set and reversibility of shift morphisms over discrete alphabets ⋮ Fundamentals of reversible flowchart languages ⋮ Cold dynamics in cellular automata: a tutorial ⋮ Towards a taxonomy for reversible computation approaches ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Asynchronous communicating cellular automata: formalization, robustness and equivalence ⋮ Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage ⋮ Cellular Automata: Descriptional Complexity and Decidability ⋮ Invertible Construction of Decimal-to-Binary Converter Using Reversible Elements ⋮ Logical Gates via Gliders Collisions ⋮ Clean Reversible Simulations of Ranking Binary Trees ⋮ The Computing Power of Determinism and Reversibility in Chemical Reaction Automata ⋮ On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View ⋮ Queue Automata: Foundations and Developments ⋮ Reversible Top-Down Syntax Analysis ⋮ When input-driven pushdown automata meet reversiblity ⋮ Fluctuation-driven computing on number-conserving cellular automata ⋮ Unnamed Item ⋮ CELLULAR AUTOMATON SUPERCOLLIDERS ⋮ Emergence of universal global behavior from reversible local transitions in asynchronous systems ⋮ A class of recursive permutations which is primitive recursive complete ⋮ Reversibility of general 1D linear cellular automata over the binary field \(\mathbb{Z}_2\) under null boundary conditions ⋮ ON 1D REVERSIBLE CELLULAR AUTOMATA WITH REFLECTIVE BOUNDARY OVER THE PRIME FIELD OF ORDER p ⋮ Design of 1-tape 2-symbol reversible Turing machines based on reversible logic elements ⋮ Reversible pushdown automata ⋮ Reversibility of linear cellular automata ⋮ A closed formula for the inverse of a reversible cellular automaton with \((2 R + 1)\)-cyclic rule ⋮ Reversibility of 1D cellular automata with periodic boundary over finite fields \({\mathbb{Z}}_{p}\) ⋮ Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata ⋮ Reversing computation in membrane systems ⋮ Dual P Systems ⋮ Hierarchy and Expansiveness in 2D Subshifts of Finite Type ⋮ General design of reversible sequential machines based on reversible logic elements ⋮ Binary-decision-diagram-based decomposition of Boolean functions into reversible logic elements ⋮ The Degree of Irreversibility in Deterministic Finite Automata ⋮ Real-Time Reversible One-Way Cellular Automata ⋮ Computation in reversible cellular automata

Cites Work

• Firing squad synchronization problem in reversible cellular automata
• Invertible cellular automata: A review
• Conservative logic
• Computation and construction universality of reversible cellular automata
• Injectivity and surjectivity of parallel maps for cellular automata
• Reversibility and surjectivity problems of cellular automata
• Small universal Turing machines
• Universality of a reversible two-counter machine
• Self-reproduction in a reversible cellular space
• A computation-universal two-dimensional 8-state triangular reversible cellular automaton
• Procedures for calculating reversible one-dimensional cellular automata
• Theory of cellular automata: a survey
• Efficient exhaustive listings of reversible one dimensional cellular automata
• Tesselations with local transformations
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• A Universal Reversible Turing Machine
• Small Semi-weakly Universal Turing Machines
• Irreversibility and Heat Generation in the Computing Process
• Time/Space Trade-Offs for Reversible Computation
• Bicontinuous extensions of invertible combinatorial functions
• Condition for injectivity of global maps for tessellation automata
• Surprising Areas in the Quest for Small Universal Devices
• Endomorphisms and automorphisms of the shift dynamical system
• The Garden-of-Eden Theorem for Finite Configurations
• Logical Reversibility of Computation
• Machines, Computations, and Universality
• Four Small Universal Turing Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reversible computing and cellular automata -- a survey