1,042 research outputs found
Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic
No full textRealization of d-dimensional effective subshifts as projective sub-actions of d + d'-dimensional sofic subshifts for d' >= 1 is now well known [Hochman, 2009; Durand/Romashchenko/Shen, 2012; Aubrun/Sablik, 2013]. In this paper we are interested in qualitative aspects of this realization. We introduce a new topological conjugacy invariant for effective subshifts, the speed of convergence, in view to exhibit algorithmic properties of these subshifts in contrast to the usual framework that focuses on undecidable properties
Chaos and Turing Machines on Bidimensional Models at Zero Temperature
No full textEn mécanique statistique d'équilibre ou formalisme thermodynamique un des objectifs est de décrire le comportement des familles de mesures d'équilibre pour un potentiel paramétré par la température inverse. Nous considérons ici une mesure d'équilibre comme une mesure shift invariant qui maximise la pression. Il existe d'autres constructions qui prouvent le comportement chaotique de ces mesures lorsque le système se fige, c'est-à-dire lorsque la température tend vers zéro. Un des exemples les plus importants a été donné par Chazottes et Hochman où ils prouvent la non-convergence des mesures d'équilibre pour un potentiel localement constant lorsque la dimension est supérieure à 3. Dans ce travail, nous présentons une construction d'un exemple bidimensionnel décrit sur un alphabet fini et par un potentiel localement constant tel qu'il existe une séquence eta_k où la non-convergence est assurée pour toute suite de mesures d'équilibre à l'inverse de la température eta_k lorsque la température tend vers zéro. Pour cela nous utilisons la construction décrite par Aubrun et Sablik qui améliore le résultat de Hochman utilisé dans la construction de Chazottes et Hochman.In equilibrium statistical mechanics or thermodynamics formalism one of the main objectives is to describe the behavior of families of equilibrium measures for a potential parametrized by the inverse temperature. Here we consider equilibrium measure as the shift invariant measures that maximizes the pressure. Other constructions already prove the chaotic behavior of these measures when the system freezes, that is, when the temperature goes to zero. One of the most important examples was given by Chazottes and Hochman. They prove the non-convergence of the equilibrium measures for a locally constant potential when the dimension is bigger then 3. In this work we present a construction of a bidimensional example described by a finite alphabet and a locally constant potential there exists a sequence eta_k where the non-convergence occurs for any sequence of equilibrium measures at inverse of temperature eta_k when the temperature goes to zero. For that we use the construction described by Aubrun and Sablik which improves the result of Hochman used in the construction of Chazottes and Hochman
An Order on Sets of Tilings Corresponding to an Order on Languages
No full textInternational audienceTraditionally a tiling is defined with a finite number of finite forbidden patterns. We can generalize this notion considering any set of patterns. Generalized tilings defined in this way can be studied with a dynamical point of view, leading to the notion of subshift. In this article we establish a correspondence between an order on subshifts based on dynamical transformations on them and an order on languages of forbidden patterns based on computability properties
Complexity and Robustness of Tilings with Random Perturbations
No full textLa question centrale de ce manuscrit est celle de la robustesse aux perturbations de pavages définis par règles locales. Ici, un pavage désigne un étiquetage de la grille ℤ^d par un alphabet fini, avec des règles de voisinage déterminant quels symboles peuvent être juxtaposés, à l'instar de pièces de puzzle. Lorsque le nombre de règles est fini, on parle de sous-décalage de type fini (ou Subshift of Finite Type en anglais, abrégé en SFT). Dès la dimension d = 2, des structures complexes (apériodiques, hiérarchiques, autosimilaires) peuvent apparaître pour certains choix de règles locales. L'enjeu est alors de savoir à quel point ces structures sont préservées lorsqu'une faible proportion de perturbations est autorisée. L'enjeu est ici double. D'une part, pour les informaticiens, de telles structures peuvent servir à encoder des modèles de calcul (i.e. des ordinateurs) comme les machines de Turing. En théorie de l'information, il est naturel de se demander si un signal peut être transmis dans un milieu bruité, et par extension s'il est possible de réaliser physiquement un modèle de calcul qui produira des résultats corrects malgré des rares mais inévitables défauts localisés. D'autre part, pour les physiciens, de telles structures sont comparables à celles des quasicristaux, des matériaux hautement ordonnés mais sans structure cristalline (c'est-à-dire périodique), dont on peine encore à proposer un modèle théorique expliquant leur formation. Mon travail dans ce manuscrit vient refléter et entremêler ces deux points de vue. Après quelques chapitres introductifs, le premier bloc thématique concerne un bruit localisé, indépendant d'une cellule à l'autre. Ici, la question est de savoir si, globalement, une structure admissible de forte densité est observable dans les pavages perturbés (on parlera alors de structure stable). Le problème en dimension d = 1 est comme souvent traité à part, auquel cas il est possible de décider (algorithmiquement) si un choix de règles induit un système stable. En dimension d ≥ 2, des exemples de structures stables sont proposés, d'abord périodiques, en exploitant leur redondance en fin de compte assez localisée, puis apériodiques, en se basant sur une variante du pavage apériodique de Robinson (avec une structure quasi-périodique complexe émergeant de règles simples). En implémentant des calculs dans cette structure hiérarchique, par réduction depuis d'autres problèmes indécidables, il est montré que cette question de stabilité est indécidable, et plus précisément Π_2-dure dans la hiérarchie arithmétique. Enfin, par des arguments d'analyse calculable sur l'espace des mesures de probabilité sur ces pavages perturbés, une majoration Π_4 sur la complexité de la stabilité est obtenue. Le second bloc adopte un point de vue plus physique, en associant aux règles locales un potentiel induisant des mesures de Gibbs. La quantité de perturbations découle alors d'un paramètre de température, qu'on fait tendre vers 0 également. Ici, le comportement local est étudié (dans la topologie faible-* ), et la question n'est plus de savoir si le système converge mais vers quelle(s) limite(s). Dans le cas d = 1, de tels potentiels induisent une unique mesure perturbée pour toute température, et cette famille de mesures converge lorsque la température tend vers 0. En dimension d ≥ 2, ce n'est plus le cas, et il existe de tels potentiels pour lesquels le système est chaotique (il n'admet aucune trajectoire convergente). Sous une hypothèse supplémentaire d'uniformité du modèle, je prouve ici que l'ensemble des valeurs d'adhérence des trajectoires est au plus Π_2-calculable. Ensuite, l'optimalité de cette borne est établie via un résultat de réalisation (à homéomorphisme affine calculable près) de tous les ensembles Π_2 calculables comme ensembles d'accumulation pour un certain potentiel, en encodant les calculs nécessaires dans des structures qui s'effaceront à la limite.The central question of this thesis is that of the robustness to perturbations of tilings defined by local rules. Here, a tiling refers to a labelling of the grid ℤ^d by a finite alphabet, with neighbourhood rules determining which symbols can be juxtaposed, like puzzle pieces. When the number of rules is finite, we obtain a Subshift of Finite Type (or SFT). Starting from dimension d = 2, complex structures (aperiodic, hierarchical, self-similar) can appear for certain choices of local rules. The challenge is then to know to what extent these structures are preserved when a small proportion of perturbations is allowed. The challenge here is twofold. Firstly, for computer scientists, such structures can be used to encode computational models (i.e. computers) such as Turing machines. In information theory, it is natural to ask whether a signal can be transmitted in a noisy environment, and by extension whether it is physically possible to create a computational model that will produce correct results despite rare but inevitable localised faults. Secondly, for physicists, such structures are comparable to those of quasicrystals, materials that are highly ordered but have no crystalline (i.e. periodic) structure, and for which it is still difficult to propose a theoretical model explaining their formation. My work in this manuscript reflects and intertwines these two viewpoints. After some introductory chapters, the first thematic block concerns localised noise, independent from one cell to another. Here, the question is to know whether, globally, an admissible structure of high density occurs in the perturbed tilings (we will then speak of a stable structure). As is often the case, the problem in dimension d = 1 is treated separately, in which case it is possible to decide (algorithmically) whether a choice of rules leads to a stable system. In dimension d ≥ 2, examples of stable structures are proposed, first periodic, by exploiting their ultimately quite localised redundancy, then aperiodic, based on a variant of Robinson's aperiodic tiling (with a complex quasi-periodic structure emerging from simple rules). By implementing computations in this hierarchical structure, by reduction from other undecidable problems, it is shown that this question of stability is undecidable, and more precisely Π_2-hard in the arithmetic hierarchy. Finally, using computable analysis arguments on the space of probability measures on these perturbed tilings, a Π_4 upper bound on the complexity of stability is obtained. The second block adopts a more physical outlook, by associating to the local rules a potential inducing Gibbs measures. The quantity of perturbations is then related to a temperature parameter, which will also go to 0. Here, the local behaviour is studied (in the weak-* topology), and the question is no longer whether the system converges but to what limit(s). In the case d = 1, such potentials induce a single Gibbs measurement for any temperature, and this family of measurements converges when the temperature goes to 0. In dimension d ≥ 2, this is no longer the case, and there are such potentials for which the system is chaotic (it admits no convergent trajectory). Under an additional assumption of uniformity of the model, I prove here that the set of adherence values of the trajectories is at most Π_2-computable. Then, the optimality of this bound is established via a realisation result (up to a computable affine homeomorphism) of all Π_2-computable sets as accumulation points for some potential, encoding the necessary computations in structures that will vanish at the limit
Analysis of Mathieu Equation Stable Solutions in the First Zone of Stability
No full textAbstractThe paper presents the results of a homogeneous Mathieu equation studies. Mathieu equation solutions are oscillations, modulated in amplitude and frequency. In the computational experiments we found dependences of the given oscillations on the ratio of the coefficients. These dependences are shown in graphs that can be used for an approximate estimation of the Mathieu equation solutions without integration
Chaos and Turing Machines on Bidimensional Models at Zero Temperature
No full textEn mécanique statistique d'équilibre ou formalisme thermodynamique un des objectifs est de décrire le comportement des familles de mesures d'équilibre pour un potentiel paramétré par la température inverse. Nous considérons ici une mesure d'équilibre comme une mesure shift invariant qui maximise la pression. Il existe d'autres constructions qui prouvent le comportement chaotique de ces mesures lorsque le système se fige, c'est-à-dire lorsque la température tend vers zéro. Un des exemples les plus importants a été donné par Chazottes et Hochman où ils prouvent la non-convergence des mesures d'équilibre pour un potentiel localement constant lorsque la dimension est supérieure à 3. Dans ce travail, nous présentons une construction d'un exemple bidimensionnel décrit sur un alphabet fini et par un potentiel localement constant tel qu'il existe une séquence eta_k où la non-convergence est assurée pour toute suite de mesures d'équilibre à l'inverse de la température eta_k lorsque la température tend vers zéro. Pour cela nous utilisons la construction décrite par Aubrun et Sablik qui améliore le résultat de Hochman utilisé dans la construction de Chazottes et Hochman.In equilibrium statistical mechanics or thermodynamics formalism one of the main objectives is to describe the behavior of families of equilibrium measures for a potential parametrized by the inverse temperature. Here we consider equilibrium measure as the shift invariant measures that maximizes the pressure. Other constructions already prove the chaotic behavior of these measures when the system freezes, that is, when the temperature goes to zero. One of the most important examples was given by Chazottes and Hochman. They prove the non-convergence of the equilibrium measures for a locally constant potential when the dimension is bigger then 3. In this work we present a construction of a bidimensional example described by a finite alphabet and a locally constant potential there exists a sequence eta_k where the non-convergence occurs for any sequence of equilibrium measures at inverse of temperature eta_k when the temperature goes to zero. For that we use the construction described by Aubrun and Sablik which improves the result of Hochman used in the construction of Chazottes and Hochman
Pensar las escalas para pensar las luchas: Autor: Mathieu UHEL
No full textA través de un título sugerente, “pensar las escalas para pensar las luchas”, Mathieu Uhel entreteje la construcción teórico-crítica del concepto escala, generada por la geografía radical anglosajona de finales del siglo XX, con la necesidad/utilidad práctica de la escala para concienciar las luchas sociales. El artículo cumple un doble propósito: por un lado, delinear los elementos de lectura sobre el concepto escala; y, con ello, promover la atención de esta problemática en las luchas contemporáneas. En un primer apartado, Uhel ubica las discusiones académicas en torno a la escala, como herramienta metodológica útil para comprender la complejidad de las sociedades capitalistas; en el segundo apartado, el autor avanza la exposición en torno al contexto de la dimensión escalar del imperialismo capitalista; finalmente, el autor se centra en el rol de la actividad política a escala nacional en la tensa relación entre las imposiciones del capital y la lucha social.Por meio de um título sugestivo, “pensando escalas para pensar lutas”, Mathieu Uhel entrelaça a construção teórico-crítica do conceito de escala, gerado pela geografia radical anglo-saxônica do final do século XX, com a necessidade / utilidade prática escala para aumentar a consciência das lutas sociais. O artigo tem um duplo propósito: por um lado, delinear os elementos de leitura sobre o conceito de escala; e, com isso, promover atenção a esse problema nas lutas contemporâneas. Na primeira seção, Uhel localiza as discussões acadêmicas em torno da escala, como uma ferramenta metodológica útil para compreender a complexidade das sociedades capitalistas; na segunda seção, o autor avança a exposição em torno do contexto da dimensão escalar do imperialismo capitalista; por fim, o autor enfoca o papel da atividade política em escala nacional na tensa relação entre as imposições do capital e a luta social.Mathieu Uhel\u27s suggestive title, “Thinking about scales to think about struggles”, he interweaves the theoretical-critical construction of concept scale, generated by radical Anglo-Saxon geography in the late 20th century, with it´s practical utility to social struggles. The article serves two purposes: on the one hand, Uhel locates academic discussion around scale; and, with this, he promotes attention to this problem in contemporary struggles. In the first section, Uhel locates academic discussions around scale, as a useful methodological tool to understand the complexity of capitalist societies; in the second section, the author advances the argument around the context of the scalar dimension of capitalist imperialism; finally, the author focuses on the role of political activity on a national scale in the tense relationship between the impositions of capital and the social movement
Complexité algorithmique des invariants de type croissance des sous-décalages de type fini sous contrainte dynamique
No full textLes sous-décalages multidimensionnels (SFT) sont des ensembles de colorations d'une grille régulière infinie définis par lois locales. Ces objets sont impliqués dans plusieurs domaines des mathématiques et en particulier la physique statistique. Un problème important est de calculer leur entropie. Cependant, il a été prouvé qu'il n'existe pas d'algorithme uniforme pour faire ce calcul. Une approche naturelle est de trouver une classe de SFT, définie par des contraintes dynamiques, sur laquelle ceci est vrai. Dans ce texte, on propose des résultats reliés à ce problème. Les plus important d'entre eux sont: (1) l'existence de SFT apériodiques vérifiant une variante de la propriété d'assemblage introduite ici et appelée assemblage linéaire; (2) une caractérisation des valeurs de l'entropie pour ces SFT (répondant en particulier à une question ouverte de Hochman et Meyerovitch); (3) une caractérisation d'un seuil pour la calculabilité de l'entropie pour les sous-décalages multidimensionnels à language décidable; (4) une caractérisation des valeurs possibles de la dimension entropique pour les SFT tridimensionnels minimaux. Les deux résultats de caractérisation peuvent être interprétés comme une approximation par le haut de classes de SFT optimales sur lesquelles l'entropie peut être calculé uniformément. Le résultat sur le seuil caractérise une classe optimale mais pour les sous-décalage à langage décidable. Le même problème reste ouvert pour les SFT multidimensionnels. De plus, on étend le problème à l'intervalle unité, et caractérise les valeurs possibles de l'entropie pour les fonctions calculables de l'intervalle.Multidimensional subshifts of finite type (SFT) are sets of colorings of an infinite regular grid defined by local rules. They are involved in many areas of mathematics and in particular statistical physics. One important problem is to compute the entropy of these systems. It was proved that their entropy can not be computed algorithmically in a uniform way. However one canseek for a subclass, in particular defined by dynamical constraints, on which the entropy can be computed algorithmically. In this text, we expose results related to this problem. The most saliant ones are: (1) the existence of aperiodic subshifts of finite type under linear version block gluing constraint, introduced here; (2) a characterization of the values of the entropy for these subshifts (this answers an open question by Hochman and Meyerovitch); (3) a characterization of a threshold on a quantified version of the irreducibility property for the computability of the entropy of decidable subshifts; (4) a characterization of the entropy dimensions of minimal tridimensional SFT. The two characterization results can be interpreted as the approximation from above of some classes of SFT in which the possibility to embed universal computation (and thus have the non-computability of the entropy) vanishes. The result on the threshold characterize an optimal class but is related to decidable subshifts. A challenging open question is to find a similar result for multidimensional SFT. Moreover, we extend this investigation on the unit interval and characterize the values of the entropy of computable interval maps
Mathieu Ichou, Les Enfants d’immigrés à l’école
No full textIt is common to hear in the fields of educational and immigration sociology that on average, the children of immigrants do not perform as well in school as children of native-born parents. Mathieu Ichou offers an innovative sociological analysis on a topic that is heavily exploited by political and media discourse, and subject to much scientific controversy. The author takes distance from the homogenized vision of a “second generation” of students who have totally failed academically, and rep..
- …
