Simulation cellulaire

 Simulation cellulaire

Reprenons les notions de morphismes et de simulations définies dans la section 1.2, en se servant de la structure de l’espace symbolique pour obtenir une idée intuitive de «codage simple» entre les deux systèmes concernés. La simplicité se voit ici dans le caractère local du morphisme : les fractions finies des configurations peuvent ainsi être traduites en parallèle, et indépendamment des cellules situées loin d’elles. En d’autres termes, par le théorème de Hedlund 2.2.1, le morphisme est également un morphisme du décalage. Morphismes cellulaires.

Unmorphisme cellulaire d’un SS (Σ,F) dans un autre (Λ,G) est un morphisme de (Σ,F) dans (Λ,G) qui est aussi est morphisme de (Σ,σm) dans (Λ,σm′), où m,m′ ∈ ◆∗.– S’il est surjectif, c’est une factorisation cellulaire et (Λ,G) est appelé facteur cellulaire de (Σ,F).

S’il est bijectif, c’est une conjugaison cellulaire; (Σ,F) et (Λ,G) sont alors dits conjugués cellulaires.– Une sous-conjugaison (resp. sous-factorisation) cellulaire de (Σ,F) dans (Λ,G) est une conjugaison (resp. factorisation) cellulaire d’un sous-système (Σ′,F) dans (Λ,G), où (Σ′,σ) est un sous-système de (Σ,σ).

Ce dernier est alors un sous-conjugué (resp. sous-facteur) de (Σ,F).– Une sous-conjugaison (resp. sous-factorisation) cellulaire est dite par blocs (resp. de type fini, sofique) si Σ′ est un décalage complet sur un sous-alphabet (resp. un STF, un sous-décalage sofique). Le grand avantage de ces morphismes cellulaires est de préserver un tant soit peu la structure de l’espace des configurations, ce qui permettra une meilleure notion de préservation de la dynamique d’un AC.

En particulier, on peut remarquer que l’image d’une configuration périodique par un tel morphisme reste périodique. Simulations cellulaires. Définition 3.2.2 (Simulation cellulaire).– Une simulation cellulaire de période n ∈ ◆∗ par pas de n′ ∈ ◆∗ (ou (n,n′)-simulation cellulaire) par un SS (Σ,F) d’un autre (Λ,G) est une (n,n′)-simulation par (Σ,F) de (Λ,G), qui est à la fois une simulation par (Σ,σ) de (Λ,σ).– Elle est carrée si la période m et le pas m′ de la simulation du décalage sont égaux à la période n et au pas n′ de la simulation du SS

Une simulation directionnelle de pente α ∈ ◗ par un SS (Σ,F) d’un autre (Λ,G) est une simulation cellulaire par (Σ,σpFq) de (Λ,G), où α = p q. On pourra qualifier une simulation de par blocs ou hors-contexte en sous-entendant qu’il s’agit d’une simulation cellulaire. On remarque que la notion de simulation cellulaire «colle» à celle d’ACP : en commutant avec les décalages, on obtient que tout SS simulé par un ACP est un ACP, et que tout SS simulé par blocs hors-contexte d’un AC est un AC.

On peut remarquer que ce qui importe dans la définition de la simulation directionnelle est la pente p q : on peut s’arranger pour que la fraction soit irréductible, puisqu’une simulation par (A❩,σkpFkq) de (B❩,G) est bien toujours une simulation par (A❩,σpFq) de (B❩,G), quel que soit k ∈ ◆.

Une variante, correspondant à l’approche de [79], autoriserait les simulations directionnelles à avoir des pentes irrationnelles. Une autre variante de simulation cellulaire consisterait à autoriser le pas et la période horizontaux n,n′ ∈ ❩∗ à être de signes opposés. En d’autres termes, on assimilerait le comportement d’un SS et son symétrique, ce qui peut s’avérer intéressant dans certains cas.

Remarque 3.2.3. La définition de simulation directionnelle, qui vient du fait qu’on s’intéresse à l’action de la règle locale avant tout, peut être vue comme la simulation de l’AC en tant qu’action continue du monoïde commutatif ❩ × ◆ définie pour (i,j) ∈ ❩ × ◆ par (F,σ)(i,j) : x → σiFj(x). Cette notion se rapproche alors de la simulation : il existe deux couples p,q ∈ ❩ × ◆ et une sous-factorisation Φ de (X,(F,σ)p) dans (Y,(G,σ)q), i.e. pour tout k ∈ ◆2, Φ(F,σ)pk = (G,σ)qkΦ (où les produits pk et qk sont compris composante par composante). Si

milairement à la remarque 1.2.5, on peut montrer que les simulations directionnelle, cellulaire, par blocs, hors-contexte représentent des relations transitives et réflexives; elles induisent donc des préordres sur les SS. Le préordre des simulations par blocs hors-contexte carrées (sans décalage) sur les AC a été particulièrement étudié dans [29, 57]. Puis il a été généralisé dans [30] aux simulations directionnelles par blocs hors-contexte exactes. Dans [31], on trouve des comparaisons intéressantes entre la structure de plusieurs préordres :

cette même simulation directionnelle par blocs hors-contexte exacte,– la simulation directionnelle par blocs hors-contexte complète,– la simulation directionnelle par blocs hors-contexte. Sortir du cadre des simulations par blocs hors-contexte introduit nombre de problèmes et ne permet pas d’utiliser au mieux toutes les possibilités des AC : des propriétés simples visibles sur les cellules des configurations pourraient ne pas se transmettre; en particulier, le simulé peut ne plus être un AC. On peut également ne plus avoir de préordre. Universalité intrinsèque.

Les AC intrinsèquement universels pour une loi de simulation sont ceux qui simulent tous les AC. Après être apparue dans [25], cette définition a subi une évolution progressive. Dans [30], on les définit pour la simulation directionnelle par blocs hors-contexte exacte et il est prouvé que la simulation peut de plus être requise totale sans que cela n’affecte cette définition d’universalité de façon similaire au corollaire 2.6.40 sur les sous-décalages.