Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 27-06-2017 10:38:13

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 851
Lieu: Seahaven island

Automate cellulaire capriciexu

Hello,

Voici une petite question ouverte (je n'ai pas la réponse) et l'occasion de découvrir un automate cellulaire fascinant "Single rotation reversible bloc cellular automata".

Voici comment il fonctionne:
-On se trouve sur une grille 2D maillage carré.
-Chaque case peut être une cellule vivante ou morte.
-A chaque génération on découpe le grille en bloc 2x2 cellules.
-Si le bloc ne contient qu'une seule cellule vivante on tourne ce bloc de 90 degrés dans le sens des aiguilles d'une montre, sinon on le laisse intacte.
La subtilité: une génération sur deux on utilise pas le même découpage en blocs, voir sur l'image ci dessous: une étape va utiliser le découpage bleu, l’étape suivante le découpage pointillée rouge, puis l’étape suivante de nouveau le bleu, etc...

https://upload.wikimedia.org/wikipedia/commons/thumb/b/b8/Margolus_block_neighborhood.svg/360px-Margolus_block_neighborhood.svg.png

L'ensemble des règles est illustré dans cette petite animation:

https://lh5.googleusercontent.com/-mTAJ1a9hwXQ/UmzYqTP0NRI/AAAAAAAAE6M/fFMvSHjffjQ/w200-h150-no/animation.gif

Cet automate est réellement fascinant pour tout plein de raisons, vous pouvez jetez un œil à ce blog pour en savoir plus.

Et pour le plaisir des yeux vous pouvez regarder cette très belle simulation:



Les questions:

-Sauriez vous trouver des "invariants" dans cet univers? comme des lois de conservation etc....?

-L'univers est extrêmement riche en "spaceships" (structure périodique à une translation près) le blogger ci dessus en a referencé des 100aines qui se forment spontanément, mais ils se déplacent tous soit orthogonalement (vertical horizontal) soit diagonalement (sur les diagonales principales) pas encore vu de spaceship oblique, et vu leur abondance ça cache un truc. La gloire infinie à celui qui prouvera que c'est impossible (ce qui me semble très probable) ou qui trouvera un contre exemple.

PS:
Ici un simulateur en ligne:
http://dmishin.github.io/js-revca/index.html
Si vous désirez coder une simulation vous même, gardez bien en tete qu'il y a trivialement conservation de la matière et que le règles donnent une possibilité de "suivre" chaque cellule (ce qui permet de simuler leur deplacement plus efficacement).

Voici quelques éléments et précisions:

-Il y a trivialement conservation de la population.
-Il y a potentiellement des structures immortelles, par réversibilité des règles elles ne peuvent pas se former. la population des structures immortelles est constante.
-Les règles permettent une traçabilité des cellules, on peut "suivre" leur déplacement, leur attribuer une identité.
-Si on regarde le déplacement d'une cellule, celle ci alterne obligatoirement déplacement horizontal et déplacement vertical.
-Lorsqu'une cellule rentre sur une case, on sait qu'elle n'aura que deux manières d'en sortir.
-Si on colorie l'espace façon damier, une cellule, lorsqu'elle se déplace, alterne la couleur de la case sur laquelle elle se trouve.
-Si une structure du genre spaceship entre en collision avec une autre structure, alors le résultat de la collision ne peut pas être spatialement borné, Ça vient du fait que si il l’était il serait périodique, et que sil était périodique alors ça serait contradictoire avec la réversibilité de cet automate. En pratique: si un planeur rentre un autre planeur ressort.
-Si on regarde un spaceship en particulier, au bout d'une période, l'ensemble a effectue une translation. Ça ne garantit pas a première vu que chaque cellule qui le compose aient effectue cette même translation (car elles peuvent avoir permute de rôle dans le spaceship). Cependant il existe forcement une multiple de la période au bout du quel c'est le cas[i] (que toute les cellules se soient translatée de la même quantité). Ça peut peut-être s'utiliser dans une démo.
[/i]
Voila voila!



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 27-06-2017 10:52:11

Varzmir
Habitué de Prise2Tete
Enigmes résolues : 22
Messages : 17

Automate cellulaire capricieuxx

Je ne connaissais pas cet automate cellulaire ! Ca a l'air vraiment passionnant.
Bon déja, il y a invariance de la "masse" mais je suppose qu'il y a bien plus que ça...smile Je vais m'y pencher plus sérieusement cool
EDIT : Il y a une bijection entre l'étape n et l'étape n+1 ce qui fait qu'on peut remonter le temps ! Du coup on a une sorte de conservation de l'entropie.

 #3 - 27-06-2017 12:13:25

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 851
Lieu: Seahaven island

Automate celulaire capricieux

@Varzmir: Oui il est réversible. il y a conservation de l'information (pas de l'entropie qui, elle augmente). Ça a tout un tas de conséquences: si deux planeurs se collisionnent, alors le nuage issue de la collision ne peut pas rester spatialement borné (sinon il finirait par être périodique et macroscopiquement irréversible, on ne pourrait plus remonter à la collision) en pratique: de toute collision il y a un produit, si un planeur arrive sur un truc: un autre planeur fini par repartir smile

 #4 - 27-06-2017 23:17:41

Varzmir
Habitué de Prise2Tete
Enigmes résolues : 22
Messages : 17

automate xellulaire capricieux

Ah oui super raisonnement ! J'avais remarqué ça en expérimentant mais l'idée de la démonstration par l'absurde (avec l'impossibilité d'un nuage spatialement borné) est géniale ! big_smile Donc ça veut dire que toute figure qui n'est pas immédiatement périodique est non bornée et mène forcément (du moins très probablement) à un planeur.
Concernant l'entropie, je ne suis pas sûr de comprendre pourquoi elle augmente. La conservation de l'information n'est elle pas la marque d'une conservation de l'entropie ? Je ne m'y connais pas beaucoup.
Je pensais également à l'idée d'une invariance du mouvement : le nombre de particules qui bougent de l'étape n à n+1 pourrait être constant (Bon en fait c'est pas le cas).

 #5 - 28-06-2017 09:32:07

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 851
Lieu: Seahaven island

automate cellulaire capricieyx

La conservation de l'information n'est elle pas la marque d'une conservation de l'entropie ?

Nope! Si tu regardes la vidéo de simulation, qui commence avec un carre de cellules aléatoire en son centre, tu peux voir qu'a terme, les choses vont se diluer et polluer l'espace entier. Si tu recommence la même expérience des milliards de fois (tirer des trucs au hasard dans un carre central) tu verras toujours ce phénomène, cette dilution, se produire. L'entropie c'est la notion qu'on construit pour traduire irréversibilité statistique de cette évolution (un état dilué se contracte en un état dense infiniment rarement, un état dense se dilate en un état dilué infiniment souvent) en attribuant par définition, une entropie strictement plus élevée aux états macroscopique vers lequel les choses évoluent statistiquement. Dans le cas de notre vidéo, l'entropie du carré aléatoire initial est strictement plus faible que l'entropie de l’état global en fin de vidéo. Aucun information n'a cependant été crée, car les règles sont réversibles. Je me fais un peu de pub pour la route, je parle d'entropie ici sur ma chaîne: https://www.youtube.com/watch?v=rHIPMHO_tNA

 #6 - 30-06-2017 22:42:23

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 239

Automate cellulaire capriieux

Je remet les 3 messages disparus suite à la maintenance d'hier:
J'avais conjecturé que le système se stabilisait en un système que l'on peut décomposer avec des oscillateurs (périodiques dans le temps) et des spaceships (périodiques dans l'espace et le temps).
Je me demandais donc si il existait d'autre forme d'évolution, comme par exemple deux spaceships s'éloignant l'un de l'autre et s'échangeant un spaceship entre eux.
Je me demandais s'il était également possible d'aboutir sur un système réellement chaotique...

Clydevil m'avait montré le résultat d'un "ping pong" de spaceship, qui permet d'envisager une piste de recherche:
http://dmishin.blogspot.fr/2015/01/new- … ships.html

J'avais posté un propriété que j'avais trouvée, qui peut être intéressante, bien que pas compliquée...
En cherchant dans cette voie, on y arrivera peut être.
http://www.prise2tete.fr/upload/caduk-VaisseauMouvant.PNG
RLE(a mettre dans le buffer):
b2o10b2o$4o8b4o$4o8b4o$b2o10b2o8$7bo$b2o2bobo5b2o$4o3bo4b4o$4o8b4o$b2o10b2o
d'autres dérivés:
$2o6b2o$2o6b2o4$5bo$7bo$5bo$2o5b3o$2o6b2o

b2o8b2o$b2o8b2o7$10bo$13bo$b2o5bo2b2o$b2o8b2o$11bo

6bo$2o4bobo7b2o$2o4bo9b2o

L'idée est de projeter des vaisseau su de petites structures pour en voir le produit, l'objectif étant de construire un cycle avec, l'idéal étant que les vaisseaux déplacent ses structures...

 #7 - 03-07-2017 09:43:30

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 851
Lieu: Seahaven island

Automate celllaire capricieux

Je rajoute les quelques précisions dont j'avais parlé avant le crash, en espérant que ça motive quelqu'un pour démontrer qu'il n'y a pas de planeur oblique (ou trouver un contre exemple):
-Il y a trivialement conservation de la population.
-Il y a potentiellement des structures immortelles, par réversibilité des règles elles ne peuvent pas se former. la population des structures immortelles est constante.
-Les règles permettent une traçabilité des cellules, on peut "suivre" leur déplacement, leur attribuer une identité.
-Si on regarde le déplacement d'une cellule, celle ci alterne obligatoirement déplacement horizontal et déplacement vertical.
-Lorsqu'une cellule rentre sur une case, on sait qu'elle n'aura que deux manières d'en sortir.
-Si on colorie l'espace façon damier, une cellule, lorsqu'elle se déplace, alterne la couleur de la case sur laquelle elle se trouve.
-Si une structure du genre spaceship entre en collision avec une autre structure, alors le résultat de la collision ne peut pas être spatialement borné, Ça vient du fait que si il l’était il serait périodique, et que sil était périodique alors ça serait contradictoire avec la réversibilité de cet automate. En pratique: si un planeur rentre un autre planeur ressort.
-Si on regarde un spaceship en particulier, au bout d'une période, l'ensemble a effectue une translation. Ça ne garantit pas a première vu que chaque cellule qui le compose aient effectue cette même translation (car elles peuvent avoir permute de rôle dans le spaceship). Cependant il existe forcement une multiple de la période au bout du quel c'est le cas (que toute les cellules se soient translatée de la même quantité). Ça peut peut-être s'utiliser dans une démo.

Voila voila!

 #8 - 17-07-2017 23:40:13

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3332

automate cellulaire capricirux

Je ne sais pas si c'est ce que tu proposes de chercher. Comme "figure invariante" celle-ci est périodique et d'entropie constante.


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #9 - 23-07-2017 12:34:56

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 851
Lieu: Seahaven island

Automate celllaire capricieux

@shadok: Je cherche des quantites invariantes, par exemple "le nombre de cellules" est une quantite qui est conservee tout au long de la simulation.

 #10 - 23-07-2017 12:37:14

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 851
Lieu: Seahaven island

automate cellulaiee capricieux

@Tout le monde: Pour faire naitre peut etre une vocation a chercher d´avantage ces questions je propose ma derniere video ou je parle de cet automate smile

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
Automate cellulaire par Ebichu
24-02-2016 Enigmes Mathématiques
P2T
13 pièces par Nombrilist
16-10-2009 Enigmes Mathématiques
P2T
C'est l'heure 3 par scarta
29-04-2011 Enigmes Mathématiques
P2T
La foire aux disques par schaff60
23-02-2010 Enigmes Mathématiques
P2T
26-06-2012 Enigmes Mathématiques
P2T
Triangles par Anapurna
19-09-2009 Enigmes Mathématiques
P2T
Calcul premier par franck9525
06-10-2010 Enigmes Mathématiques
P2T
Le concours LEMURIEN par Promath-
02-02-2012 Enigmes Mathématiques
P2T
Pile ou face ? par Milou_le_viking
02-12-2009 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete