Article de Mathiew Cook :
wpmedia.wolfram.com/uploads/s...
J'ai acquis les connaissances nécessaires pour faire cette vidéo lors de mon premier stage de recherche en Master d'informatique théorique qui portait sur la question ouverte de savoir si la règle 54 des automates cellulaires élémentaires était elle aussi Turing universelle. Je n'ai pas réussi à prouver ou réfuter cette hypothèse mais au moins j'ai approfondi mes connaissance en Turing-Universalité et en calculabilité.
Si ça vous intéresse voici mon rapport de stage dans lequel je réexplique (avec beaucoup plus de détail) ce que présente dans cette vidéo : drive.google.com/file/d/1GbHa...
Si vous avez des questions sur le sujet, posez-les-moi en commentaire et j'y répondrais.
Timecode :
0:00 Introduction
0:28 Automates Cellulaires
1:38 Automates Cellulaires Elémentaires
3:14 Machines de Turing
5:50 Machines de Turing Universelles
6:37 Un Automate Cellulaire Universel
9:02 La Règle 110
9:56 Gliders
10:30 Systeme de Gliders Turing Universel
12:34 Preuve de M.Cook
13:15 Indécidabilité et Conclusion
Petit Edit :
à 10:30 j'ai oublié de le préciser mais il faut rajouter une infinité de gliders de directions 0 correspondant au symbole blanc pour avoir la puissance Turing. Une des façon de faire ça avec seulement une entrée finie est de créer des "gliders gun" (des gliders qui créent d'autres gliders) qui génèrent régulièrement des gliders correspondant au symbole blanc.
Oui, ce sont bien des cigales que l'on entend tout au long de la vidéo ( j'habite à Marseille).
Негізгі бет Ғылым және технология Comment la règle 110 des automates cellulaires élémentaire a été prouvée Turing Universelle ?
Пікірлер: 6