Complexity of Langton's ant

Gajardo A.; Moreira, A.; Goles, E.

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. © 2002 Elsevier Science B.V. All rights reserved.

Más información

Título según WOS: Complexity of Langton's ant
Título según SCOPUS: Complexity of Langton's ant
Título de la Revista: DISCRETE APPLIED MATHEMATICS
Volumen: 117
Número: 01-mar
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2002
Página de inicio: 41
Página final: 50
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0166218X00003346
DOI:

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

Notas: ISI, SCOPUS