Complexity of Langton's Ant

Simple item page
dc.creatorGajardo, Anahi
dc.creatorMoreira, Andres
dc.creatorGoles, Eric
dc.date2003-06-13
dc.date2003-06-13
dc.date.accessioned2026-07-07T05:34:47Z
dc.date.available2026-07-07T05:34:47Z
dc.descriptionThe 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.
dc.description8 pages, 9 figures. Complements at http://www.dim.uchile.cl/~agajardo/langton
dc.identifierhttps://arxiv.org/abs/nlin/0306022
dc.identifierhttp://arxiv.org/abs/nlin/0306022
dc.identifierFinal version in Discrete Applied Mathematics, Vol. 117, Issue 1-3, pp. 41-50 (2002)
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/80500
dc.subjectCellular Automata and Lattice Gases
dc.titleComplexity of Langton's Ant
dc.typetext

Files

Collections

arXiv