Complexity of Langton's ant

Authors :: Gajardo, A.
Moreira, A.
Goles, E.
Source :: Discrete Applied Mathematics. Mar2002, Vol. 117 Issue 1-3, p41. 10p.
Publication Year :: 2002
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. [Copyright &y& Elsevier]