Codage d’une machine de Turing dans un décalage sur Z

Codage d’une machine de Turing dans un décalage sur Z

Cette construction utilise un décalage substitutif (voir la Partie 2.1), dont on sait qu’il est aussi sofique par un résultat de Mozes [Moz89], pour définir des espaces de calcul. Les diagrammes espace-temps de la machine de Turing sont ajoutés à ces espaces de calcul à l’aide d’opérations simples sur les décalages (voir la Partie 2.2) afin d’obtenir le décalage sofique souhaité (voir la Partie 2.3). Cette construction constitue le point principal de la preuve du Théorème 3.1.1, qui sera présentée dans le Chapitre 3. Elle sera aussi réutilisée et adaptée aux, ce qui signifie qu’avec notre formalisme, le support du motif s(a) dépend de la lettre a. Une substitution multidimensionnelle est non dégénérée si kNous venons de voir comment une substitution peut agir sur un motif fini ou sur une configuration infinie. Supposons maintenant qu’il nous est donné un ensemble fini de substitutions, comment le faire agir sur un motif ou une configuration ?, chaque substitution étant appliquée de manière uniforme à toutes les lettres d’une configuration (Partie 2.1.3). Mais l’ensemble S peut également agir de manière non uniforme sur une configuration x, la substitu- tion appliquée à une lettre de x dépendant cette fois de la position de la lettre (Partie 2.1.4).

Dans une première approche combinatoire, on s’intéresse au langage des mo-tifs produits par la suite S, appelés les S-motifs, que l’on interprète comme les motifs autorisés d’un décalage. Le décalage S-adique local engendré par la suite sur une configuration de manière non déterministe, ou plus précisément de ma- nière non uniforme. Étant donné un motif p 2 A L’ensemble des S -motifs est défini par induction. Un S -motif de niveau 0 est une lettre de l’alphabet A, et p est un S -motif de niveau n + 1 s’il existe un S -motif pToutes les substitutions considérées jusqu’ici sont déterministes, puisque leur ensemble de règles est donné par une fonction. Cependant le formalisme pré- senté avec les ensembles de substitutions S englobe aussi ces substitutions non déterministes. Étant donnée s une substitution non déterministe, si une lettre a 2 A a deux images possibles p. En répétant ce procédé, on peut transformer une substitution non déterministe s en un ensemble de substitutions déterministes S de sorte que le décalage ( ;Remarque. La propriété A est tout de même vérifiée par bon nombre d’en- sembles de substitutions. Par exemple tout ensemble de substitutions S dans lequel l’image d’une lettre par une substitution s 2 S ne dépend que de la substitution s possède la propriété A. De plus, si l’ensemble S est réduit à une unique substitution déterministe, alors S possède la propriété A.

Idée de la démonstration Nous donnons les principales idées pour adapter la preuve originale du Théorème 2.1.1, et ainsi obtenir un schéma de preuve du Corollaire 2.1.2. Soit S un ensemble de substitutions qui possède la propriété A.est un facteur de . Ledécalage contient une grille qui assure qu’une configuration x appartient au décalage sofique si et seulement si on peut trouver, pour tout n 2 N, unesont codés àl’intérieur d’une structure hiérarchique. On appelle Q l’ensemble des motifs de taille 2 2 qui apparaissent dans un S -motif. En plus de ce réseau permettant de dé-substituer la configuration x autant qu’on le souhaite, on ajoute la condi- tion suivante : tout motif de taille 2 2 qui apparaît dans une configurationil est facile de construire une configuration y de qui code x et toutes ses pré-images. Réciproquement étant donné un motif p qui apparaît dans une configuration x 2 , on peut trouver une suite de motifs finis de substitution (sp apparaît dans un motif de taille 2 2 qui apparaît lui-même dans un S -motif (grâce à la condition Q), et la propriété A assure alors que le motif p apparaît aussi dans un S -motif (voir la Figure 7). Ainsi l’utilisation conjointe de la propriété A et de la condition Q assure que tout motif apparaissant dans x apparaît aussi dans un S -motif.s’exprime essentiellement avec les S -motifs. Toute configuration x appartenant à l’un de ces deux décalages doit posséder un antécédent d’ordre arbitraire par S , ce que la construction de Mozes nous assure, mais on impose à tout motif apparaissant dans x d’être un S -motif uniquement pour le décalage T.