Automates cellulaires - Historique des versions

Mluque le 28 mai 2022 à 09:58

2022-05-28T09:58:44Z

← Version précédente		Version du 28 mai 2022 à 09:58
Ligne 1 :		Ligne 1 :
	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.		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.

Mluque le 28 mai 2022 à 09:58

2022-05-28T09:58:07Z

← Version précédente		Version du 28 mai 2022 à 09:58
Ligne 132 :		Ligne 132 :

	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>]].		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 À ~~venir~~]]		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]]

Mluque le 27 mai 2022 à 17:56

2022-05-27T17:56:56Z

← Version précédente		Version du 27 mai 2022 à 17:56
Ligne 20 :		Ligne 20 :
	* <math>Q</math> est l'ensemble fini des états des cellules de <math>A</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>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>		* <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>		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>

Ligne 131 :		Ligne 131 :
	== Remarque sur l'écriture des règles automates cellulaires ==		== 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.		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 À venir]]

Mluque le 27 mai 2022 à 17:37

2022-05-27T17:37:13Z

@@ Ligne 87 : / Ligne 87 : @@
 ===== Règle 110 =====
-Cette règle a été prouvée [[#Turing-universelle|Turing-universelle]].
+Cette règle a été prouvée [[#Universalité Turing|Turing-universelle]].
 [[Fichier:regle_110.jpg|500px]]
@@ Ligne 114 : / Ligne 114 : @@
 ** 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]]

Mluque le 27 mai 2022 à 16:58

2022-05-27T16:58:01Z

← Version précédente		Version du 27 mai 2022 à 16:58
Ligne 93 :		Ligne 93 :
	=== Automates cellulaires type "Vie" ===		=== Automates cellulaires type "Vie" ===

	Ces automates sont ~~bi-dimensionnels~~ 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.		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 de John H. Conway ====
Ligne 104 :		Ligne 104 :
	* Dans les autres cas elle sera morte.		* Dans les autres cas elle sera morte.
	Cette règle peut donc s'écrire <math>B3/S23</math>.		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]]

Mluque le 27 mai 2022 à 15:39

2022-05-27T15:39:47Z

@@ Ligne 8 : / Ligne 8 : @@
 Un automate cellulaire est une grille régulière dont les cases sont appelées &laquo; cellules &raquo;. Chacune a un &laquo; état &raquo; parmi un ensemble fini. L'état d'une cellule au &laquo; tour &raquo; t+1 est définit en fonction de cet état et celui de l'ensemble fini de cellules &laquo; voisinage &raquo; au tour t, par la &laquo; règle &raquo; de l'automate cellulaire. Lorsque toutes les cellules ont été mises à jour, on parle de &laquo; génération &raquo;.
 === Définition formelle ===
@@ Ligne 56 : / Ligne 61 : @@
 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.
+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 :

Mluque le 27 mai 2022 à 13:20

2022-05-27T13:20:12Z

← Version précédente		Version du 27 mai 2022 à 13:20
Ligne 19 :		Ligne 19 :

	== Classifications ==		== 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 ===		=== Classification de Wolfram ===
Ligne 30 :		Ligne 32 :
	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.		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]]
	[image]

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

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

	=== Classification d'Eppstein ===		=== Classification d'Eppstein ===
Ligne 45 :		Ligne 47 :

	À 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.		À 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.

Mluque le 27 mai 2022 à 10:57

2022-05-27T10:57:10Z

← Version précédente		Version du 27 mai 2022 à 10:57
Ligne 22 :		Ligne 22 :
	=== Classification de Wolfram ===		=== Classification de Wolfram ===

	Stephen Wolfram classe les automates cellulaires en 4 classes selon leur comportement avec des configurations initiales aléatoires:		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.		# 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.		# Cyclique : Après un certain nombre de générations, une série de configurations se répètent périodiquement.
Ligne 28 :		Ligne 28 :
	# 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.		# 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.		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.

	[image]		[image]
Ligne 37 :		Ligne 37 :

	=== Classification d'Eppstein ===		=== 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.

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... »

2022-05-26T18:29:46Z

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... »

Nouvelle page

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 ».

=== 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 ==

=== 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.

[image]

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

[image]

=== Classification d'Eppstein ===

Automates cellulaires - Historique des versions

Mluque le 28 mai 2022 à 09:58

Mluque le 28 mai 2022 à 09:58

Mluque le 27 mai 2022 à 17:56

Mluque le 27 mai 2022 à 17:37

Mluque le 27 mai 2022 à 16:58

Mluque le 27 mai 2022 à 15:39

Mluque le 27 mai 2022 à 13:20

Mluque le 27 mai 2022 à 10:57

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... »

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... »