[Benjamin Hellouin, 16.12.21, Luminy]
Dans un groupe à problème du mot décidable, pour les sous-shifts effectifs :
D∈Π⁰₁
PD∈Σ⁰₁ (on peut encoder en un sous-shift dont chaque cellule détermine tout le reste, en encodant l'orbite finie localement)
AD∈Σ¹₁
problèmes Σ¹₁-complets naturels [Harel] :
- domino avec une tuile donnée récurrente
- récurrence d'un état donné des machines non déterministes sur entrée vide
(ou déterministes sur une entrée quelconque. déterministe sur entrée vide : Π⁰₂-complet).
| AD | SFT | sofic | effectif |
| ℤ | Δ⁰₁ | Δ⁰₁ | Π⁰₁ |
| ℤ² | Π⁰₁ | Π⁰₁ | Π⁰₁ |
| ℤ³ | ?? | Σ¹₁ | Σ¹₁ |
| ℤ⁴ | Σ¹₁ | Σ¹₁ | Σ¹₁ |
[Vanier,Hellouin,Grandjean] a montré mardi que dans effectifs ℤ² : AD∈Π⁰₁.
- preuve : deux droites se croisent, donc on peut rassembler inductivement les bris de périodes pour obtenir une fonction f explicitable tq tout x apériodique (de tout sous-shift sur un alphabet donné) contient pour tout n une position dont la boule de rayon f(n) brise les périodes bornées par n (et donc le sous-shift contient une configuration qui les brise toutes autour de la position 0).
[Hellouin,Callard] : sofiques ℤ³ ou SFT ℤ⁴ : AD est Σ¹₁-complet
- preuve : réduction de la récurrence d'état : encodage d'une trace bien initialisée dans un Tœplitz (effectif) 1D. À chaque niveau, l'apparition de l'état particulier brise envoie une ligne (une fois sur deux) et une colonne (une fois sur deux) pour briser les périodes.
- SFT dans ℤ³ : on peut rapprocher aussi deux ou trois bris (en prenant la distance minimale entre deux bris : nombre fini de plans fortement périodiques distincts entre les deux → dépompage). Comment faire l'induction ??
[discussion de l'après-midi]
- WPD∈Σ⁰₂ en général, mais équivalent à PD dans ℤ². Avec la preuve complémentaire de [Hellouin,Callard], on réduit au problème de la non-récurrence d'un état donné des machines non déterministes sur entrée vide (Σ⁰₂, comme toute formule du type "∃ forme finie dans laquelle blabla et à l'extérieur de laquelle blibli").
- Le problème "∃ configuration avec 2 (ou k fixé, ou ≥k) occurrences de rouge" est Σ⁰₂ : encode ta machine et délimite l'entrée avec les deux rouges → on réduit COTOTAL
- Le problème "∀k,∃ configuration avec ≥k occurrences de rouge" est Π⁰₃ : encode ta machine dans la grille sparse de [Jeandel-Vanier], et on marque tous les bits de l'entrée avec des rouge → on réduite COFINITE
- En MSO, on peut dire "il existe un chemin infini sans cycle", et du coup "X est infini" (par le lemme de König X est alors visité infiniment par un chemin), et du coup on peut exprimer DA.
En simulant chaque formule Σⁿᵢ pour tout i, on a un gros résultat de complétude.
Et on peut faire ça sur tous les graphes à largeur arborescente infinie, grâce à l'expression des grilles mineurs de Kuske-Lohrey.
