caracgeneralise.tex

   1
   2 Commençons par caractériser l'ensemble $\mathcal{T}$ des fonctions transitives:
   3
   4 \begin{theorem} $G_{f_g}$  est transitive si et seulement si
   5  $\textsc{gig}(f)$ est fortement connexe.
   6 \end{theorem}
   7
   8 \begin{Proof}
   9
  10 $\Longleftarrow$ Supposons que $\textsc{gig}(f)$ soit fortement connexe.
  11 Soient $(x,S)$ et $(x',S')$ deux points de $\mathcal{X}_g$ et  $\varepsilon >0$.
  12 On construit la stratégie $\tilde S$ telle que la distance
  13 entre $(x,\tilde S)$ et  $(x,S)$ est inférieure à
  14 $\varepsilon$ et telle que les  itérations parallèles de $G_{f_g}$ depuis
  15 $(x,\tilde S)$ mènent au point $(x',S')$.
  16
  17 Pour cela, on pose $t_1 =-\lfloor\log_{10}(\varepsilon)\rfloor$ et   $x''$ la
  18 configuration de $\Bool^{\mathsf{N}}$ obtenue depuis $(x,S)$
  19 après $t_1$ itérations
  20 parallèles de $G_{f_g}$.
  21 Comme $\textsc{gig}(f)$ est fortement connexe, il existe une
  22 stratégie $S''$ et un entier  $t_2$ tels que $x'$ est atteint depuis
  23 $(x'',S'')$ après $t_2$ itérations de $G_{f_g}$.
  24
  25 Considérons à présent la stratégie
  26 $\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)$.
  27 Il est évident que $(x',s')$ est atteint depuis  $(x,\tilde S)$ après
  28 $t_1+t_2$ itérations parallèles de $G_{f_g}$. Puisque
  29 $\tilde s_t=s_t$ pour $t<t_1$, grâce au choix de $t_1$,
  30 on a $d((x,S),(x,\tilde S))<\epsilon$.
  31 Par conséquent, $G_{f_g}$ est transitive.
  32
  33 $\Longrightarrow$ Démontrons la contraposée.
  34 Si $\textsc{gig}(f)$ n'est pas  fortement connexe, alors
  35 il existe deux configurations $x$  et $x'$ telles qu'aucun chemin de
  36 $\textsc{gig}(f)$ ne mène de $x$ à $x'$.
  37 Soient $S$ et $S'$ deux stratégies et $\varepsilon \in ]0;1[$.
  38 Alors, pour tout $(x'',S'')$ tel que
  39 $d((x'',S''),(x,S))<\varepsilon$ on a $x''$ qui est égal à $x$.
  40 Comme il n'existe aucun chemin de $\textsc{gig}(f)$
  41 qui mène de $x$ à $x'$,
  42 les itérations de $G_{f_g}$ à partir de
  43 $(x'',S'') = (x,S'')$ ne peuvent atteindre que des points
  44 $(x''',S''')$ de $\mathcal{X}_g$ tels que $x''' \neq x'$,
  45 et donc ne peuvent pas atteindre $(x',S')$.
  46 On peut remarquer que, du fait que $x''' \neq x'$,
  47 elles n'atteignent que des points de $\mathcal{X}_g$
  48 dont la distance à $(x',S')$ est supérieure à 1.
  49 Pour tout entier naturel $t$, on a
  50 $G_{f_g}^t(x'',S'') \neq (x',S')$.
  51 Ainsi $G_{f_g}$ n'est pas transitive et
  52 par contraposée, on a la démonstration souhaitée.
  53 \end{Proof}
  54
  55
  56 Prouvons à présent le théorème suivant:
  57
  58 \begin{theorem}
  59 \label{Prop: T est dans R:gp} $\mathcal{T} \subset \mathcal{R}$.
  60 \end{theorem}
  61
  62
  63 \begin{Proof}
  64 Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$ telle que  $G_{f_g}$ est transitive (\textit{i.e.}
  65 $f$ appartient à $\mathcal{T}$).
  66 Soit $(x,S) \in\mathcal{X}_g$ et $\varepsilon >0$. Pour
  67 prouver que $f$ appartient à  $\mathcal{R}$, il suffit de prouver
  68 qu'il existe une stratégie $\tilde S$ telle que la distance entre
  69 $(x,\tilde S)$ et $(x,S)$ est inférieure à  $\varepsilon$ et telle que
  70 $(x,\tilde S)$ est un  point périodique.
  71
  72 Soit $t_1=-\lfloor \log_{10}(\varepsilon)\rfloor$  et soit $x'$ la
  73 configuration obtenue après $t_1$ itérations de $G_{f_g}$ depuis  $(x,S)$.
  74 D'après la proposition précédente, $\textsc{gig}(f)$ est fortement connexe.
  75 Ainsi, il existe une stratégie $S'$ et un nombre $t_2\in\Nats$ tels
  76 que $x$ est atteint depuis $(x',S')$ après $t_2$ itérations de $G_{f_g}$.
  77
  78 Soit alors la  stratégie $\tilde S$ qui alterne les $t_1$ premiers termes
  79 de $S$ avec les $t_2$ premiers termes de $S'$.
  80 Ainsi $\tilde S$ est définie par
  81 \begin{equation*}
  82 (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).
  83 \end{equation*}
  84 Il est évident que  $(x,\tilde S)$ s'obtient à partir de  $(x,\tilde S)$ après
  85 $t_1+t_2$ itérations parallèles de $G_{f_g}$. Ainsi $(x,\tilde S)$ est un point
  86 périodique. Puisque $\tilde s_t$ est égal à $s_t$ pour $t<t_1$, d'après le
  87 choix de  $t_1$, on a  $d((x,S),(x,\tilde S))<\epsilon$.
  88 \end{Proof}
  89
  90 On peut conclure  que $\mathcal{C} = \mathcal{R} \cap \mathcal{T}
  91 = \mathcal{T}$. On a alors la  caractérisation suivante:
  92
  93 \begin{theorem}%[Characterization of $\mathcal{C}$]
  94 \label{Th:CaracIC:gp}
  95 Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$. La fonction $G_{f_g}$ est chaotique
  96 si et seulement si $\textsc{gig}(f)$ est fortement connexe.
  97 \end{theorem}