{"id":1077,"date":"2011-03-21T05:44:26","date_gmt":"2011-03-21T04:44:26","guid":{"rendered":"http:\/\/sciencetonnante.wordpress.com\/?p=1077"},"modified":"2011-03-21T05:44:26","modified_gmt":"2011-03-21T04:44:26","slug":"la-fourmi-de-langton","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2011\/03\/21\/la-fourmi-de-langton\/","title":{"rendered":"La fourmi de Langton"},"content":{"rendered":"<p style=\"text-align:justify;\"><a href=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/escher-ants-e1300654671872.jpg\"><img decoding=\"async\" class=\"alignleft size-thumbnail wp-image-1105 lazyload\" title=\"escher-ants\" data-src=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/escher-ants-e1300654671872.jpg?w=150\" alt=\"\" width=\"150\" height=\"102\" src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" style=\"--smush-placeholder-width: 150px; --smush-placeholder-aspect-ratio: 150\/102;\" \/><\/a>La fourmi de Langton est un petit programme informatique qui d\u00e9crit une fourmi se d\u00e9pla\u00e7ant sur les cases d&rsquo;une grille. Les r\u00e8gles qui r\u00e9gissent le mouvement de la fourmi sont d\u2019une grande simplicit\u00e9, et pourtant son comportement est complexe et tout sauf anodin. Et personne ne comprend vraiment pourquoi\u2026<\/p>\n<h3 style=\"text-align:justify;\">Les r\u00e8gles du jeu<\/h3>\n<p style=\"text-align:justify;\">Pour jouer \u00e0 la fourmi de Langton (du nom de son cr\u00e9ateur Chris Langton) il vous faut une feuille quadrill\u00e9e, un crayon et une gomme. Au d\u00e9part les cases de la grille peuvent \u00eatre blanches ou noires, mais supposons pour commencer qu\u2019elles sont toutes blanches. Mettez une petite fl\u00e8che dans une des cases\u00a0: ce sera votre fourmi, et l\u2019orientation de la fl\u00e8che indiquera sa direction.<\/p>\n<p style=\"text-align:justify;\"><strong>A chaque tour, la fourmi se d\u00e9place selon les r\u00e8gles suivantes <\/strong>:<\/p>\n<ol>\n<li> Si la fourmi est sur une case blanche, elle effectue une rotation vers la gauche; si elle est sur une case noire, elle effectue une rotation vers la droite ;<\/li>\n<li>La fourmi inverse la couleur de la case sur      laquelle elle se trouve (blanc devient noir et r\u00e9ciproquement);<\/li>\n<li>La fourmi avance d\u2019une case dans la direction      de son orientation.<\/li>\n<\/ol>\n<ul style=\"text-align:justify;\"><\/ul>\n<p style=\"text-align:justify;\">Et on recommence. Facile, non\u00a0?<\/p>\n<p style=\"text-align:justify;\"><!--more--><\/p>\n<p style=\"text-align:justify;\">Voici ci-dessous un dessin du premier d\u00e9placement de notre fourmi : on part d&rsquo;une configuration donn\u00e9e (T=0) et on applique les 3 r\u00e8gles du mouvement : rotation, inversion de couleur et d\u00e9placement, et on termine dans la nouvelle configuration (T=1).<\/p>\n<p style=\"text-align:justify;\"><a href=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/langton_mouvement-1.png\"><img decoding=\"async\" class=\"aligncenter size-full wp-image-1079 lazyload\" title=\"langton_mouvement\" data-src=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/langton_mouvement-1.png\" alt=\"\" width=\"576\" height=\"151\" data-srcset=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/langton_mouvement-1.png 576w, https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/langton_mouvement-1-300x79.png 300w\" data-sizes=\"(max-width: 576px) 100vw, 576px\" src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" style=\"--smush-placeholder-width: 576px; --smush-placeholder-aspect-ratio: 576\/151;\" \/><\/a><\/p>\n<p style=\"text-align:justify;\">Si vous \u00eates courageux, prenez votre crayon et votre gomme, et faites avancer la fourmi 5 fois. Le r\u00e9sultat doit \u00eatre semblable \u00e0 celui ci-dessous.<\/p>\n<p style=\"text-align:justify;\"><a href=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/langton_debut-1.png\"><img decoding=\"async\" class=\"aligncenter size-full wp-image-1080 lazyload\" title=\"langton_debut\" data-src=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/langton_debut-1.png\" alt=\"\" width=\"583\" height=\"121\" data-srcset=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/langton_debut-1.png 583w, https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/langton_debut-1-300x62.png 300w\" data-sizes=\"(max-width: 583px) 100vw, 583px\" src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" style=\"--smush-placeholder-width: 583px; --smush-placeholder-aspect-ratio: 583\/121;\" \/><\/a><\/p>\n<p style=\"text-align:justify;\">Rassurez-vous pour la suite, en pratique on ne simule pas l&rsquo;\u00e9volution de la fourmi avec un papier et un crayon, mais avec un (petit) programme informatique. Alors <strong>simulons\u00a0 notre fourmi et voyons ce qu&rsquo;elle dessine avec les cases noires.<\/strong><\/p>\n<h3 style=\"text-align:justify;\">Les phases de la vie de la fourmi<\/h3>\n<p style=\"text-align:justify;\">A vue de nez, rien de bien enthousiasmant dans cette fourmi. Elle ob\u00e9it \u00e0 des r\u00e8gles tr\u00e8s simples et on se dit que son \u00e9volution ne va pas \u00eatre bien passionnante. Et pourtant, quand on la simule pendant quelques milliers de tours, il se passe des choses vraiment \u00e9tonnantes.<\/p>\n<p style=\"text-align:justify;\">En effet, la fourmi va passer par <strong>3 phases vraiment tr\u00e8s diff\u00e9rentes, la phase \u00ab\u00a0sym\u00e9trique\u00a0\u00bb, la phase \u00ab\u00a0chaotique\u00a0\u00bb et la phase \u00ab\u00a0autoroute\u00a0\u00bb<\/strong>.<\/p>\n<p style=\"text-align:justify;\">Au d\u00e9but de son \u00e9volution, la fourmi se balade dans une zone assez limit\u00e9e de la grille, en dessinant des <strong>configurations r\u00e9guli\u00e8res et sym\u00e9triques<\/strong>. En voici quelques exemples (la fourmi est en rouge) :<\/p>\n<p style=\"text-align:justify;\"><a href=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/sym-1.png\"><img decoding=\"async\" class=\"aligncenter size-full wp-image-1081 lazyload\" title=\"sym\" data-src=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/sym-1.png\" alt=\"\" width=\"600\" height=\"185\" data-srcset=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/sym-1.png 600w, https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2011\/03\/sym-1-300x93.png 300w\" data-sizes=\"(max-width: 600px) 100vw, 600px\" src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" style=\"--smush-placeholder-width: 600px; --smush-placeholder-aspect-ratio: 600\/185;\" \/><\/a><\/p>\n<p style=\"text-align:justify;\">Quand on voit ces figures, on peut penser que la fourmi de Langton va passer le restant de son existence \u00e0 dessiner des jolies choses bien sym\u00e9triques. Mais <strong>\u00e0 partir de 500 tours, tout change<\/strong>. Elle se met \u00e0 avoir un <strong>comportement chaotique,<\/strong> en \u00e9largissant son terrain de jeu et en cr\u00e9ant des configurations tr\u00e8s irr\u00e9guli\u00e8res.<\/p>\n<p style=\"text-align:justify;\">Cette phase chaotique dure jusqu\u2019\u00e0 environ 10000 tours, et l\u00e0 le miracle se produit\u00a0: <strong>la fourmi entame la construction d\u2019une autoroute <\/strong>tr\u00e8s r\u00e9guli\u00e8re qui la conduit \u00e0 l\u2019infini.<\/p>\n<p style=\"text-align:justify;\">Voyez par vous-m\u00eame cette vid\u00e9o que j&rsquo;ai r\u00e9alis\u00e9e et qui montre les 12\u00a0000 premiers tours. Observez bien la phase sym\u00e9trique (jusqu&rsquo;\u00e0 500), la phase chaotique (de 500 \u00e0 10000) et vous comprendrez vite \u00e0 la fin de la vid\u00e9o ce que l&rsquo;on appelle l&rsquo;autoroute ! (attention la vid\u00e9o s&rsquo;acc\u00e9l\u00e8re au fur et \u00e0 mesure)<\/p>\n<p style=\"text-align:justify;\">[youtube=http:\/\/www.youtube.com\/watch?v=i8N2xnMm6qE]<\/p>\n<h3 style=\"text-align:justify;\">Le myst\u00e8re de l\u2019autoroute<\/h3>\n<p style=\"text-align:justify;\">L\u2019autoroute est en fait un motif p\u00e9riodique de 104 pas qui se r\u00e9p\u00e8te, et conduit au trac\u00e9 que vous observez sur le film pr\u00e9c\u00e9dent. <strong>Personne ne comprend pourquoi elle appara\u00eet et comment elle peut \u00e9merger du d\u00e9sordre<\/strong> qui caract\u00e9rise la phase chaotique.<\/p>\n<p style=\"text-align:justify;\">Ce qu\u2019il y a de plus perturbant, c\u2019est que m\u00eame si on part d\u2019une grille dont les cases sont colori\u00e9es al\u00e9atoirement en blanc ou en noir, <strong>l\u2019autoroute finit toujours par appara\u00eetre un jour ou l\u2019autre<\/strong>.<\/p>\n<p style=\"text-align:justify;\">C\u2019est encore un probl\u00e8me ouvert de d\u00e9montrer que quelle que soit la configuration initiale, une autoroute appara\u00eet (\u00e0 moins de chercher un contre-exemple, mais aucun n\u2019a \u00e9t\u00e9 trouv\u00e9 \u00e0 ce jour).<\/p>\n<p style=\"text-align:justify;\">Toutefois un pas int\u00e9ressant a \u00e9t\u00e9 franchi : <strong>on peut d\u00e9montrer que la trajectoire de la fourmi est toujours non-born\u00e9e<\/strong>. C&rsquo;est \u00e0 dire que la fourmi finit toujours son parcours \u00e0 l&rsquo;infini&#8230;mais on ne sait pas montrer que c&rsquo;est toujours via une construction d&rsquo;autoroute !<\/p>\n<h3 style=\"text-align:justify;\">G\u00e9n\u00e9raliser la fourmi<\/h3>\n<p style=\"text-align:justify;\">Il existe de nombreuses mani\u00e8res de g\u00e9n\u00e9raliser le jeu de la fourmi de Langton. On peut bien s\u00fbr d\u00e9marrer avec une grille dont certaines cases sont d\u00e9j\u00e0 noires. On peut modifier la topologie de la feuille, et jouer sur un tore au lieu d\u2019un plan infini. On peut aussi changer la nature de la grille, triangulaire ou hexagonale par exemple. On peut \u00e9galement <strong>lancer plusieurs fourmis<\/strong> en m\u00eame temps.<\/p>\n<p style=\"text-align:justify;\">Une autre g\u00e9n\u00e9ralisation fascinante consiste \u00e0 <strong>ajouter d\u2019autres couleurs que le noir et le blanc<\/strong>. Si par exemple on ajoute le rouge, on doit d\u00e9finir la s\u00e9quence des couleurs, par exemple blanc-&gt;noir-&gt;rouge-&gt;blanc, et la rotation associ\u00e9e \u00e0 chaque couleur, par exemple blanc=gauche, noir=droite, rouge=droite. Mais on aurait aussi bien pu choisir rouge=gauche. Et ce choix peut \u00eatre critique pour le comportement global de la fourmi !<\/p>\n<p style=\"text-align:justify;\">Si on joue avec N couleurs, on a donc tout un tas de choix possibles (du genre 2^N) et tous ces choix peuvent conduire \u00e0 des r\u00e9sultats tr\u00e8s tr\u00e8s diff\u00e9rents. Un joli floril\u00e8ge dans la vid\u00e9o ci-dessous, qui montre que d<strong>es r\u00e8gles en apparence tr\u00e8s proches peuvent donner des comportements globaux tr\u00e8s \u00e9loign\u00e9s<\/strong>.<\/p>\n<p style=\"text-align:justify;\">[youtube=http:\/\/www.youtube.com\/watch?v=1X-gtr4pEBU]<\/p>\n<h3 style=\"text-align:justify;\">A quoi sert la fourmi\u00a0?<\/h3>\n<p style=\"text-align:justify;\">La fourmi de Langton est un bel exemple de ce concept un peu flou que tout un tas de monde appelle l\u2019<strong>\u00e9mergence.<\/strong> Il s\u2019agit en gros du fait qu\u2019un syst\u00e8me au comportement \u00e9l\u00e9mentaire simple peut donner lieu \u00e0 un comportement global complexe. On retrouve cette id\u00e9e en informatique, en physique, en biologie ou en sociologie.<\/p>\n<p style=\"text-align:justify;\">La fourmi est donc une sorte de \u00ab forme de\u00a0vie artificielle\u00a0\u00bb, \u00e0 l\u2019instar du <a href=\"http:\/\/fr.wikipedia.org\/wiki\/Jeu_de_la_vie\" target=\"_blank\" rel=\"noopener\">jeu de la vie de Conway<\/a> ou des <a href=\"http:\/\/en.wikipedia.org\/wiki\/Elementary_cellular_automaton\" target=\"_blank\" rel=\"noopener\">automates cellulaires unidimensionnels de Wolfram<\/a>, et dont on peut \u00e9tudier le comportement pour essayer de comprendre comment des formes complexe peuvent \u00e9merger d&rsquo;un syst\u00e8me aux r\u00e8gles \u00e9l\u00e9mentaires si simples.<\/p>\n<p style=\"text-align:justify;\">La fourmi de Langton n&rsquo;a pas encore livr\u00e9 tous ses myst\u00e8res !<\/p>\n","protected":false},"excerpt":{"rendered":"<p>La fourmi de Langton est un petit programme informatique qui d\u00e9crit une fourmi se d\u00e9pla\u00e7ant sur les cases d&rsquo;une grille. Les r\u00e8gles qui r\u00e9gissent le mouvement de la fourmi sont d\u2019une grande simplicit\u00e9, et pourtant son comportement est complexe et tout sauf anodin. Et personne ne comprend vraiment pourquoi\u2026 Les r\u00e8gles du jeu Pour jouer<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[45,4],"tags":[43,44],"class_list":{"0":"post-1077","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-informatique","7":"category-mathematiques","8":"tag-algorithmique","9":"tag-emergence"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/1077","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/comments?post=1077"}],"version-history":[{"count":0,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/1077\/revisions"}],"wp:attachment":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media?parent=1077"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/categories?post=1077"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/tags?post=1077"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}