Tag

Algorithmique

Browsing

Les cellules de notre organisme sont capables de se répliquer à l’identique, et ça nous parait bien naturel. Et pourtant, la question de l’auto-réplication est loin d’être évidente.

Pour s’en rendre compte, essayez-vous au petit défi suivant : écrire un programme informatique qui produise en sortie son propre code source. Ça paraît simple, non ?

Vous allez voir que ça n’est pas le cas, et que l’écriture d’un tel programme nécessite de se creuser un peu les méninges.

La fourmi de Langton est un petit programme informatique qui décrit une fourmi se déplaçant sur les cases d’une grille. Les règles qui régissent le mouvement de la fourmi sont d’une grande simplicité, et pourtant son comportement est complexe et tout sauf anodin. Et personne ne comprend vraiment pourquoi…

Les règles du jeu

Pour jouer à la fourmi de Langton (du nom de son créateur Chris Langton) il vous faut une feuille quadrillée, un crayon et une gomme. Au départ les cases de la grille peuvent être blanches ou noires, mais supposons pour commencer qu’elles sont toutes blanches. Mettez une petite flèche dans une des cases : ce sera votre fourmi, et l’orientation de la flèche indiquera sa direction.

A chaque tour, la fourmi se déplace selon les règles suivantes :

  1. 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 ;
  2. La fourmi inverse la couleur de la case sur laquelle elle se trouve (blanc devient noir et réciproquement);
  3. La fourmi avance d’une case dans la direction de son orientation.

    Et on recommence. Facile, non ?