Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard

DOI10.3390/A4010001MaRDI QIDQ1736474zbMATHOpenAlexFDO

Authors Tatsuie Tsukiji, Takeo Hagiwara

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a4010001

zbMATH Keywords

computational complexitycellular automataLangton's antLorentz lattice gasPSPACE-hardness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Recommendations

• Complexity of Langton's ant
• scientific article; zbMATH DE number 1689044
• Langton's flies
• Nontrivial turmites are Turing-universal
• Intractable problems in reversible cellular automata

Cites work

• scientific article; zbMATH DE number 426410 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1178990 (Why is no real title available?)
• Complexity of Langton's ant
• Diffusion in Lorentz lattice gas cellular automata: the honeycomb and quasi-lattices compared with the square and triangular lattices
• Recurrence properties of Lorentz lattice gas cellular automata
• Rotators, periodicity, and absence of diffusion in cyclic cellular automata

Cited in

(3)

• Complexity of Langton's ant
• PSPACE-completeness of reversible deterministic systems
• scientific article; zbMATH DE number 1689044 (Why is no real title available?)

This page was built for publication: Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard

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