Reversibility of 2D cellular automata is undecidable
From MaRDI portal
Publication:807043
DOI10.1016/0167-2789(90)90195-UzbMath0729.68058OpenAlexW4254434123WikidataQ55871046 ScholiaQ55871046MaRDI QIDQ807043
Publication date: 1990
Published in: Physica D (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0167-2789(90)90195-u
Related Items (61)
Self-organising behaviour in the presence of negative externalities: a conceptual model of commuter choice ⋮ Efficient exhaustive listings of reversible one dimensional cellular automata ⋮ How to turn a second-order cellular automaton into a lattice gas: a new inversion scheme ⋮ Intrinsic universality of a 1-dimensional reversible Cellular Automaton ⋮ Inversion of 2D cellular automata: Some complexity results ⋮ The surjectivity problem for 2D cellular automata ⋮ Reversible Causal Graph Dynamics ⋮ Wavefront cellular learning automata ⋮ Ternary reversible number-conserving cellular automata are trivial ⋮ An order-preserving property of additive invariants for Takesue-type reversible cellular automata ⋮ Reversibility problem of multidimensional finite cellular automata ⋮ Reversible cellular automaton able to simulate any other reversible one using partitioning automata ⋮ Cellular automata between sofic tree shifts ⋮ Two-dimensional rotation-symmetric number-conserving cellular automata ⋮ The Entropy and Reversibility of Cellular Automata on Cayley Tree ⋮ Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over \(\mathbb{Z}_p\) ⋮ Structure and Reversibility of 2D von Neumann Cellular Automata Over Triangular Lattice ⋮ An overview of quantum cellular automata ⋮ Reversible causal graph dynamics: invertibility, block representation, vertex-preservation ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage ⋮ Structure and reversibility of 2D hexagonal cellular automata ⋮ Efficient enumeration of three-state two-dimensional number-conserving cellular automata ⋮ On time-symmetry in cellular automata ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ 2D Triangular von Neumann Cellular Automata with Periodic Boundary ⋮ A two-layer representation of four-state reversible number-conserving 2D cellular automata ⋮ A Random NP-complete problem for inversion of 2D cellular automata ⋮ Snakes and Cellular Automata: Reductions and Inseparability Results ⋮ Emergence of universal global behavior from reversible local transitions in asynchronous systems ⋮ Nondeterministic cellular automata ⋮ Reversibility of general 1D linear cellular automata over the binary field \(\mathbb{Z}_2\) under null boundary conditions ⋮ Reversibility of linear cellular automata on Cayley trees with periodic boundary condition ⋮ Theory of cellular automata: a survey ⋮ On the structure of the set of reversible cellular automata ⋮ Garden of Eden configurations for 2-D cellular automata with rule 2460 N ⋮ When-and how-can a cellular automaton be rewritten as a lattice gas? ⋮ Invertible linear cellular automata over \(\mathbb{Z}_m\): Algorithmic and dynamical aspects ⋮ PERIODIC CONFIGURATIONS OF SUBSHIFTS ON GROUPS ⋮ Cellular automaton growth on \(\mathbb{Z}^2\): Theorems, examples, and problems ⋮ Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumeration ⋮ ON THE REVERSIBILITY OF 150 WOLFRAM CELLULAR AUTOMATA ⋮ Surprising Areas in the Quest for Small Universal Devices ⋮ Reversibility of non-saturated linear cellular automata on finite triangular grids ⋮ CELLULAR LEARNING AUTOMATA BASED DYNAMIC CHANNEL ASSIGNMENT ALGORITHMS ⋮ Some applications of propositional logic to cellular automata ⋮ Reversibility vs Local Creation/Destruction ⋮ A split-and-perturb decomposition of number-conserving cellular automata ⋮ Reversibility of number-conserving 1D cellular automata: unlocking insights into the dynamics for larger state sets ⋮ Two-dimensional cellular automata recognizer ⋮ Graph-theoretical characterization of invertible cellular automata ⋮ REVERSIBILITY ALGORITHMS FOR 3-STATE HEXAGONAL CELLULAR AUTOMATA WITH PERIODIC BOUNDARIES ⋮ Reversible space-time simulation of cellular automata ⋮ Recurrent Misconceptions in the Study of CA Reversibility on Triangular Grids ⋮ CELLULAR AUTOMATA OVER SEMI-DIRECT PRODUCT GROUPS: REDUCTION AND INVERTIBILITY RESULTS ⋮ Decidability and undecidability in cellular automata ⋮ Classifying circular cellular automata ⋮ Invertible cellular automata: A review ⋮ Parallel recognition of rational languages in plane cellular automata ⋮ Reversibility and surjectivity problems of cellular automata ⋮ Replication of spatial patterns with reversible and additive cellular automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reversibility and surjectivity problems of cellular automata
- Undecidability and nonperiodicity for tilings of the plane
- Tesselations with local transformations
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
- The undecidability of the domino problem
This page was built for publication: Reversibility of 2D cellular automata is undecidable
