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

Research output: Contribution to journal › Article › peer-review

44 Scopus citations

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.

Original language	English
Pages (from-to)	41-50
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	117
Issue number	1-3
DOIs	https://doi.org/10.1016/S0166-218X(00)00334-6
State	Published - 15 Mar 2002
Externally published	Yes

Keywords

Artificial life
Complexity
Universality
Virtual ant

Access to Document

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

Cite this

@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

Abstract

Keywords

Access to Document

Fingerprint

Cite this