caracunaire.tex

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