Wiki du LAMA (UMR 5127) - Contributions [fr]

Automates cellulaires

2022-05-28T09:58:44Z

Mluque :

Ce projet avait pour but d'étudier le fonctionnement des automates cellulaires et les caractéristiques particulières que l'on peut retrouver chez certains.

== Définitions ==

=== Définition simple ===

Un automate cellulaire est une grille régulière dont les cases sont appelées « cellules ». Chacune a un « état » parmi un ensemble fini. L'état d'une cellule au « tour » t+1 est définit en fonction de cet état et celui de l'ensemble fini de cellules « voisinage » au tour t, par la « règle » de l'automate cellulaire. Lorsque toutes les cellules ont été mises à jour, on parle de « génération ».

Pour un automate de 2 dimensions les voisinages les plus courants sont celui de von Neumann
[[Fichier:voisinage_von_neumann.png|50px]]
et celui de Moore.
[[Fichier:voisinage_moore.png|50px]] (en vert et rouge les cellules appartenant au voisinage de la cellule rouge.)

=== Définition formelle ===

Un automate cellulaire <math>A</math> est définit par le 4-uplet <math>(d,Q,V,\delta)</math> tel que :
* <math>d</math> est un entier positif, la dimension de <math>A</math>. Son réseau est donc <math>\mathbb{Z}^d</math>
* <math>Q</math> est l'ensemble fini des états des cellules de <math>A</math>
* <math>V \subseteq \mathbb{Z}^d</math>, un sous-ensemble fini du réseau, le voisinage. <math>V = \{v_1,\ldots,v_a\}</math>
* <math id="regle">\delta : Q^a \rightarrow Q</math> est la règle locale avec <math>a = |V|</math>
On peut donc définir la fonction globale d'évolution de l'automate <math>F_\delta : Q^{\mathbb{Z}^d} \rightarrow Q^{\mathbb{Z}^d}</math> définit par <math>F_\delta (c) = z \mapsto \delta\bigl(c(z+v_1),\ldots,c(z+v_a)\bigr)</math> pour tout <math>c \in Q^{\mathbb{Z}^d}</math>

== Classifications ==

Bien que les deux classifications qui sont décrites ci-dessous peuvent être retrouvées dans les travaux de certains chercheurs, il est commun de décrire un automate en fonction de leurs caractéristiques particulières sans pour autant les séparer en classes.

=== Classification de Wolfram ===

Stephen Wolfram classe les automates cellulaires en 4 classes selon leur comportement avec des configurations initiales aléatoires :
# Stable : Après un certain nombre de générations, une configuration se répète à l'infini.
# Cyclique : Après un certain nombre de générations, une série de configurations se répètent périodiquement.
# Chaotique : Comportement chaotique et génération de motifs apériodiques.
# Complexe : Apparition de structures complexes possédants divers propriétés comme la capacité de se mouvoir ou de se préserver malgré des perturbations.

L'une des principales critiques de cette classification réside dans son incapacité à déterminer si un automate cellulaire est Turin-universel, venant du fait que Wolfram ne définit la classe qu'à partir de configurations initiales aléatoires, mais pas de structure particulière créée spécifiquement. Malgré cela, cette classification reste la plus étudiée.

[[Fichier:classification_wolfram.png|750px]]

Christopher Langton propose d'envisager ces classes dans un continuum.

[[Fichier:classification_langton.png|250px]]

=== Classification d'Eppstein ===

Il existe une deuxième classification, proposée par David Eppstein. Les automates sont séparés en 4 classes :
# Expansion obligatoire : N'importe quel motif initial s'étend indéfiniment dans toutes les directions.
# Expansion impossible : Aucun motif ne peut s'étendre au-delà de ses limites initiales.
# Contraction impossible : Les motifs ne s'étendent pas forcément indéfiniment, mais ne peuvent jamais se réduire en-deçà de leur limites initiales.
# Expansion et contraction possibles : Seuls ces cas peuvent contenir des vaisseaux.

À l'heure actuelle, les automates qui ont été prouvés Turing-universels appartiennent tous à la 4ème classe. Cependant il n'a pas été démontré que les autres classes ne peuvent pas contenir d'automate Turing-universel puisqu'il existe d'autres façons de transmettre des informations que les vaisseaux.

== Les familles d'automates cellulaires célèbres ==

Il existe de nombreuses familles d'automates cellulaires, mais nous n'en verrons que deux ici.

=== Les automates cellulaires élémentaires ===

Cette famille est la plus simple des automates cellulaires. Ses membres n'ont qu'une dimension et deux états. Le voisinage d'une cellule est composé de celles directement à sa droite et sa gauche et d'elle-même.

Puisque le voisinage prend 3 cellules et que chacune d'elles a un état parmi 2, on a <math>2^3 = 8</math> motifs possibles. Pour chaque motif il y a 2 résultats possibles, donc <math>2^8 = 256</math> règles possibles pour un automate cellulaire de cette famille. Depuis les travaux de S. Wolfram sur cette famille, chacune de ces règles est nommée par le résultat de ses motifs convertit en décimal. Ainsi, la règle suivante est la 103 :
[[Fichier:regle_103.jpg|100px]]
Car
<nowiki>111 110 101 100 011 010 001 000
0 1 1 0 0 1 1 1</nowiki>
Soit <math>01100111_{(2)} = 103_{(10)}</math>

==== Règles intéressantes ====

Certaines de ces 256 règles ont des propriétés particulières. Voici 3 d'entre elles :

===== Règle 22 =====

Lorsque la configuration initiale est composée d'une seule cellule vivante on obtient une approximation du triangle de Sierpiński.

[[Fichier:regle_22.png|500px]]

===== Règle 30 =====

[https://demonstrations.wolfram.com/UsingRule30ToGeneratePseudorandomRealNumbers/#more Selon Wolfram Research], en raison de son comportement local imprévisible et son comportement global chaotique, cet automate cellulaire peut être utilisé comme générateur de nombres pseudo-aléatoires.

[[Fichier:regle_30.png|500px]]

===== Règle 110 =====

Cette règle a été prouvée [[#Universalité Turing|Turing-universelle]].

[[Fichier:regle_110.jpg|500px]]

=== Automates cellulaires type "Vie" ===

Ces automates sont bidimensionnels et utilisent le voisinage de Moore. Leurs règles peuvent toutes s'écrire sous la forme <math>Bx_1,...,x_n/Sy_1,...,y_m</math> avec <math>x</math> le nombre de cellules voisines vivantes nécessaires pour qu'une cellule puisse naître et <math>y</math> le nombre de cellules voisines vivantes nécessaires pour qu'une cellule puisse survivre.

==== Le jeu de la vie de John H. Conway ====

Le jeu de la vie est certainement l'automate cellulaire le plus connu du grand publique. Il a été imaginé par John H. Conway en 1970.

Sa règle est la suivante :
* Une cellule morte nait si elle a exactement 3 cellules voisines vivantes
* Une cellule vivante survie si elle a 2 ou 3 cellules voisines vivantes.
* Dans les autres cas elle sera morte.
Cette règle peut donc s'écrire <math>B3/S23</math>.

Malgré cette règle simple, le jeu de la vie permet d'obtenir une grande variété de type de structures :
* Des structures stables, comme le bloc [[Fichier:stable_block.png|50px]]
* Des structures périodiques, comme le clignotant [[Fichier:periodique_blinker.png|50px]]
* Des vaisseaux, structures mouvantes, comme le planeur [[Fichier:vaisseau_glider.png|50px]]
* Des mathusalems, structures qui vont mettre du temps avant de se stabiliser, comme le pentomino R [[Fichier:mathusalem_pentomino_r.png|50px]]
* Des cannons, structures créant des vaisseaux à un rythme parfois imprévisible, comme le Gosper Glider Gun [[Fichier:canon_gosper_glider_gun.png|50px]]
* Des puffeurs, vaisseaux laissant une trainée de débris, comme le Switch Engine [[Fichier:puffeur_switch_engine.png|50px]]
** Il existe des puffeurs particuliers, les rakes qui agissent à la fois comme des puffeurs et comme des canons, leur débris étant composés de vaisseaux, comme le backrake 1 [[Fichier:rake_backrake_1.png|50px]]
** Il existe également des puffeurs dits spacefillers, dont les débris remplissent tout l'espace d'un motif régulier, comme le Max [[Fichier:spacefiller_max.png|50px]]

Cet automate est [[#Universalité Turing|Turing-universel]] et [[#Universalité intrinsèque|intrinsèquement universel]].

== Universalité ==

On distingue 2 types d'universalité pour les automates cellulaires.

=== Universalité Turing ===

Un automate cellulaire dit Turing-universel a la capacité de simuler une machine de Turing. Il donc capable de réaliser n'importe quel calcul. Plus généralement on accepte comme Turing-universel les automates cellulaires capables de simuler un système Turing-complet.

=== Universalité intrinsèque ===

Un automate cellulaire dit intrinsèquement universel est capable de simuler pas à pas n'importe quel automate de même dimension. L'automate simulateur utilise des groupes de cellules identiques et réguliers, chaque groupe représentant une seule cellule de l'automate simulé. L'automate simulateur peut utiliser plusieurs tours pour simuler une étape de l'automate simulé. Chaque état de l'automate simulé a au moins une configuration correspondante dans l'automate simulateur.

== Remarque sur l'écriture des règles automates cellulaires ==

Il existe de nombreux formats pour donner la règle d'un automate. Pour un [[#Les automates cellulaires élémentaires|automate élémentaire]], on utilisera la concaténation de ses résultats pour chaque motif en binaire ou décimal. Pour un [[#Automates cellulaires type "Vie"|type "Vie"]] on utilisera le format B/S. Pourtant nous avons vu au début que l'écriture formelle de la règle d'un automate cellulaire était celle d'une fonction[[#regle|<sup>[1]</sup>]].
La raison est plutôt simple : Pour l'instant, il n'existe pas d'algorithme capable de générer n'importe quel automate cellulaire de manière optimisée, donc la plupart des logiciels de visualisation d'automates cellulaires préfèrent se concentrer sur certains types d'automates. Il n'est pas ardu pour autant de faire un générateur universel, il sera seulement très lent. C'est d'ailleurs ce que j'ai tenté de faire avec ce programme, écrit en python. [[https://github.com/UP-4303/VISI201-Automates-Cellulaires Voir le projet sur GitHub]]

Automates cellulaires

2022-05-28T09:58:07Z

Mluque :

Création en cours.

Ce projet avait pour but d'étudier le fonctionnement des automates cellulaires et les caractéristiques particulières que l'on peut retrouver chez certains.

== Définitions ==

=== Définition simple ===

Un automate cellulaire est une grille régulière dont les cases sont appelées « cellules ». Chacune a un « état » parmi un ensemble fini. L'état d'une cellule au « tour » t+1 est définit en fonction de cet état et celui de l'ensemble fini de cellules « voisinage » au tour t, par la « règle » de l'automate cellulaire. Lorsque toutes les cellules ont été mises à jour, on parle de « génération ».

Pour un automate de 2 dimensions les voisinages les plus courants sont celui de von Neumann
[[Fichier:voisinage_von_neumann.png|50px]]
et celui de Moore.
[[Fichier:voisinage_moore.png|50px]] (en vert et rouge les cellules appartenant au voisinage de la cellule rouge.)

=== Définition formelle ===

Un automate cellulaire <math>A</math> est définit par le 4-uplet <math>(d,Q,V,\delta)</math> tel que :
* <math>d</math> est un entier positif, la dimension de <math>A</math>. Son réseau est donc <math>\mathbb{Z}^d</math>
* <math>Q</math> est l'ensemble fini des états des cellules de <math>A</math>
* <math>V \subseteq \mathbb{Z}^d</math>, un sous-ensemble fini du réseau, le voisinage. <math>V = \{v_1,\ldots,v_a\}</math>
* <math id="regle">\delta : Q^a \rightarrow Q</math> est la règle locale avec <math>a = |V|</math>
On peut donc définir la fonction globale d'évolution de l'automate <math>F_\delta : Q^{\mathbb{Z}^d} \rightarrow Q^{\mathbb{Z}^d}</math> définit par <math>F_\delta (c) = z \mapsto \delta\bigl(c(z+v_1),\ldots,c(z+v_a)\bigr)</math> pour tout <math>c \in Q^{\mathbb{Z}^d}</math>

== Classifications ==

Bien que les deux classifications qui sont décrites ci-dessous peuvent être retrouvées dans les travaux de certains chercheurs, il est commun de décrire un automate en fonction de leurs caractéristiques particulières sans pour autant les séparer en classes.

=== Classification de Wolfram ===

Stephen Wolfram classe les automates cellulaires en 4 classes selon leur comportement avec des configurations initiales aléatoires :
# Stable : Après un certain nombre de générations, une configuration se répète à l'infini.
# Cyclique : Après un certain nombre de générations, une série de configurations se répètent périodiquement.
# Chaotique : Comportement chaotique et génération de motifs apériodiques.
# Complexe : Apparition de structures complexes possédants divers propriétés comme la capacité de se mouvoir ou de se préserver malgré des perturbations.

L'une des principales critiques de cette classification réside dans son incapacité à déterminer si un automate cellulaire est Turin-universel, venant du fait que Wolfram ne définit la classe qu'à partir de configurations initiales aléatoires, mais pas de structure particulière créée spécifiquement. Malgré cela, cette classification reste la plus étudiée.

[[Fichier:classification_wolfram.png|750px]]

Christopher Langton propose d'envisager ces classes dans un continuum.

[[Fichier:classification_langton.png|250px]]

=== Classification d'Eppstein ===

Il existe une deuxième classification, proposée par David Eppstein. Les automates sont séparés en 4 classes :
# Expansion obligatoire : N'importe quel motif initial s'étend indéfiniment dans toutes les directions.
# Expansion impossible : Aucun motif ne peut s'étendre au-delà de ses limites initiales.
# Contraction impossible : Les motifs ne s'étendent pas forcément indéfiniment, mais ne peuvent jamais se réduire en-deçà de leur limites initiales.
# Expansion et contraction possibles : Seuls ces cas peuvent contenir des vaisseaux.

À l'heure actuelle, les automates qui ont été prouvés Turing-universels appartiennent tous à la 4ème classe. Cependant il n'a pas été démontré que les autres classes ne peuvent pas contenir d'automate Turing-universel puisqu'il existe d'autres façons de transmettre des informations que les vaisseaux.

== Les familles d'automates cellulaires célèbres ==

Il existe de nombreuses familles d'automates cellulaires, mais nous n'en verrons que deux ici.

=== Les automates cellulaires élémentaires ===

Cette famille est la plus simple des automates cellulaires. Ses membres n'ont qu'une dimension et deux états. Le voisinage d'une cellule est composé de celles directement à sa droite et sa gauche et d'elle-même.

Puisque le voisinage prend 3 cellules et que chacune d'elles a un état parmi 2, on a <math>2^3 = 8</math> motifs possibles. Pour chaque motif il y a 2 résultats possibles, donc <math>2^8 = 256</math> règles possibles pour un automate cellulaire de cette famille. Depuis les travaux de S. Wolfram sur cette famille, chacune de ces règles est nommée par le résultat de ses motifs convertit en décimal. Ainsi, la règle suivante est la 103 :
[[Fichier:regle_103.jpg|100px]]
Car
<nowiki>111 110 101 100 011 010 001 000
0 1 1 0 0 1 1 1</nowiki>
Soit <math>01100111_{(2)} = 103_{(10)}</math>

==== Règles intéressantes ====

Certaines de ces 256 règles ont des propriétés particulières. Voici 3 d'entre elles :

===== Règle 22 =====

Lorsque la configuration initiale est composée d'une seule cellule vivante on obtient une approximation du triangle de Sierpiński.

[[Fichier:regle_22.png|500px]]

===== Règle 30 =====

[https://demonstrations.wolfram.com/UsingRule30ToGeneratePseudorandomRealNumbers/#more Selon Wolfram Research], en raison de son comportement local imprévisible et son comportement global chaotique, cet automate cellulaire peut être utilisé comme générateur de nombres pseudo-aléatoires.

[[Fichier:regle_30.png|500px]]

===== Règle 110 =====

Cette règle a été prouvée [[#Universalité Turing|Turing-universelle]].

[[Fichier:regle_110.jpg|500px]]

=== Automates cellulaires type "Vie" ===

Ces automates sont bidimensionnels et utilisent le voisinage de Moore. Leurs règles peuvent toutes s'écrire sous la forme <math>Bx_1,...,x_n/Sy_1,...,y_m</math> avec <math>x</math> le nombre de cellules voisines vivantes nécessaires pour qu'une cellule puisse naître et <math>y</math> le nombre de cellules voisines vivantes nécessaires pour qu'une cellule puisse survivre.

==== Le jeu de la vie de John H. Conway ====

Le jeu de la vie est certainement l'automate cellulaire le plus connu du grand publique. Il a été imaginé par John H. Conway en 1970.

Sa règle est la suivante :
* Une cellule morte nait si elle a exactement 3 cellules voisines vivantes
* Une cellule vivante survie si elle a 2 ou 3 cellules voisines vivantes.
* Dans les autres cas elle sera morte.
Cette règle peut donc s'écrire <math>B3/S23</math>.

Malgré cette règle simple, le jeu de la vie permet d'obtenir une grande variété de type de structures :
* Des structures stables, comme le bloc [[Fichier:stable_block.png|50px]]
* Des structures périodiques, comme le clignotant [[Fichier:periodique_blinker.png|50px]]
* Des vaisseaux, structures mouvantes, comme le planeur [[Fichier:vaisseau_glider.png|50px]]
* Des mathusalems, structures qui vont mettre du temps avant de se stabiliser, comme le pentomino R [[Fichier:mathusalem_pentomino_r.png|50px]]
* Des cannons, structures créant des vaisseaux à un rythme parfois imprévisible, comme le Gosper Glider Gun [[Fichier:canon_gosper_glider_gun.png|50px]]
* Des puffeurs, vaisseaux laissant une trainée de débris, comme le Switch Engine [[Fichier:puffeur_switch_engine.png|50px]]
** Il existe des puffeurs particuliers, les rakes qui agissent à la fois comme des puffeurs et comme des canons, leur débris étant composés de vaisseaux, comme le backrake 1 [[Fichier:rake_backrake_1.png|50px]]
** Il existe également des puffeurs dits spacefillers, dont les débris remplissent tout l'espace d'un motif régulier, comme le Max [[Fichier:spacefiller_max.png|50px]]

Cet automate est [[#Universalité Turing|Turing-universel]] et [[#Universalité intrinsèque|intrinsèquement universel]].

== Universalité ==

On distingue 2 types d'universalité pour les automates cellulaires.

=== Universalité Turing ===

Un automate cellulaire dit Turing-universel a la capacité de simuler une machine de Turing. Il donc capable de réaliser n'importe quel calcul. Plus généralement on accepte comme Turing-universel les automates cellulaires capables de simuler un système Turing-complet.

=== Universalité intrinsèque ===

Un automate cellulaire dit intrinsèquement universel est capable de simuler pas à pas n'importe quel automate de même dimension. L'automate simulateur utilise des groupes de cellules identiques et réguliers, chaque groupe représentant une seule cellule de l'automate simulé. L'automate simulateur peut utiliser plusieurs tours pour simuler une étape de l'automate simulé. Chaque état de l'automate simulé a au moins une configuration correspondante dans l'automate simulateur.

== Remarque sur l'écriture des règles automates cellulaires ==

Il existe de nombreux formats pour donner la règle d'un automate. Pour un [[#Les automates cellulaires élémentaires|automate élémentaire]], on utilisera la concaténation de ses résultats pour chaque motif en binaire ou décimal. Pour un [[#Automates cellulaires type "Vie"|type "Vie"]] on utilisera le format B/S. Pourtant nous avons vu au début que l'écriture formelle de la règle d'un automate cellulaire était celle d'une fonction[[#regle|<sup>[1]</sup>]].
La raison est plutôt simple : Pour l'instant, il n'existe pas d'algorithme capable de générer n'importe quel automate cellulaire de manière optimisée, donc la plupart des logiciels de visualisation d'automates cellulaires préfèrent se concentrer sur certains types d'automates. Il n'est pas ardu pour autant de faire un générateur universel, il sera seulement très lent. C'est d'ailleurs ce que j'ai tenté de faire avec ce programme, écrit en python. [[https://github.com/UP-4303/VISI201-Automates-Cellulaires Voir le projet sur GitHub]]

Automates cellulaires

2022-05-27T17:56:56Z

Mluque :

Automates cellulaires

2022-05-27T17:37:13Z

Mluque :

Création en cours.

Ce projet avait pour but d'étudier le fonctionnement des automates cellulaires et les caractéristiques particulières que l'on peut retrouver chez certains.

== Définitions ==

=== Définition simple ===

Un automate cellulaire est une grille régulière dont les cases sont appelées « cellules ». Chacune a un « état » parmi un ensemble fini. L'état d'une cellule au « tour » t+1 est définit en fonction de cet état et celui de l'ensemble fini de cellules « voisinage » au tour t, par la « règle » de l'automate cellulaire. Lorsque toutes les cellules ont été mises à jour, on parle de « génération ».

Pour un automate de 2 dimensions les voisinages les plus courants sont celui de von Neumann
[[Fichier:voisinage_von_neumann.png|50px]]
et celui de Moore.
[[Fichier:voisinage_moore.png|50px]] (en vert et rouge les cellules appartenant au voisinage de la cellule rouge.)

=== Définition formelle ===

Un automate cellulaire <math>A</math> est définit par le 4-uplet <math>(d,Q,V,\delta)</math> tel que :
* <math>d</math> est un entier positif, la dimension de <math>A</math>. Son réseau est donc <math>\mathbb{Z}^d</math>
* <math>Q</math> est l'ensemble fini des états des cellules de <math>A</math>
* <math>V \subseteq \mathbb{Z}^d</math>, un sous-ensemble fini du réseau, le voisinage. <math>V = \{v_1,\ldots,v_a\}</math>
* <math>\delta : Q^a \rightarrow Q</math> est la règle locale avec <math>a = |V|</math>
On peut donc définir la fonction globale d'évolution de l'automate <math>F_\delta : Q^{\mathbb{Z}^d} \rightarrow Q^{\mathbb{Z}^d}</math> définit par <math>F_\delta (c) = z \mapsto \delta\bigl(c(z+v_1),\ldots,c(z+v_a)\bigr)</math> pour tout <math>c \in Q^{\mathbb{Z}^d}</math>

== Classifications ==

Bien que les deux classifications qui sont décrites ci-dessous peuvent être retrouvées dans les travaux de certains chercheurs, il est commun de décrire un automate en fonction de leurs caractéristiques particulières sans pour autant les séparer en classes.

=== Classification de Wolfram ===

Stephen Wolfram classe les automates cellulaires en 4 classes selon leur comportement avec des configurations initiales aléatoires :
# Stable : Après un certain nombre de générations, une configuration se répète à l'infini.
# Cyclique : Après un certain nombre de générations, une série de configurations se répètent périodiquement.
# Chaotique : Comportement chaotique et génération de motifs apériodiques.
# Complexe : Apparition de structures complexes possédants divers propriétés comme la capacité de se mouvoir ou de se préserver malgré des perturbations.

L'une des principales critiques de cette classification réside dans son incapacité à déterminer si un automate cellulaire est Turin-universel, venant du fait que Wolfram ne définit la classe qu'à partir de configurations initiales aléatoires, mais pas de structure particulière créée spécifiquement. Malgré cela, cette classification reste la plus étudiée.

[[Fichier:classification_wolfram.png|750px]]

Christopher Langton propose d'envisager ces classes dans un continuum.

[[Fichier:classification_langton.png|250px]]

=== Classification d'Eppstein ===

Il existe une deuxième classification, proposée par David Eppstein. Les automates sont séparés en 4 classes :
# Expansion obligatoire : N'importe quel motif initial s'étend indéfiniment dans toutes les directions.
# Expansion impossible : Aucun motif ne peut s'étendre au-delà de ses limites initiales.
# Contraction impossible : Les motifs ne s'étendent pas forcément indéfiniment, mais ne peuvent jamais se réduire en-deçà de leur limites initiales.
# Expansion et contraction possibles : Seuls ces cas peuvent contenir des vaisseaux.

À l'heure actuelle, les automates qui ont été prouvés Turing-universels appartiennent tous à la 4ème classe. Cependant il n'a pas été démontré que les autres classes ne peuvent pas contenir d'automate Turing-universel puisqu'il existe d'autres façons de transmettre des informations que les vaisseaux.

== Les familles d'automates cellulaires célèbres ==

Il existe de nombreuses familles d'automates cellulaires, mais nous n'en verrons que deux ici.

=== Les automates cellulaires élémentaires ===

Cette famille est la plus simple des automates cellulaires. Ses membres n'ont qu'une dimension et deux états. Le voisinage d'une cellule est composé de celles directement à sa droite et sa gauche et d'elle-même.

Puisque le voisinage prend 3 cellules et que chacune d'elles a un état parmi 2, on a <math>2^3 = 8</math> motifs possibles. Pour chaque motif il y a 2 résultats possibles, donc <math>2^8 = 256</math> règles possibles pour un automate cellulaire de cette famille. Depuis les travaux de S. Wolfram sur cette famille, chacune de ces règles est nommée par le résultat de ses motifs convertit en décimal. Ainsi, la règle suivante est la 103 :
[[Fichier:regle_103.jpg|100px]]
Car
<nowiki>111 110 101 100 011 010 001 000
0 1 1 0 0 1 1 1</nowiki>
Soit <math>01100111_{(2)} = 103_{(10)}</math>

==== Règles intéressantes ====

Certaines de ces 256 règles ont des propriétés particulières. Voici 3 d'entre elles :

===== Règle 22 =====

Lorsque la configuration initiale est composée d'une seule cellule vivante on obtient une approximation du triangle de Sierpiński.

[[Fichier:regle_22.png|500px]]

===== Règle 30 =====

[https://demonstrations.wolfram.com/UsingRule30ToGeneratePseudorandomRealNumbers/#more Selon Wolfram Research], en raison de son comportement local imprévisible et son comportement global chaotique, cet automate cellulaire peut être utilisé comme générateur de nombres pseudo-aléatoires.

[[Fichier:regle_30.png|500px]]

===== Règle 110 =====

Cette règle a été prouvée [[#Universalité Turing|Turing-universelle]].

[[Fichier:regle_110.jpg|500px]]

=== Automates cellulaires type "Vie" ===

Ces automates sont bidimensionnels et utilisent le voisinage de Moore. Leurs règles peuvent toutes s'écrire sous la forme <math>Bx_1,...,x_n/Sy_1,...,y_m</math> avec <math>x</math> le nombre de cellules voisines vivantes nécessaires pour qu'une cellule puisse naître et <math>y</math> le nombre de cellules voisines vivantes nécessaires pour qu'une cellule puisse survivre.

==== Le jeu de la vie de John H. Conway ====

Le jeu de la vie est certainement l'automate cellulaire le plus connu du grand publique. Il a été imaginé par John H. Conway en 1970.

Sa règle est la suivante :
* Une cellule morte nait si elle a exactement 3 cellules voisines vivantes
* Une cellule vivante survie si elle a 2 ou 3 cellules voisines vivantes.
* Dans les autres cas elle sera morte.
Cette règle peut donc s'écrire <math>B3/S23</math>.

Malgré cette règle simple, le jeu de la vie permet d'obtenir une grande variété de type de structures :
* Des structures stables, comme le bloc [[Fichier:stable_block.png|50px]]
* Des structures périodiques, comme le clignotant [[Fichier:periodique_blinker.png|50px]]
* Des vaisseaux, structures mouvantes, comme le planeur [[Fichier:vaisseau_glider.png|50px]]
* Des mathusalems, structures qui vont mettre du temps avant de se stabiliser, comme le pentomino R [[Fichier:mathusalem_pentomino_r.png|50px]]
* Des cannons, structures créant des vaisseaux à un rythme parfois imprévisible, comme le Gosper Glider Gun [[Fichier:canon_gosper_glider_gun.png|50px]]
* Des puffeurs, vaisseaux laissant une trainée de débris, comme le Switch Engine [[Fichier:puffeur_switch_engine.png|50px]]
** Il existe des puffeurs particuliers, les rakes qui agissent à la fois comme des puffeurs et comme des canons, leur débris étant composés de vaisseaux, comme le backrake 1 [[Fichier:rake_backrake_1.png|50px]]
** Il existe également des puffeurs dits spacefillers, dont les débris remplissent tout l'espace d'un motif régulier, comme le Max [[Fichier:spacefiller_max.png|50px]]

Cet automate est [[#Universalité Turing|Turing-universel]] et [[#Universalité intrinsèque|intrinsèquement universel]].

== Universalité ==

On distingue 2 types d'universalité pour les automates cellulaires.

=== Universalité Turing ===

Un automate cellulaire dit Turing-universel a la capacité de simuler une machine de Turing. Il donc capable de réaliser n'importe quel calcul. Plus généralement on accepte comme Turing-universel les automates cellulaires capables de simuler un système Turing-complet.

=== Universalité intrinsèque ===

Un automate cellulaire dit intrinsèquement universel est capable de simuler pas à pas n'importe quel automate de même dimension. L'automate simulateur utilise des groupes de cellules identiques et réguliers, chaque groupe représentant une seule cellule de l'automate simulé. L'automate simulateur peut utiliser plusieurs tours pour simuler une étape de l'automate simulé. Chaque état de l'automate simulé a au moins une configuration correspondante dans l'automate simulateur.

== Remarque sur l'écriture des règles automates cellulaires ==

Il existe de nombreux formats pour donner la règle d'un automate. Pour un [[#Les automates cellulaires élémentaires|automate élémentaire]], on utilisera la concaténation de ses résultats pour chaque motif en binaire ou décimal. Pour un [[#Automates cellulaires type "Vie"|type "Vie"]] on utilisera le format B/S.

Automates cellulaires

2022-05-27T16:58:01Z

Mluque :

Création en cours.

Ce projet avait pour but d'étudier le fonctionnement des automates cellulaires et les caractéristiques particulières que l'on peut retrouver chez certains.

== Définitions ==

=== Définition simple ===

Un automate cellulaire est une grille régulière dont les cases sont appelées « cellules ». Chacune a un « état » parmi un ensemble fini. L'état d'une cellule au « tour » t+1 est définit en fonction de cet état et celui de l'ensemble fini de cellules « voisinage » au tour t, par la « règle » de l'automate cellulaire. Lorsque toutes les cellules ont été mises à jour, on parle de « génération ».

Pour un automate de 2 dimensions les voisinages les plus courants sont celui de von Neumann
[[Fichier:voisinage_von_neumann.png|50px]]
et celui de Moore.
[[Fichier:voisinage_moore.png|50px]] (en vert et rouge les cellules appartenant au voisinage de la cellule rouge.)

=== Définition formelle ===

Un automate cellulaire <math>A</math> est définit par le 4-uplet <math>(d,Q,V,\delta)</math> tel que :
* <math>d</math> est un entier positif, la dimension de <math>A</math>. Son réseau est donc <math>\mathbb{Z}^d</math>
* <math>Q</math> est l'ensemble fini des états des cellules de <math>A</math>
* <math>V \subseteq \mathbb{Z}^d</math>, un sous-ensemble fini du réseau, le voisinage. <math>V = \{v_1,\ldots,v_a\}</math>
* <math>\delta : Q^a \rightarrow Q</math> est la règle locale avec <math>a = |V|</math>
On peut donc définir la fonction globale d'évolution de l'automate <math>F_\delta : Q^{\mathbb{Z}^d} \rightarrow Q^{\mathbb{Z}^d}</math> définit par <math>F_\delta (c) = z \mapsto \delta\bigl(c(z+v_1),\ldots,c(z+v_a)\bigr)</math> pour tout <math>c \in Q^{\mathbb{Z}^d}</math>

== Classifications ==

Bien que les deux classifications qui sont décrites ci-dessous peuvent être retrouvées dans les travaux de certains chercheurs, il est commun de décrire un automate en fonction de leurs caractéristiques particulières sans pour autant les séparer en classes.

=== Classification de Wolfram ===

Stephen Wolfram classe les automates cellulaires en 4 classes selon leur comportement avec des configurations initiales aléatoires :
# Stable : Après un certain nombre de générations, une configuration se répète à l'infini.
# Cyclique : Après un certain nombre de générations, une série de configurations se répètent périodiquement.
# Chaotique : Comportement chaotique et génération de motifs apériodiques.
# Complexe : Apparition de structures complexes possédants divers propriétés comme la capacité de se mouvoir ou de se préserver malgré des perturbations.

L'une des principales critiques de cette classification réside dans son incapacité à déterminer si un automate cellulaire est Turin-universel, venant du fait que Wolfram ne définit la classe qu'à partir de configurations initiales aléatoires, mais pas de structure particulière créée spécifiquement. Malgré cela, cette classification reste la plus étudiée.

[[Fichier:classification_wolfram.png|750px]]

Christopher Langton propose d'envisager ces classes dans un continuum.

[[Fichier:classification_langton.png|250px]]

=== Classification d'Eppstein ===

Il existe une deuxième classification, proposée par David Eppstein. Les automates sont séparés en 4 classes :
# Expansion obligatoire : N'importe quel motif initial s'étend indéfiniment dans toutes les directions.
# Expansion impossible : Aucun motif ne peut s'étendre au-delà de ses limites initiales.
# Contraction impossible : Les motifs ne s'étendent pas forcément indéfiniment, mais ne peuvent jamais se réduire en-deçà de leur limites initiales.
# Expansion et contraction possibles : Seuls ces cas peuvent contenir des vaisseaux.

À l'heure actuelle, les automates qui ont été prouvés Turing-universels appartiennent tous à la 4ème classe. Cependant il n'a pas été démontré que les autres classes ne peuvent pas contenir d'automate Turing-universel puisqu'il existe d'autres façons de transmettre des informations que les vaisseaux.

== Les familles d'automates cellulaires célèbres ==

Il existe de nombreuses familles d'automates cellulaires, mais nous n'en verrons que deux ici.

=== Les automates cellulaires élémentaires ===

Cette famille est la plus simple des automates cellulaires. Ses membres n'ont qu'une dimension et deux états. Le voisinage d'une cellule est composé de celles directement à sa droite et sa gauche et d'elle-même.

Puisque le voisinage prend 3 cellules et que chacune d'elles a un état parmi 2, on a <math>2^3 = 8</math> motifs possibles. Pour chaque motif il y a 2 résultats possibles, donc <math>2^8 = 256</math> règles possibles pour un automate cellulaire de cette famille. Depuis les travaux de S. Wolfram sur cette famille, chacune de ces règles est nommée par le résultat de ses motifs convertit en décimal. Ainsi, la règle suivante est la 103 :
[[Fichier:regle_103.jpg|100px]]
Car
<nowiki>111 110 101 100 011 010 001 000
0 1 1 0 0 1 1 1</nowiki>
Soit <math>01100111_{(2)} = 103_{(10)}</math>

==== Règles intéressantes ====

Certaines de ces 256 règles ont des propriétés particulières. Voici 3 d'entre elles :

===== Règle 22 =====

Lorsque la configuration initiale est composée d'une seule cellule vivante on obtient une approximation du triangle de Sierpiński.

[[Fichier:regle_22.png|500px]]

===== Règle 30 =====

[https://demonstrations.wolfram.com/UsingRule30ToGeneratePseudorandomRealNumbers/#more Selon Wolfram Research], en raison de son comportement local imprévisible et son comportement global chaotique, cet automate cellulaire peut être utilisé comme générateur de nombres pseudo-aléatoires.

[[Fichier:regle_30.png|500px]]

===== Règle 110 =====

Cette règle a été prouvée [[#Turing-universelle|Turing-universelle]].

[[Fichier:regle_110.jpg|500px]]

=== Automates cellulaires type "Vie" ===

Ces automates sont bidimensionnels et utilisent le voisinage de Moore. Leurs règles peuvent toutes s'écrire sous la forme <math>Bx_1,...,x_n/Sy_1,...,y_m</math> avec <math>x</math> le nombre de cellules voisines vivantes nécessaires pour qu'une cellule puisse naître et <math>y</math> le nombre de cellules voisines vivantes nécessaires pour qu'une cellule puisse survivre.

==== Le jeu de la vie de John H. Conway ====

Le jeu de la vie est certainement l'automate cellulaire le plus connu du grand publique. Il a été imaginé par John H. Conway en 1970.

Sa règle est la suivante :
* Une cellule morte nait si elle a exactement 3 cellules voisines vivantes
* Une cellule vivante survie si elle a 2 ou 3 cellules voisines vivantes.
* Dans les autres cas elle sera morte.
Cette règle peut donc s'écrire <math>B3/S23</math>.

Malgré cette règle simple, le jeu de la vie permet d'obtenir une grande variété de type de structures :
* Des structures stables, comme le bloc [[Fichier:stable_block.png|50px]]
* Des structures périodiques, comme le clignotant [[Fichier:periodique_blinker.png|50px]]
* Des vaisseaux, structures mouvantes, comme le planeur [[Fichier:vaisseau_glider.png|50px]]
* Des mathusalems, structures qui vont mettre du temps avant de se stabiliser, comme le pentomino R [[Fichier:mathusalem_pentomino_r.png|50px]]
* Des cannons, structures créant des vaisseaux à un rythme parfois imprévisible, comme le Gosper Glider Gun [[Fichier:canon_gosper_glider_gun.png|50px]]
* Des puffeurs, vaisseaux laissant une trainée de débris, comme le Switch Engine [[Fichier:puffeur_switch_engine.png|50px]]
** Il existe des puffeurs particuliers, les rakes qui agissent à la fois comme des puffeurs et comme des canons, leur débris étant composés de vaisseaux, comme le backrake 1 [[Fichier:rake_backrake_1.png|50px]]
** Il existe également des puffeurs dits spacefillers, dont les débris remplissent tout l'espace d'un motif régulier, comme le Max [[Fichier:spacefiller_max.png|50px]]

Fichier:Vaisseau glider.png

2022-05-27T16:56:47Z

Mluque : Structure de type vaisseau

Structure de type vaisseau

Fichier:Mathusalem pentomino r.png

2022-05-27T16:56:13Z

Mluque : Structure de type mathusalem

Structure de type mathusalem

Fichier:Rake backrake 1.png

2022-05-27T16:51:13Z

Mluque : Structure de type rake

Structure de type rake

Fichier:Puffeur switch engine.png

2022-05-27T16:46:02Z

Mluque : Structure de type puffeur

Structure de type puffeur

Fichier:Stable block.png

2022-05-27T16:45:48Z

Mluque : Structure de type stable

Structure de type stable

Fichier:Periodique blinker.png

2022-05-27T16:45:26Z

Mluque : Structure de type périodique

Structure de type périodique

Fichier:Canon gosper glider gun.png

2022-05-27T16:26:46Z

Mluque : Structure de type canon

Structure de type canon

Fichier:Spacefiller max.png

2022-05-27T16:25:14Z

Mluque : Structure de type spacefiller

Structure de type spacefiller

Automates cellulaires

2022-05-27T15:39:47Z

Mluque :

Fichier:Voisinage moore.png

2022-05-27T15:28:19Z

Mluque : Voisinage de Moore

Voisinage de Moore

Fichier:Voisinage von neumann.png

2022-05-27T15:27:58Z

Mluque : Voisinage de von Neumann

Voisinage de von Neumann

Fichier:Regle 110.jpg

2022-05-27T14:54:37Z

Mluque : Automate cellulaire élémentaire 110

Automate cellulaire élémentaire 110

Fichier:Regle 30.png

2022-05-27T13:54:00Z

Mluque : Automate cellulaire élémentaire 30

Automate cellulaire élémentaire 30

Fichier:Regle 22.png

2022-05-27T13:53:43Z

Mluque : Automate cellulaire élémentaire 22

Automate cellulaire élémentaire 22

Fichier:Regle 103.jpg

2022-05-27T13:25:54Z

Mluque : Visualisation de la règle élémentaire 103

Visualisation de la règle élémentaire 103

Automates cellulaires

2022-05-27T13:20:12Z

Mluque :

Fichier:Classification langton.png

2022-05-27T13:02:41Z

Mluque : Classification des automates cellulaires de Stephen Wolfram, dans le continuum proposé par Christopher Langton

Classification des automates cellulaires de Stephen Wolfram, dans le continuum proposé par Christopher Langton

Fichier:Classification wolfram.png

2022-05-27T12:47:33Z

Mluque : Classification des automates cellulaires de Stephen Wolfram

Classification des automates cellulaires de Stephen Wolfram

Automates cellulaires

2022-05-27T10:57:10Z

Mluque :

Automates cellulaires

2022-05-26T18:29:46Z

Mluque : Page créée avec « Création en cours. Ce projet avait pour but d'étudier le fonctionnement des automates cellulaires et les caractéristiques particulières que l'on peut retrouver chez c... »