Generalized symmetrical Langton's ant problem is PSPACE-complete.
|
Accession number;02A0428168
|
| Title;Generalized symmetrical Langton's ant problem is PSPACE-complete. |
| Author;
YAMAGUCHI EIJI
(Nagoya Univ., Graduate School of Human Informatics, JPN)
TSUKIJI TATSUIE
(Nagoya Univ., Graduate School of Human Informatics, JPN)
|
Journal Title;IEIC Technical Report (Institute of Electronics, Information and Communication Engineers)
|
Journal Code:S0532B
|
ISSN:0913-5685
|
|
VOL.101;NO.708(COMP2001 93-104);PAGE.49-56(2002)
|
| Figure&Table&Reference;FIG.10, REF.4 |
| Pub. Country;Japan |
| Language;Japanese |
| Abstract;Chris Langton proposed a model of an artificial life, named Langton's ant: an ant put on a grid goes by a square, turns left or right according to the state of the square where he is on, and changes its state. Though it is a quite simple definition, the ant's behavior is surprisingly unpredictable. Lots of research showed the computational complexity, the potential and the application of Langton's ant. In this paper, we define a problem of anticipating the ant's behavior under definite conditions, and show it PSPACE-complete. (author abst.) |
|
|
|
Related Articles;
|
|
