cs.tex

   1 Dans  cette  partie, les  définitions  fondamentales  liées  au chaos  dans  les
   2 systèmes booléens sont rappelées et plusieurs résultats théoriques sont montrés.
   3
   4 \begin{Def}[Chaos (Devaney)]
   5 Une fonction $k$ continue sur un espace métrique $(\mathcal{X},d)$ est \textbf{chaotique}
   6 si elle est transitive,
   7 régulière et fortement sensible aux conditions initiales.
   8 \end{Def}
   9
  10 \begin{Def}[Transitivité]
  11 Une fonction $k$ est  \textbf{transitive} sur $(\mathcal{X},d)$ si  la propriété suivante est établie:
  12 \[
  13 \forall X, Y\in \mathcal{X},
  14 \forall \epsilon > 0,
  15 \exists  Z \in \mathcal{X},
  16 \exists  t \in \Nats,
  17 d(X,Z) < \epsilon  \land k^t(Z) = Y
  18 \]
  19 \end{Def}
  20
  21 \begin{Def}[Point périodique]
  22   Un point $P  \in \mathcal{X}$ est dit \textbf{périodique}  de période $t$ pour
  23   une fonction $k$ si $t$ est un entier  naturel non nul tel que $k^t(P) = P$ et
  24   pour tout $n$, $0 < n \le t-1$, on a $k^n(P) \neq P$.
  25   Par la  suite, $\textbf{Per(k)}$ dénote  l'ensemble des points  périodiques de
  26   $k$ dans $\mathcal{X}$ de période quelconque.
  27 \end{Def}
  28
  29 \begin{Def}[Régularité]
  30 Une fonction $k$  est dite \textbf{régulière} dans $(\mathcal{X},d)$
  31 si l'ensemble des points périodiques de $k$ est dense dans $\mathcal{X}$,
  32 c'est-à-dire  si la propriété suivante est établie:
  33 \[
  34 \forall X \in \mathcal{X}, \forall \epsilon > 0, \exists Y \in \textit{Per}(k)
  35  \textrm{ tel que } d(X,Y) < \epsilon.
  36 \]
  37 \end{Def}
  38
  39 \begin{Def}[Forte sensibilité aux conditions initiales]
  40 Une fonction $k$ définie sur $(\mathcal{X},d)$
  41 est  \textbf{fortement sensible aux conditions initiales}
  42 s'il existe une valeur $\epsilon> 0$ telle que
  43 pour tout $X \in \mathcal{X}$ et pour tout
  44  $\delta > 0$, il existe  $Y \in  \mathcal{X}$ et
  45 $t \in \Nats$ qui vérifient  $d(X,Y) < \delta$ et
  46 $d(k^t(X) , k^t(Y)) > \epsilon$.
  47 \end{Def}
  48
  49
  50 John Banks et ses collègues ont cependant
  51 démontré que la sensibilité aux conditions initiales est une conséquence
  52 de la régularité et de la transitivité topologique~\cite{Banks92}.
  53 On ne se focalise donc que sur ces deux dernières
  54 propriétés pour caractériser les fonctions booléennes $f$
  55 rendant chaotique la fonction engendrée $G_f$.
  56 Ceci est réalisé en établissant les relations d'inclusion entre
  57 les ensembles $\mathcal{T}$ des fonctions topologiquement transitives,
  58 $\mathcal{R}$ des fonctions régulières
  59 et $\mathcal{C}$ des fonctions chaotiques définis respectivement ci-dessous:
  60 \begin{itemize}
  61 \item   $\mathcal{T}   =    \left\{f   :   \mathds{B}^n   \to
  62 \mathds{B}^n \big/ G_f \textrm{ est transitive} \right\}$,
  63 \item   $\mathcal{R}   =    \left\{f   :   \mathds{B}^n   \to
  64 \mathds{B}^n \big/ G_f \textrm{ est régulière} \right\}$,
  65 \item   $\mathcal{C}   =    \left\{f   :   \mathds{B}^n   \to
  66 \mathds{B}^n  \big/  G_f  \textrm{  est chaotique} \right\}$.
  67 \end{itemize}
  68
  69
  70 Commençons par caractériser l'ensemble $\mathcal{T}$ des fonctions transitives:
  71
  72 \begin{Theo} $G_f$  est transitive si et seulement si
  73  $\Gamma(f)$ est fortement connexe.
  74 \end{Theo}
  75
  76 \begin{Proof}
  77
  78 $\Longleftarrow$ Supposons que $\Gamma(f)$ soit fortement connexe.
  79 Soient $(S,x)$ et $(S',x')$ deux points de $\mathcal{X}$ et  $\varepsilon >0$.
  80 On construit la stratégie $\tilde S$ telle que la distance
  81 entre $(\tilde S,x)$ et  $(S,x)$ est inférieure à
  82 $\varepsilon$ et telle que les  itérations parallèles de $G_f$ depuis
  83 $(\tilde S,x)$ mènent au point $(S',x')$.
  84
  85 Pour cela, on pose $t_1 =-\lfloor\log_{10}(\varepsilon)\rfloor$ et   $x''$ la
  86 configuration de $\Bool^n$ obtenue depuis $(S,x)$ après $t_1$ itérations
  87 parallèles de $G_f$.
  88 Comme $\Gamma(f)$ est fortement connexe, il existe une
  89 stratégie $S''$ et un entier  $t_2$ tels que $x'$ est atteint depuis
  90 $(S'',x'')$ après $t_2$ itérations de $G_f$.
  91
  92 Considérons à présent la stratégie
  93 $\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)$.
  94 Il est évident que $(s',x')$ est atteint depuis  $(\tilde S,x)$ après
  95 $t_1+t_2$ itérations parallèles de $G_f$. Puisque
  96 $\tilde s_t=s_t$ pour $t<t_1$, grâce au choix de $t_1$,
  97 on a $d((S,x),(\tilde
  98 S,x))<\epsilon$.
  99 Par conséquent, $G_f$ est transitive.
 100
 101 $\Longrightarrow$ Démontrons la contraposée.
 102 Si $\Gamma(f)$ n'est pas  fortement connexe, alors
 103 il existe deux configurations $x$  et $x'$ telles qu'aucun chemin de
 104 $\Gamma(f)$ ne mène de $x$ à $x'$.
 105 Soient $S$ et $S'$ deux stratégies et $\varepsilon \in ]0;1[$.
 106 Alors, pour tout $(S'',x'')$ tel que
 107 $d((S'',x''),(S,x))<\varepsilon$ on a $x''$ qui est égal à $x$.
 108 Comme il n'existe aucun chemin de $\Gamma(f)$
 109 qui mène de $x$ à $x'$,
 110 les itérations de $G_f$ à partir de
 111 $(S'', x'') = (S'', x)$ ne peuvent atteindre que des points
 112 $(S''', x''')$ de $\mathcal{X}$ tels que $x''' \neq x'$,
 113 et donc ne peuvent pas atteindre $(S', x')$.
 114 On peut remarquer que, du fait que $x''' \neq x'$,
 115 elles n'atteignent que des points de $\mathcal{X}$
 116 dont la distance à $(S', x')$ est supérieure à 1.
 117 Pour tout entier naturel $t$, on a
 118 $G_f^t(S'',x'') \neq (S',x')$.
 119 Ainsi $G_f$ n'est pas transitive et
 120 par contraposée, on a la démonstration souhaitée.
 121 \end{Proof}
 122
 123
 124 Prouvons à présent le théorème suivant:
 125
 126 \begin{Theo}
 127 \label{Prop: T est dans R} $\mathcal{T} \subset \mathcal{R}$.
 128 \end{Theo}
 129
 130
 131 \begin{Proof}
 132 Soit $f:\Bool^n\to\Bool^n$ telle que  $G_f$ est transitive (\textit{i.e.}
 133 $f$ appartient à $\mathcal{T}$).
 134 Soit $(S,x) \in\mathcal{X}$ et $\varepsilon >0$. Pour
 135 prouver que $f$ appartient à  $\mathcal{R}$, il suffit de prouver
 136 qu'il existe une stratégie $\tilde S$ telle que la distance entre
 137 $(\tilde S,x)$ et $(S,x)$ est inférieure à  $\varepsilon$ et telle que
 138 $(\tilde S,x)$ est un  point périodique.
 139
 140 Soit $t_1=-\lfloor \log_{10}(\varepsilon)\rfloor$  et soit $x'$ la
 141 configuration obtenue après $t_1$ itérations de $G_f$ depuis  $(S,x)$.
 142 D'après la proposition précédente, $\Gamma(f)$ est fortement connexe.
 143 Ainsi, il existe une stratégie $S'$ et un nombre $t_2\in\Nats$ tels
 144 que $x$ est atteint depuis $(S',x')$ après $t_2$ itérations de $G_f$.
 145
 146 Soit alors la  stratégie $\tilde S$ qui alterne les $t_1$ premiers termes
 147 de $S$ avec les $t_2$ premiers termes de $S'$.
 148 Ainsi $\tilde S$ est définie par
 149 \begin{equation*}
 150 (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).
 151 \end{equation*}
 152 Il est évident que  $(\tilde S,x)$ s'obtient à partir de  $(\tilde S,x)$ après
 153 $t_1+t_2$ itérations parallèles de $G_f$. Ainsi $(\tilde S,x)$ est un point
 154 périodique. Puisque $\tilde s_t$ est égal à $s_t$ pour $t<t_1$, d'après le
 155 choix de  $t_1$, on a  $d((S,x),(\tilde S,x))<\epsilon$.
 156 \end{Proof}
 157
 158 On peut conclure  que $\mathcal{C} = \mathcal{R} \cap \mathcal{T}
 159 = \mathcal{T}$. On a alors la  caractérisation suivante:
 160
 161 \begin{Theo}%[Characterization of $\mathcal{C}$]
 162 \label{Th:CaracIC}
 163 Soit $f:\Bool^n\to\Bool^n$. La fonction $G_f$ est chaotique
 164 si et seulement si $\Gamma(f)$ est fortement connexe.
 165 \end{Theo}
 166
 167
 168 %%% Local Variables:
 169 %%% mode: latex
 170 %%% TeX-master: "main"
 171 %%% End: