Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 17 Février 2004

La fourmi de Langton: un système indécidable

par Anahí Gajardo (Universidad de Concepción, Chile)

La fourmi de Langton est un systeme dynamique introduit par C. Langton qui essayait de montrer que des regles automatiques simples peuvent donner lieu a des comportements aussi complexes que ceux des organismes vivants. En effet, la fourmi de Langton a une dynamique tres imprevisible et etonnante. Elle a été etudiee par plusieurs chercheurs dans differents contextes: dynamique, physique, combinatoire et informatique. Plusieurs proprietes ont ete prouvees, mais sa caracteristique la plus remarquable est encore un probleme ouvert.

Dans toutes les simulations qui ont ete faites, en partant avec differentes distributions des etats des sommets, il est observe que la fourmi tombe (apres une phase initiale) dans un mouvement periodique tel qu'elle avance constamment dans une direction. Mais on ne sait pas encore si cela se produit dans absolument tous les cas.

Dans ce seminaire, on fera un bilan des resultats les plus importants, les outils avec lesquels ce systeme a ete etudie et les conjectures qui resistent encore.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr