Intractable problems in reversible cellular automata

DOI10.1007/BF00669293MaRDI QIDQ1104752zbMATH OpenFDO

Authors Farrokh Vatan

Publication date 1988

Published in International Journal of Theoretical Physics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00669293

zbMATH Keywords

billiard balldistribution of gas moleculesPSPACE-completereversible cellular automaton

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80) Compressible fluids and gas dynamics (76N99)

Review text

The billiard ball model, a classical mechanical system in which all parameters are real variables, can perform all digital computations. An eight-state, 11-neighbor reversible cellular automaton (an entirely discrete system in which all parameters are integer variables) can simulate this model. One of the natural problems for this system is to determine the shape of a container so that the initial specific distribution of gas molecules eventually leads to a predetermined distribution. This problem is PSPACE-complete. Related intractable and decidable problems are discussed as well.

Recommendations

• Reversibility and surjectivity problems of cellular automata
• scientific article; zbMATH DE number 4058875
• Reversibility of 2D cellular automata is undecidable
• scientific article; zbMATH DE number 1775519
• On the structure of the set of reversible cellular automata

Cites work

• A Universal Four-State Cellular Computer
• Computation and construction universality of reversible cellular automata
• Conservative logic
• scientific article; zbMATH DE number 3898247 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3692653 (Why is no real title available?)
• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• On reversibility in cellular automata
• Tesselations with local transformations

Cited in

(3)

• Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard
• scientific article; zbMATH DE number 1775519 (Why is no real title available?)
• A random NP-complete problem for inversion of 2D cellular automata

This page was built for publication: Intractable problems in reversible cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104752)