Complexity of Langton's ant

A. Gajardo, A. Moreira, E. Goles

Research output: Contribution to journalArticlepeer-review

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

Keywords

  • Artificial life
  • Complexity
  • Universality
  • Virtual ant

Fingerprint

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

Cite this