Intractable problems in reversible cellular automata

DOI10.1007/BF00669293zbMath0647.68055MaRDI QIDQ1104752

Farrokh Vatan

Publication date: 1988

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

zbMATH Keywords

PSPACE-completereversible cellular automatonbilliard balldistribution of gas molecules

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conservative logic
• On reversibility in cellular automata
• Computation and construction universality of reversible cellular automata
• Tesselations with local transformations
• Irreversibility and Heat Generation in the Computing Process
• A Universal Four-State Cellular Computer
• Logical Reversibility of Computation