Study of attractors complexity in cellular automata and the topological structure of Z^d-subshifts
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This work explores two notions of typicality in dynamical systems within the frameworkof symbolic dynamics. The first concerns typical systems from a topological viewpoint: thosethat are “large” in a topological sense, often referred to as generic systems. We focus onthe topological space S d of all subshifts AZd, where A is a finite subset of Z. For d = 1, R.Pavlov and S. Schmieding, [57], have shown that isolated subshifts are generic. To navigatethis question for d ≥ 2, we introduce the notion of maximal subsystem—a subsystem thatis inclusion-wise maximal—and use it to characterise isolated systems in Sd as follows: asubshift is isolated if and only if it is of finite type and it has a finite class of maximalsubsystems that contains every proper subsystem. This class is not generic as in the d = 1case, but any generic class must contain it, hence the interest in it. Later, we provideinsights into how the number of maximal subsystems a subshift has relates to its dynamicaland structural properties. Finally, we use some of the machinery developed to show that theCantor-Bendixon rank of Sd is infinite when d ≥ 2, which drastically differs from the casefor d = 1, where the Cantor-Bendixon rank is 1. The second notion changes focus to typically observable behaviours in the form of attractors. In the context of cellular automata, we investigate how complicated the generic and likely limit sets are, originally introduced by J. Milnor. To measure this, we rely on the well known arithmetical hierarchy and find that in general, the language of the likely limit set is a Σ3 set—for the generic limit set, the same upper bound was already known from [72]. Under the restriction of an automaton with equicontinuity points, we show that both attractors coincide and the complexity decreases to Σ1, with tight bounds. In the case the attractors are inclusion-wise minimal, we find an upper bound of Π2, matching known results for general systems, [62]. Finally, we prove the following realisation theorem: for any pair of chain-mixing Π2 subshifts Y ⊆ X, there exists a cellular automaton whose generic and likely limit sets are precisely X and Y , respectively. Altogether, this work offers new insights into the interplay between structure and observability in symbolic dynamical systems, highlighting how typical behaviours may vary dramatically across dimensions and under different dynamical constraints.
Este trabajo explora dos nociones de tipicalidad en el contexto de la dinámica simbólica. La primera se enfoca en sistemas típicos desde una perspectiva topológica: aquellos que son ”grandes” en sentido topológico, a menudo llamados sistemas genéricos. Nos centramos en el espacio topológico S^d de todos los subshifts A^{Z^d} , donde A es un subconjunto finito de Z. Para d = 1, R. Pavlov y S. Schmieding demostraron que los subshifts aislados son genréricos. Para abordar esta pregunta para d ≥ 2, introducimos la noción de subsistema maximal—un subsistema maximal para la inclusión—y la usamos para caracterizar sistemas aislados en S^d como sigue: un subshift es aislado si y solo si es de tipo finito y tiene una clase finita de subsistemas maximales que contiene a todo subsistema propio. A diferencia del caso d = 1, los sistemas aislados no son genéricos, pero cualquier conjunto genérico debe contenerlos, de ahí el interés por ellos. Luego, exploramos cómo el número de subsistemas maximales de un subshift se relaciona con sus propiedades dinámicas y estructurales. Finalmente, usamos parte de la maquinaria desarrollada para demostrar que el rango de Cantor-Bendixon de S^d es infinito para d ≥ 2, en marcado contraste con el caso d = 1, donde dicho rango es 1.La segunda noción se enfoca en comportamientos típicamente observables, en forma de atractores. En el contexto de autómatas celulares, investigamos cuán complicados pueden llegar a ser los conjuntos límite genérico y métrico, originalmente introducidos por J. Milnor. Para medir esto, nos basamos en la jerarquía aritmética y encontramos que, en general, el lenguaje del conjunto límite métrico es un conjunto Σ_3—para el conjunto límite genérico, esta cota superior ya era conocida, por el trabajo de I. Törmä. Bajo la restricción de un autómata con puntos de equicontinuidad, mostramos que ambos atractores coinciden y que la complejidad disminuye a Σ_1 y que esta cota se alcanza. Cuando los atractores son minimales para la inclusión, hallamos una cota superior de Π_2, coincidiendo con el resultado para sistemas generales de C. Rojas y M. Sablik. Finalmente, probamos el siguiente teorema de realización: para cualquier par de subshifts Π_2 Y,X que son cadena-mixtos y tales que Y ⊆ X, existe un autómata celular cuyos conjuntos límite genérico y métrico son, respectivamente, X e Y .Este trabajo ofrece nuevas perspectivas sobre la interacción entre estructura y observabilidad en sistemas dinámicos simbólicos, destacando cómo los comportamientos típicos pueden variar drásticamente entre dimensiones y bajo distintas restricciones dinámicas.
Este trabajo explora dos nociones de tipicalidad en el contexto de la dinámica simbólica. La primera se enfoca en sistemas típicos desde una perspectiva topológica: aquellos que son ”grandes” en sentido topológico, a menudo llamados sistemas genéricos. Nos centramos en el espacio topológico S^d de todos los subshifts A^{Z^d} , donde A es un subconjunto finito de Z. Para d = 1, R. Pavlov y S. Schmieding demostraron que los subshifts aislados son genréricos. Para abordar esta pregunta para d ≥ 2, introducimos la noción de subsistema maximal—un subsistema maximal para la inclusión—y la usamos para caracterizar sistemas aislados en S^d como sigue: un subshift es aislado si y solo si es de tipo finito y tiene una clase finita de subsistemas maximales que contiene a todo subsistema propio. A diferencia del caso d = 1, los sistemas aislados no son genéricos, pero cualquier conjunto genérico debe contenerlos, de ahí el interés por ellos. Luego, exploramos cómo el número de subsistemas maximales de un subshift se relaciona con sus propiedades dinámicas y estructurales. Finalmente, usamos parte de la maquinaria desarrollada para demostrar que el rango de Cantor-Bendixon de S^d es infinito para d ≥ 2, en marcado contraste con el caso d = 1, donde dicho rango es 1.La segunda noción se enfoca en comportamientos típicamente observables, en forma de atractores. En el contexto de autómatas celulares, investigamos cuán complicados pueden llegar a ser los conjuntos límite genérico y métrico, originalmente introducidos por J. Milnor. Para medir esto, nos basamos en la jerarquía aritmética y encontramos que, en general, el lenguaje del conjunto límite métrico es un conjunto Σ_3—para el conjunto límite genérico, esta cota superior ya era conocida, por el trabajo de I. Törmä. Bajo la restricción de un autómata con puntos de equicontinuidad, mostramos que ambos atractores coinciden y que la complejidad disminuye a Σ_1 y que esta cota se alcanza. Cuando los atractores son minimales para la inclusión, hallamos una cota superior de Π_2, coincidiendo con el resultado para sistemas generales de C. Rojas y M. Sablik. Finalmente, probamos el siguiente teorema de realización: para cualquier par de subshifts Π_2 Y,X que son cadena-mixtos y tales que Y ⊆ X, existe un autómata celular cuyos conjuntos límite genérico y métrico son, respectivamente, X e Y .Este trabajo ofrece nuevas perspectivas sobre la interacción entre estructura y observabilidad en sistemas dinámicos simbólicos, destacando cómo los comportamientos típicos pueden variar drásticamente entre dimensiones y bajo distintas restricciones dinámicas.
Description
Tesis (Doctor en Matemáticas)--Pontificia Universidad Católica de Chile, 2025