×

Rice’s theorem for \(\mu \)-limit sets of cellular automata. (English) Zbl 1334.68141

Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-22011-1/pbk). Lecture Notes in Computer Science 6756, 89-100 (2011).
Summary: Cellular automata are a parallel and synchronous computing model, made of infinitely many finite automata updating according to the same local rule. Rice’s theorem states that any nontrivial property over computable functions is undecidable. It has been adapted by J. Kari to limit sets of cellular automata [Theor. Comput. Sci. 127, No. 2, 229–254 (1994; Zbl 0824.68078)], that is the set of configurations that can be reached arbitrarily late. This paper proves a new Rice theorem for \(\mu \)-limit sets, which are sets of configurations often reached arbitrarily late.
For the entire collection see [Zbl 1217.68004].

MSC:

68Q80 Cellular automata (computational aspects)
03B25 Decidability of theories and sets of sentences

Citations:

Zbl 0824.68078
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Boyer, L., Delacourt, M., Sablik, M.: Construction of {\(\mu\)}-limit sets. In: Kari, J. (ed.) JAC 2010, vol. 13, pp. 76–87. TUCS Lecture notes, Turku (2010)
[2] Boyer, L., Poupet, V., Theyssier, G.: On the complexity of limit sets of cellular automata associated with probability measures. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 190–201. Springer, Heidelberg (2006) · Zbl 1132.68494 · doi:10.1007/11821069_17
[3] Delacourt, M., Poupet, V., Sablik, M., Theyssier, G.: Directional dynamics along arbitrary curves in cellular automata. To be Pubished in Theoretical Computer Science (2011) · Zbl 1225.37017
[4] Fredricksen, H., Kessler, I.: Lexicographic compositions and debruijn sequences. Journal of Combinatorial Theory, Series A 22(1), 17–30 (1977) · Zbl 0343.05008 · doi:10.1016/0097-3165(77)90059-0
[5] Guillon, P., Richard, G.: Revisiting the rice theorem of cellular automata. In: Marion, J.Y., Schwentick, T. (eds.) STACS 2010, vol. 5, pp. 441–452. LIPIcs, Schloss Dagstuhl (2010) · Zbl 1230.68152
[6] Hurley, M.: Ergodic aspects of cellular automata. Ergodic Theory and Dynamical Systems 10, 671–685 (1990) · Zbl 0695.58019
[7] Kari, J.: Rice’s theorem for the limit sets of cellular automata. Theoretical Computer Science 127(2), 229–254 (1994) · Zbl 0824.68078 · doi:10.1016/0304-3975(94)90041-8
[8] Kurka, P., Maass, A.: Limit sets of cellular automata associated to probability measures. Journal of Statistical Physics 100, 1031–1047 (2000) · Zbl 0995.37008 · doi:10.1023/A:1018706923831
[9] von Neumann, J.: Theory of Self-Reproducing Automata. University of Illinois Press, Champaign (1966)
[10] Rice, H.G.: Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society 74(2), 358–366 (1953) · Zbl 0053.00301 · doi:10.1090/S0002-9947-1953-0053041-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.