%0 Journal Article
%T Recognizing the Repeatable Configurations of Time-Reversible Generalized LangtonĄ¯s Ant Is PSPACE-Hard
%A Tatsuie Tsukiji
%A Takeo Hagiwara
%J Algorithms
%D 2011
%I MDPI AG
%R 10.3390/a4010001
%X Chris Langton proposed a model of an artificial life that he named Ą°antĄą: an agent- called ant- that is over a square of a grid moves by turning to the left (or right) accordingly to black (or white) color of the square where it is heading, and the square then reverses its color. Bunimovich and Troubetzkoy proved that an antĄ¯s trajectory is always unbounded, or equivalently, there exists no repeatable configuration of the antĄ¯s system. On the other hand, by introducing a new type of color where the ant goes straight ahead and the color never changes, repeatable configurations are known to exist. In this paper, we prove that determining whether a given finite configuration of generalized LangtonĄ¯s ant is repeatable or not is PSPACE-hard. We also prove the PSPACE-hardness of the antĄ¯s problem on a hexagonal grid.
%K cellular automata
%K computational complexity
%K LangtonĄ¯s ant
%K Lorentz lattice gas
%K PSPACE-hard
%U http://www.mdpi.com/1999-4893/4/1/1