3- Chaos et complexité

Le nombre d'univers possibles est virtuellement infini. Dans ce contexte, Wolfram s'est interrogé sur l'existence de règles générales de comportement des automates cellulaires 11.

S.Wolfram s'est intéressé aux automates à une dimension, deux états avec un voisinage de deux. Il considère que ne sont « légaux » que les automates qui d'une part éliminent toute cellule dont le voisinage est vide, et d'autre part sont symétriques. Il n'existe alors que 32 automates légaux dont l'auteur a réalisé une étude systématique.

Cette étude a montré que, selon l'auteur, de nombreux automates cellulaires (peut-être tous) s'intègrent dans quatre classes principales :

1. Classe I- L'évolution conduit à des configurations homogènes.

Un automate de classe I (règle 36)

1. Classe II- L'évolution conduit à des structures simples ou périodiques.

Un automate de classe II (règle 40)

1. Classe III- L'évolution conduit à des configurations chaotiques.

Un automate de classe III (règle 18)

Ces trois classes peuvent être liées à des comportements physiques connus que l'auteur présente en termes d'attracteurs dans l'espace des phases. Un tel espace est utilisé pour représenter la dynamique d'un système. Chacun des points d'une représentation graphique figure les états du système en fonction du temps. Par exemple, le mouvement d'un pendule sans frottement sera représenté par un cercle décrivant son caractère cyclique. Si l'on considère un pendule réel (c'est-à-dire soumis aux frottements) la trajectoire sera une spirale rejoignant progressivement le centre de la figure, soit le point représentant la position d'arrêt. Ce point, comme le cercle, est un attracteur, il correspond à la trajectoire du système stabilisé. On connaît depuis longtemps l'attracteur fixe où la stabilisation correspond à l'arrêt, ainsi que l'attracteur cyclique. Dans ce dernier cas, le système répète en permanence le même mouvement (votre c?ur tant que vous êtes en vie par exemple), on obtient alors une figure plus ou moins circulaire, mais dans tout les cas bouclant sur elle-même. Plus récemment, en 1963, une nouvelle forme d'attracteur à été découverte : l'attracteur de Lorenz 12 généralisé sous la forme des attracteurs étranges. Ce type de représentation dans l'espace des phases correspond aux systèmes chaotiques. La complexité des figures engendrées y évoque clairement la sensibilité aux conditions initiales.

Attracteurs

Dans le cas de la classe IV, le parallèle avec des mécanismes connus est beaucoup moins évident. Les automates de cette classe évoluent vers des configurations globales complexes.

Un automate de classe IV (règle 20)

Pour Wolfram, « Les automates cellulaires peuvent être vus comme des ordinateurs dans lesquels les données sont représentées par les configurations initiales, et traitées à travers l'évolution temporelle. Le calcul universel [dans le sens de la machine universelle de Turing] implique que des configurations initiales adéquates peuvent gérer des procédures algorithmiques arbitraire 13. » Wolfram constate que les automates cellulaires de classe IV engendrent des structures qui rappellent fortement le Jeu de la vie. Or on sait, parce que cela a été réalisé, que ce dernier permet de construire une machine universelle de Turing. À partir de là, il pose l'hypothèse selon laquelle cette classe caractérise les automates ayant des capacités de Calcul Universel. Pour que cette capacité émerge, les cellules doivent pouvoir communiquer entre elles et transmettre l'information. Dans les automates de classe I et II, l'interdépendance des cellules est trop forte pour qu'un traitement utile puisse avoir lieu. Les automates de classe III quant à eux se caractérisent par une interdépendance trop faible. Les classes I à III sont les plus fréquentes. Elles représentent 30 des 32 automates de Wolfram. Ce n'est donc que dans une minorité de cas -- 2 sur 32 en l'occurrence -- que l'on trouve des automates cellulaires de classe IV. Ces automates cellulaires qui sont à la limite entre les classes I et II d'une part et III d'autre part, sont seuls aptes à un traitement éventuel de l'information et sont donc les seuls « intéressants » 14.

C. Langton s'est intéressé lui aussi à l'existence de règles générales de classification des automates cellulaires. Le problème réside dans le nombre d'automates cellulaires possibles. Si l'on considère les seuls automates à une dimension, 8 états et un voisinage de 5, il existe 8 puissance 8⁵, soit 8³²⁷⁶⁸ (près de 10³⁰⁰⁰⁰) univers possibles. Langton a décidé de caractériser les automates cellulaires en fonction d'un paramètre général, le paramètre . est en fait la probabilité au sein de toutes les configurations de voisinages possibles, qu'une configuration donnée entraîne la « vie » de la cellule, soit :

1-(nombre de transitions « mortelles »/nombre total de transitions).

En construisant des règles de transitions à partir de ce paramètre, Langton a pu proposer une classification des automates cellulaires. Pour une valeur faible, les cellules disparaissent rapidement. Si on élève la valeur grossièrement au-dessus de 0,2 on constate l'apparition de structures cycliques ou persistantes. Au dessus de 0,3 des comportements complexes et imprévisibles apparaissent. Enfin, au dessus de 0,5 la multiplication de structures induit un comportement chaotique. D'une certaine manière, le paramètre indique la température de l'univers de l'automate cellulaire 15.

Les quatre figures suivantes montrent des exemples d'automates une dimension à huit états avec un voisinage de cinq 16.

= 0.1

= 0.25

= 0.45

= 0.8

On retrouve donc bien chez Langton, mais dans un cadre plus général, la classification de Wolfram. D'après Langton, les automates de classe IV, ceux dont le paramètre se situe entre environ 0.3 et 0.5, sont ceux dont la capacité de transmission de l'information est la plus importante : « (...) les automates cellulaires capables de réaliser des calculs non triviaux -- y compris la capacité de Calcul Universel -- ont plus de chance de se trouver au voisinage de la transition de phase entre l'ordre et le chaos (...) 17. » On aurait ainsi la progression suivante dans l'espace des phases :

homogène -> cyclique -> complexe -> chaotique.

J.-C. Heudin 18 utilise un paramètre ( ) qui, dans des automates cellulaires à deux dimensions, correspond au nombre de cellules nécessaires pour qu'une cellule reste inchangée. Si l'on prend le cas de Conway, ce paramètre vaut 2. Il redéfinit les automates à partir de quatre règles soit :

R1 : le voisinage est inférieur à : la cellule meurt.

R2 : une cellule entourée de cellules vivantes conserve son état.

R3 : une cellule ayant +1 voisines vivantes devient vivante.

R4 : une cellule entourée de plus de +1 voisines meurt.

Pour = 1, les probabilités d'exécution des règles sont : R4>R3>R2>R1. Pour = 2, les probabilités s'inversent. On obtient : R1>R2>R3>R4. Au delà de 2, l'ordre reste identique mais les règles R2 à R4 ne s'exécutent que marginalement.

Heudin montre ainsi un changement fondamental dans l'univers des automates cellulaires pour = 2. C'est au cours de cette modification profonde des propriétés de l'automate -- de cette transition de phase -- que se manifeste la complexité : « Pour apparaître [le complexe a] besoin d'ordre et d'une pincée de chaos. Cette situation n'est possible qu'à l'interface des deux régimes, à la frontière qui mène au chaos 19. »

La généralisation des enseignements des automates cellulaires, la diversité des structures universelles ou l'existence de la vie, amènent ainsi à penser que, parmi l'infinité d'univers possibles, les lois de notre Univers sont précisément à la frontière entre l'ordre et le chaos. C'est l'essence de l'approche de Langton dans son expression : « La vie au bord du chaos 20. »