On the Undecidability of Attractor Properties for Cellular Automata

Issue title: From Physics to Computer Science: to Gianpiero Cattaneo for his 70th birthday

Article type: Research Article

Authors: Di Lena, Pietro | Margara, Luciano

Affiliations: Department of Computer Science, University of Bologna, Mura Anteo Zamboni, 40127 Bologna, Italy. dilena@cs.unibo.it | Department of Computer Science, University of Bologna, Mura Anteo Zamboni, 40127 Bologna, Italy

Note: [] Address for correspondence: Department of Computer Science, University of Bologna, Mura Anteo Zamboni, 40127 Bologna, Italy

Abstract: The attractor properties in Cellular Automata dynamical systems have been extensively investigated and well characterized. We consider here two attractor classification for Cellular Automata and we prove the computational undecidability of some questions related to such classifications.

Keywords: Cellular Automata, Attractors, Computational Undecidability

DOI: 10.3233/FI-2012-641

Journal: Fundamenta Informaticae, vol. 115, no. 1, pp. 75-85, 2012