\begin{Proof}
$\Longleftarrow$ Supposons que $\Gamma(f)$ soit fortement connexe.
-Soient $(S,x)$ et $(S',x')$ deux points de $\mathcal{X}$ et $\varepsilon >0$.
+Soient $(x,S)$ et $(x',S')$ deux points de $\mathcal{X}$ et $\varepsilon >0$.
On construit la stratégie $\tilde S$ telle que la distance
-entre $(\tilde S,x)$ et $(S,x)$ est inférieure à
+entre $(x,\tilde S)$ et $(x,S)$ est inférieure à
$\varepsilon$ et telle que les itérations parallèles de $G_f$ depuis
-$(\tilde S,x)$ mènent au point $(S',x')$.
+$(x,\tilde S)$ mènent au point $(x',S')$.
Pour cela, on pose $t_1 =-\lfloor\log_{10}(\varepsilon)\rfloor$ et $x''$ la
-configuration de $\Bool^n$ obtenue depuis $(S,x)$ après $t_1$ itérations
+configuration de $\Bool^{\mathsf{N}}$ obtenue depuis $(x,S)$ après $t_1$
+itérations
parallèles de $G_f$.
Comme $\Gamma(f)$ est fortement connexe, il existe une
stratégie $S''$ et un entier $t_2$ tels que $x'$ est atteint depuis
-$(S'',x'')$ après $t_2$ itérations de $G_f$.
+$(x'',S'')$ après $t_2$ itérations de $G_f$.
Considérons à présent la stratégie
$\tilde S=(s_0,\dots,s_{t_1-1},s''_0,\dots,s''_{t_2-1},s'_0,s'_1,s'_2,s'_3\dots)$.
-Il est évident que $(s',x')$ est atteint depuis $(\tilde S,x)$ après
+Il est évident que $(x',s')$ est atteint depuis $(x,\tilde S)$ après
$t_1+t_2$ itérations parallèles de $G_f$. Puisque
$\tilde s_t=s_t$ pour $t<t_1$, grâce au choix de $t_1$,
-on a $d((S,x),(\tilde
-S,x))<\epsilon$.
+on a $d((x,S),(x,\tilde S))<\epsilon$.
Par conséquent, $G_f$ est transitive.
$\Longrightarrow$ Démontrons la contraposée.
il existe deux configurations $x$ et $x'$ telles qu'aucun chemin de
$\Gamma(f)$ ne mène de $x$ à $x'$.
Soient $S$ et $S'$ deux stratégies et $\varepsilon \in ]0;1[$.
-Alors, pour tout $(S'',x'')$ tel que
-$d((S'',x''),(S,x))<\varepsilon$ on a $x''$ qui est égal à $x$.
+Alors, pour tout $(x'',S'')$ tel que
+$d((x'',S''),(x,S))<\varepsilon$ on a $x''$ qui est égal à $x$.
Comme il n'existe aucun chemin de $\Gamma(f)$
qui mène de $x$ à $x'$,
les itérations de $G_f$ à partir de
-$(S'', x'') = (S'', x)$ ne peuvent atteindre que des points
-$(S''', x''')$ de $\mathcal{X}$ tels que $x''' \neq x'$,
-et donc ne peuvent pas atteindre $(S', x')$.
+$(x'',S'') = (x,S'')$ ne peuvent atteindre que des points
+$(x''',S''')$ de $\mathcal{X}$ tels que $x''' \neq x'$,
+et donc ne peuvent pas atteindre $(x',S')$.
On peut remarquer que, du fait que $x''' \neq x'$,
elles n'atteignent que des points de $\mathcal{X}$
-dont la distance à $(S', x')$ est supérieure à 1.
+dont la distance à $(x',S')$ est supérieure à 1.
Pour tout entier naturel $t$, on a
-$G_f^t(S'',x'') \neq (S',x')$.
+$G_f^t(x'',S'') \neq (x',S')$.
Ainsi $G_f$ n'est pas transitive et
par contraposée, on a la démonstration souhaitée.
\end{Proof}
\begin{Proof}
-Soit $f:\Bool^n\to\Bool^n$ telle que $G_f$ est transitive (\textit{i.e.}
+Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$ telle que $G_f$ est transitive (\textit{i.e.}
$f$ appartient à $\mathcal{T}$).
-Soit $(S,x) \in\mathcal{X}$ et $\varepsilon >0$. Pour
+Soit $(x,S) \in\mathcal{X}$ et $\varepsilon >0$. Pour
prouver que $f$ appartient à $\mathcal{R}$, il suffit de prouver
qu'il existe une stratégie $\tilde S$ telle que la distance entre
-$(\tilde S,x)$ et $(S,x)$ est inférieure à $\varepsilon$ et telle que
-$(\tilde S,x)$ est un point périodique.
+$(x,\tilde S)$ et $(x,S)$ est inférieure à $\varepsilon$ et telle que
+$(x,\tilde S)$ est un point périodique.
Soit $t_1=-\lfloor \log_{10}(\varepsilon)\rfloor$ et soit $x'$ la
-configuration obtenue après $t_1$ itérations de $G_f$ depuis $(S,x)$.
+configuration obtenue après $t_1$ itérations de $G_f$ depuis $(x,S)$.
D'après la proposition précédente, $\Gamma(f)$ est fortement connexe.
Ainsi, il existe une stratégie $S'$ et un nombre $t_2\in\Nats$ tels
-que $x$ est atteint depuis $(S',x')$ après $t_2$ itérations de $G_f$.
+que $x$ est atteint depuis $(x',S')$ après $t_2$ itérations de $G_f$.
Soit alors la stratégie $\tilde S$ qui alterne les $t_1$ premiers termes
de $S$ avec les $t_2$ premiers termes de $S'$.
\begin{equation*}
(s_0,\dots,s_{t_1-1},s'_0,\dots,s'_{t_2-1},s_0,\dots,s_{t_1-1},s'_0,\dots,s'_{t_2-1},s_0,\dots).
\end{equation*}
-Il est évident que $(\tilde S,x)$ s'obtient à partir de $(\tilde S,x)$ après
-$t_1+t_2$ itérations parallèles de $G_f$. Ainsi $(\tilde S,x)$ est un point
+Il est évident que $(x,\tilde S)$ s'obtient à partir de $(x,\tilde S)$ après
+$t_1+t_2$ itérations parallèles de $G_f$. Ainsi $(x,\tilde S)$ est un point
périodique. Puisque $\tilde s_t$ est égal à $s_t$ pour $t<t_1$, d'après le
-choix de $t_1$, on a $d((S,x),(\tilde S,x))<\epsilon$.
+choix de $t_1$, on a $d((x,S),(x,\tilde S))<\epsilon$.
\end{Proof}
On peut conclure que $\mathcal{C} = \mathcal{R} \cap \mathcal{T}
\begin{theorem}%[Characterization of $\mathcal{C}$]
\label{Th:CaracIC}
-Soit $f:\Bool^n\to\Bool^n$. La fonction $G_f$ est chaotique
+Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$. La fonction $G_f$ est chaotique
si et seulement si $\Gamma(f)$ est fortement connexe.
\end{theorem}
