Discussion :

[Andariel]

Bonjour,

Je m'explique :
Je cherche à faire passer un algorithme du langage turing vers le système du "jeu de la vie". Je sais que théoriquement la chose est possible mais de là à avoir la moindre idée pour comment le faire de façon pratique ...

Merci d'avance de votre aide.

[Trap D]

Tu pourrais donner un peu plus de détails ???
Le langage de Turing, c'est quoi, les bandes infinies avec des 0 et des 1 ??
Le "système" du jeu de la vie c'est quoi ?? (je connais le jeu, mais le système....)

[Andariel]

Oui, c'est un peu ça.
En gros, la machine de turing est une machine qui utilise un ruban divisé en cases contenant des symbloes, pouvant possèder plusieurs états et qui suit un programme déterminé afin de réalisé n'importe quel algorithme.

Lis ça sinon, ce sera sans doute plus clair ^^
http://fr.wikipedia.org/wiki/Machine_de_Turing

Pour le jeu de la vie, c'est un automate cellulaire (rien à voir avec des humoristes ).
C'est un façon de paver une surface divisée en cellules ainsi :

Si une cellule est vide (dite morte) :

• Si elle est entourée de 3 cellules pleines, elle se remplie à la prochaine étape
• Sinon, elle reste vide

Si une cellule est pleine (dite vivante) :

• Si elle possède 2 ou 3 voisins vivants, elle reste vivante à la prochaine étape
• Sinon, elle passe à l'état 'mort' à la prochaine étape.

Avec des animations :
http://fr.wikipedia.org/wiki/Jeu_de_la_vie
Et pour essayer :
http://www.univ-lemans.fr/enseigneme...rs/conway.html

Voilà... j'espère vous avoir informé suffisament...

[Trap D]

Ton problème serait donc, si j'ai bien compris, comment écrire le jeu de la vie sur une Machine de Turing, c'est ça ?

[Andariel]

Presque ^^
En fait c'est l'opération inverse :
Je cherche à retranscrire une méthode de la machine de turing dans le jeu de la vie.
En théorie c'est possible ,si on dispose d'une quatitée infinie de cellules, de retranscrire n'importe quel programme en turing vers le jeu de la vie. Je sais que c'est un problème de configuration de départ (en plaçant correctement les cellules de départ, on fait tourner les étapes comme on ferait tourner un algo et paf ! ca marche ) Sauf que c'est théorique et là je nage un peu pour arriver à transcrire...

[Trap D]

Dommage, j'avais espéré que ce soit le contraire, car là, je n'ai absolument aucune idée

[Andariel]

En vérité, je ne demande pas non plus une méthode globale ! Simplement un exemple que je pourrait *erm* montrer à mes profs
Parceque turing j'ai compris, le jeu de la vie aussi mais ils se sont mis en tête que je pouvais transcrire un algo x de l'un vers l'autre. Et sans exemple, je sais qu'ils ne me croiront pas sur parole ...
J'ai vraiment tout essayé mais là je doit avouer que je suis à cours d'idées...

[Andariel]

C'est une consiration ou vraiment personne ne trouve le solution ?
J'ai essayé différentes choses avec différents algorithmes (crible d'érathostène, division euclidienne, etc...) mais je doit avouer que je séche.
Celui qui me semble le plus simple à mettre en oeuvre est celui-là (que j'ai repris du lien vers wikipédia traitant du turing) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 Anc. Sym. Sym.      Nouv.  
 état lu   écr. Mouv. état    
 - - - - - - - - - - - -     
  e1  1  ->  0   D    e2      
  e2  1  ->  1   D    e2      
  e2  0  ->  0   D    e3      
  e3  1  ->  1   D    e3
  e3  0  ->  1   G    e4     
  e4  1  ->  1   G    e4
  e4  0  ->  0   G    e5
  e5  1  ->  1   G    e5
  e5  0  ->  1   D    e1

(Ecrit en turing, )
Cet algorithme transforme une série de n 1 en deux séries de n 1 séparée par un 0. Par exemple 1111 devient 111101111
Ca pourrait être possible de le transcrire dans un jeu de la vie, parceque après quelques essais j'obtient des résultats avec des lignes de n pleines.

Le but serait de passer de

00000000
00011000
00000000

à

0000000
0110110
0000000

Mais j'ai alors quantitée de problèmes étant donné que ce n'est pas une structure stable... des idées ?

[Andariel]

Euhh... toujours pas ?