Complexity of Langton's ant

DOI10.1016/S0166-218X(00)00334-6MaRDI QIDQ1348376zbMATH OpenDBLPWikidataFDO

Authors Anahí Gajardo, Andrés Moreira, Eric Goles

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

zbMATH Keywords

P-hardness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80) Neural networks for/in biological studies, artificial life and related topics (92B20)

Abstract: The virtual ant introduced by C. Langton has an interesting behavior, which has been studied in several contexts. Here we give a construction to calculate any boolean circuit with the trajectory of a single ant. This proves the P-hardness of the system and implies, through the simulation of one dimensional cellular automata and Turing machines, the universality of the ant and the undecidability of some problems associated to it.

Recommendations

• Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard
• scientific article; zbMATH DE number 1689044
• Nontrivial turmites are Turing-universal
• scientific article; zbMATH DE number 1241089
• How random is spatiotemporal chaos of Langton's ant?

Cites work

• Cellular automata model for the diffusion equation
• Further travels with my ant
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1178990 (Why is no real title available?)
• Propagation and organization in lattice random media
• Recurrence properties of Lorentz lattice gas cellular automata
• Rotators, periodicity, and absence of diffusion in cyclic cellular automata

Cited in

(21)

• The robot crawler graph process
• Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard
• Dynamics of a class of ants on a one-dimensional lattice
• On the emergence of regularities on one-dimensional decreasing sandpiles
• Eric Goles
• An extended strange planet protocol
• How random is spatiotemporal chaos of Langton's ant?
• scientific article; zbMATH DE number 1689044 (Why is no real title available?)
• The Complexity of Small Universal Turing Machines: A Survey
• Busy beaver machines and the observant otter heuristic (or how to tame dreadful dragons)
• 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
• scientific article; zbMATH DE number 2046040 (Why is no real title available?)
• Nontrivial turmites are Turing-universal
• Strong emergence of wave patterns on Kadanoff sandpiles
• Breakout
• How fast does Langton's ant move?
• The robot cleans up
• A pseudo-random network mobile automaton with linear growth

This page was built for publication: Complexity of Langton's ant

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