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

DOI10.3390/A4010001zbMATH Open1461.68126OpenAlexW2154560238MaRDI QIDQ1736474FDOQ1736474

Authors: Tatsuie Tsukiji, Takeo Hagiwara 

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

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

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

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)

Cites Work

• Title not available (Why is that?)
• Complexity of Langton's ant
• Rotators, periodicity, and absence of diffusion in cyclic cellular automata
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Complexity of Langton's ant
• Title not available (Why is that?)
• PSPACE-completeness of reversible deterministic systems

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)