Intractable problems in reversible cellular automata

DOI10.1007/BF00669293zbMATH Open0647.68055MaRDI QIDQ1104752FDOQ1104752

Farrokh Vatan

Publication date: 1988

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

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

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

• Conservative logic
• Title not available (Why is that?)
• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• Title not available (Why is that?)
• On reversibility in cellular automata
• Title not available (Why is that?)
• Tesselations with local transformations
• Title not available (Why is that?)
• Computation and construction universality of reversible cellular automata
• A Universal Four-State Cellular Computer

Cited In (2)

• Title not available (Why is that?)
• 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)