Reversibility of 2D cellular automata is undecidable
From MaRDI portal
Publication:807043
DOI10.1016/0167-2789(90)90195-UzbMath0729.68058WikidataQ55871046 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
68Q80: Cellular automata (computational aspects)
Related Items
Wavefront cellular learning automata, 2D Triangular von Neumann Cellular Automata with Periodic Boundary, Surprising Areas in the Quest for Small Universal Devices, Reversibility of non-saturated linear cellular automata on finite triangular grids, Intrinsic universality of a 1-dimensional reversible Cellular Automaton, Reversible cellular automaton able to simulate any other reversible one using partitioning automata, The Entropy and Reversibility of Cellular Automata on Cayley Tree, Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage, Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumeration, Reversibility vs Local Creation/Destruction, Structure and Reversibility of 2D von Neumann Cellular Automata Over Triangular Lattice, On the structure of the set of reversible cellular automata, ON THE REVERSIBILITY OF 150 WOLFRAM CELLULAR AUTOMATA, Recurrent Misconceptions in the Study of CA Reversibility on Triangular Grids, Replication of spatial patterns with reversible and additive cellular automata, Two-dimensional rotation-symmetric number-conserving cellular automata, Efficient methods with polynomial complexity to determine the reversibility of general 1D linear cellular automata over \(\mathbb{Z}_p\), 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, Cellular automata between sofic tree shifts, On time-symmetry in cellular automata, Groups, graphs, languages, automata, games and second-order monadic logic, Emergence of universal global behavior from reversible local transitions in asynchronous systems, Nondeterministic cellular automata, An order-preserving property of additive invariants for Takesue-type reversible cellular automata, A Random NP-complete problem for inversion of 2D cellular automata, Classifying circular cellular automata, Invertible cellular automata: A review, Garden of Eden configurations for 2-D cellular automata with rule 2460 N, Invertible linear cellular automata over \(\mathbb{Z}_m\): Algorithmic and dynamical aspects, Cellular automaton growth on \(\mathbb{Z}^2\): Theorems, examples, and problems, Two-dimensional cellular automata recognizer, Reversibility and surjectivity problems of cellular automata, Inversion of 2D cellular automata: Some complexity results, The surjectivity problem for 2D cellular automata, Graph-theoretical characterization of invertible cellular automata, Reversible space-time simulation of cellular automata, Parallel recognition of rational languages in plane 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, 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, 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, Efficient enumeration of three-state two-dimensional number-conserving cellular automata, Reversibility problem of multidimensional finite cellular automata, Structure and reversibility of 2D hexagonal cellular automata, When-and how-can a cellular automaton be rewritten as a lattice gas?, Ternary reversible number-conserving cellular automata are trivial, REVERSIBILITY ALGORITHMS FOR 3-STATE HEXAGONAL CELLULAR AUTOMATA WITH PERIODIC BOUNDARIES, Decidability and undecidability in cellular automata, Snakes and Cellular Automata: Reductions and Inseparability Results, Reversible Causal Graph Dynamics, A two-layer representation of four-state reversible number-conserving 2D cellular automata, CELLULAR LEARNING AUTOMATA BASED DYNAMIC CHANNEL ASSIGNMENT ALGORITHMS, CELLULAR AUTOMATA OVER SEMI-DIRECT PRODUCT GROUPS: REDUCTION AND INVERTIBILITY RESULTS, PERIODIC CONFIGURATIONS OF SUBSHIFTS ON GROUPS, Some applications of propositional logic to cellular automata
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
