{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:27:50Z","timestamp":1760239670192,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2020,12,16]],"date-time":"2020-12-16T00:00:00Z","timestamp":1608076800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Langton\u2019s ant is a deterministic cellular automaton studied in many fields, artificial life, computational complexity, cryptography, emergent dynamics, Lorents lattice gas, and so forth, motivated by the hardness of predicting the ant\u2019s macroscopic behavior from an initial microscopic configuration. Gajardo, Moreira, and Goles (2002) proved that Langton\u2019s ant is PTIME -hard for reachability. On a twisted torus, we demonstrate that it is PSPACE hard to determine whether the ant will ever visit almost all vertices or nearly none of them.<\/jats:p>","DOI":"10.3390\/a13120344","type":"journal-article","created":{"date-parts":[[2020,12,16]],"date-time":"2020-12-16T09:21:15Z","timestamp":1608110475000},"page":"344","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Hardness of Approximation for Langton\u2019s Ant on a Twisted Torus"],"prefix":"10.3390","volume":"13","author":[{"given":"Takeo","family":"Hagiwara","sequence":"first","affiliation":[{"name":"Department of Science and Engineering, Tokyo Denki University, Tokyo 120-8551, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7997-6633","authenticated-orcid":false,"given":"Tatsuie","family":"Tsukiji","sequence":"additional","affiliation":[{"name":"Graduate School of Advanced Science and Technology, Tokyo Denki University, Tokyo 120-8551, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/0167-2789(86)90237-X","article-title":"Studying artificial life with cellular automata","volume":"22","author":"Langton","year":"1986","journal-title":"Phys. Nonlinear Phenom."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1002\/cplx.1042","article-title":"Dynamical behavior and complexity of Langton\u2019s ant","volume":"6","author":"Moreira","year":"2001","journal-title":"Complexity"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Hamann, H., Schmickl, T., and Crailsheim, K. (2011, January 11\u201315). Thermodynamics of emergence: Langton\u2019s ant meets Boltzmann. Proceedings of the 2011 IEEE Symposium on Artificial Life (ALIFE), Paris, France.","DOI":"10.1109\/ALIFE.2011.5954660"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Rao, K.N., Divya, M., Pallavi, M., and Priyanka, B.N. (2015). Modeling Artificial Life: A Cellular Automata Approach. Computational Intelligence Techniques for Comparative Genomics, Springer.","DOI":"10.1007\/978-981-287-338-5_6"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Schiff, J.L. (2020). Order from Chaos. The Mathematical Universe, Springer.","DOI":"10.1007\/978-3-030-50649-0"},{"key":"ref_6","unstructured":"Gale, D., Propp, J., Sutherland, S., and Troubetzkoy, S. (1995). Further travels with my ant. arXiv."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/j.tcs.2004.03.012","article-title":"Dynamics of a class of ants on a one-dimensional lattice","volume":"322","author":"Gajardo","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"ref_8","unstructured":"Gale, D. (2012). Tracking the Automatic Ant: And Other Mathematical Explorations, Springer Science & Business Media."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1007\/BF01017981","article-title":"Diffusion and propagation in triangular Lorentz lattice gas cellular automata","volume":"62","author":"Kong","year":"1991","journal-title":"J. Stat. Phys."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF01049035","article-title":"Recurrence properties of Lorentz lattice gas cellular automata","volume":"67","author":"Bunimovich","year":"1992","journal-title":"J. Stat. Phys."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.physa.2016.08.077","article-title":"Equivalence of deterministic walks on regular lattices on the plane","volume":"466","author":"Rechtman","year":"2017","journal-title":"Phys. Stat. Mech. Its Appl."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1023\/A:1004611208149","article-title":"Propagation and organization in lattice random media","volume":"97","author":"Grosfils","year":"1999","journal-title":"J. Stat. Phys."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1023\/A:1026581213671","article-title":"How fast does Langton\u2019s ant move?","volume":"102","author":"Boon","year":"2001","journal-title":"J. Stat. Phys."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0166-218X(00)00334-6","article-title":"Complexity of Langton\u2019s ant","volume":"117","author":"Gajardo","year":"2002","journal-title":"Discret. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3390\/a4010001","article-title":"Recognizing the repeatable configurations of time-reversible generalized Langton\u2019s ant is PSPACE-hard","volume":"4","author":"Tsukiji","year":"2011","journal-title":"Algorithms"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1034","DOI":"10.1587\/transfun.E99.A.1034","article-title":"Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata","volume":"99","author":"Hagiwara","year":"2016","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1063\/1.1503664","article-title":"Systems with Emergent Dynamics","volume":"Volume 627","author":"Stewart","year":"2002","journal-title":"AIP Conference Proceedings"},{"key":"ref_18","unstructured":"Heiney, K., Tufte, G., and Nichele, S. (2020). On Artificial Life and Emergent Computation in Physical Substrates. arXiv."},{"key":"ref_19","unstructured":"Hosseini, S.M., Karimi, H., and Jahan, M.V. (2011, January 18\u201321). From Complexity to Random Behaviors; Generate Random Numbers by Confusion in Cellular Automata State\u2019s. Proceedings of the International Conference on Scientific Computing (CSC), Las Vegas, NV, USA."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1109\/MMUL.2011.54","article-title":"Digital image scrambling using 2D cellular automata","volume":"19","author":"Mahafzah","year":"2012","journal-title":"IEEE Multimed."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1515\/jamsi-2015-0008","article-title":"How Random Is Spatiotemporal Chaos of Langton\u2019s Ant?","volume":"11","year":"2015","journal-title":"J. Appl. Math. Stat. Inform."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2449","DOI":"10.1007\/s11071-014-1824-0","article-title":"A novel image encryption scheme using chaos and Langton\u2019s Ant cellular automaton","volume":"79","author":"Wang","year":"2015","journal-title":"Nonlinear Dyn."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"e52","DOI":"10.1002\/spy2.52","article-title":"Linear-feedback shift register-based multi-ant cellular automation and chaotic map-based image encryption","volume":"1","author":"Dey","year":"2018","journal-title":"Secur. Priv."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Arora, S., and Barak, B. (2009). Computational Complexity: A Modern Approach, Cambridge University Press.","DOI":"10.1017\/CBO9780511804090"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"JACM"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF01044230","article-title":"Driven nonequilibrium lattice systems with shifted periodic boundary conditions","volume":"56","author":"Leung","year":"1989","journal-title":"J. Stat. Phys."},{"key":"ref_27","unstructured":"Anderson, M.J. (1998). Cooperative Behavior in Driven Lattice Systems with Shifted Periodic Boundary Conditions. [Ph.D. Thesis, Virginia Tech]."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02187706","article-title":"Rectilinear planar layouts and bipolar orientations of planar graphs","volume":"1","author":"Rosenstiehl","year":"1986","journal-title":"Discret. Comput. Geom."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02187705","article-title":"A unified approach to visibility representations of planar graphs","volume":"1","author":"Tamassia","year":"1986","journal-title":"Discret. Comput. Geom."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/344\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:45:38Z","timestamp":1760179538000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/344"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,16]]},"references-count":29,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2020,12]]}},"alternative-id":["a13120344"],"URL":"https:\/\/doi.org\/10.3390\/a13120344","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,12,16]]}}}