Complexity of Langton's ant

A. Gajardo, A. Moreira, E. Goles

Research output: Contribution to journalArticlepeer-review

43 Scopus citations


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 languageEnglish
Pages (from-to)41-50
Number of pages10
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - 15 Mar 2002
Externally publishedYes


  • Artificial life
  • Complexity
  • Universality
  • Virtual ant


Dive into the research topics of 'Complexity of Langton's ant'. Together they form a unique fingerprint.

Cite this