Complexity of Langton's ant

A. Gajardo; A. Moreira; E. Goles

doi:10.1016/S0166-218X(00)00334-6

Complexity of Langton's ant

A. Gajardo, A. Moreira, E. Goles

Producción científica: Contribución a una revista › Artículo › revisión exhaustiva

44 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 original	Inglés
Páginas (desde-hasta)	41-50
Número de páginas	10
Publicación	Discrete Applied Mathematics
Volumen	117
N.º	1-3
DOI	https://doi.org/10.1016/S0166-218X(00)00334-6
Estado	Publicada - 15 mar. 2002
Publicado de forma externa	Sí

Acceder al documento

10.1016/S0166-218X(00)00334-6

Citar esto

@article{5efd8ff862184a54b4ab725ccf80c79c,

title = "Complexity of Langton's ant",

abstract = "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.",

keywords = "Artificial life, Complexity, Universality, Virtual ant",

author = "A. Gajardo and A. Moreira and E. Goles",

year = "2002",

month = mar,

day = "15",

doi = "10.1016/S0166-218X(00)00334-6",

language = "English",

volume = "117",

pages = "41--50",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Complexity of Langton's ant

AU - Gajardo, A.

AU - Moreira, A.

AU - Goles, E.

PY - 2002/3/15

Y1 - 2002/3/15

N2 - 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.

AB - 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.

KW - Artificial life

KW - Complexity

KW - Universality

KW - Virtual ant

UR - http://www.scopus.com/inward/record.url?scp=84867959134&partnerID=8YFLogxK

U2 - 10.1016/S0166-218X(00)00334-6

DO - 10.1016/S0166-218X(00)00334-6

M3 - Article

AN - SCOPUS:84867959134

SN - 0166-218X

VL - 117

SP - 41

EP - 50

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

Complexity of Langton's ant

Resumen

Acceder al documento

Huella

Citar esto