Complexity of Langton's ant
From MaRDI portal
Publication:1348376
DOI10.1016/S0166-218X(00)00334-6zbMath1050.68047arXivnlin/0306022WikidataQ56115563 ScholiaQ56115563MaRDI QIDQ1348376
Eric Goles Chacc, Andrés Moreira, Anahí Gajardo
Publication date: 15 May 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/nlin/0306022
Analysis of algorithms and problem complexity (68Q25) Neural networks for/in biological studies, artificial life and related topics (92B20) Cellular automata (computational aspects) (68Q80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
How random is spatiotemporal chaos of Langton's ant? ⋮ The Complexity of Small Universal Turing Machines: A Survey ⋮ Dynamics of a class of ants on a one-dimensional lattice ⋮ Busy beaver machines and the observant otter heuristic (or how to tame dreadful dragons) ⋮ The robot cleans up ⋮ The robot crawler graph process ⋮ About non-monotony in Boolean automata networks ⋮ Kadanoff sand pile model. Avalanche structure and wave shape ⋮ On Goles' universal machines: a computational point of view ⋮ On time-symmetry in cellular automata ⋮ Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard ⋮ Strong emergence of wave patterns on Kadanoff sandpiles ⋮ On the emergence of regularities on one-dimensional decreasing sandpiles ⋮ Casse-Briques ⋮ A pseudo-random network mobile automaton with linear growth ⋮ Eric Goles ⋮ An extended strange planet protocol
Cites Work