Complexity of Langton's ant

A. Gajardo, A. Moreira, E. Goles

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

42 Citas (Scopus)

Resumen

The virtual ant introduced by Langton [Physica D 22 (1986) 120] 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.

Idioma originalInglés
Páginas (desde-hasta)41-50
Número de páginas10
PublicaciónDiscrete Applied Mathematics
Volumen117
N.º1-3
DOI
EstadoPublicada - 15 mar. 2002
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'Complexity of Langton's ant'. En conjunto forman una huella única.

Citar esto