Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard
type: Item
instance of: scholarly article
title: Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard
zbMATH Open document ID: 1461.68126
author: Tatsuie Tsukiji
author: Takeo Hagiwara
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 37B15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7042094
zbMATH Keywords: cellular automata
zbMATH Keywords: computational complexity
zbMATH Keywords: Langton's ant
zbMATH Keywords: Lorentz lattice gas
zbMATH Keywords: PSPACE-hardness
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a4010001
OpenAlex ID: W2154560238
cites work: Q4398784
cites work: Q3137260
cites work: Recurrence properties of Lorentz lattice gas cellular automata
cites work: Diffusion in Lorentz lattice gas cellular automata: the honeycomb and quasi-lattices compared with the square and triangular lattices
cites work: Rotators, periodicity, and absence of diffusion in cyclic cellular automata
cites work: Complexity of Langton's ant
cites work: Q4198056
DOI: 10.3390/A4010001
description: scientific article; zbMATH DE number 7042094