Emergence dans les modèles de calcul – EMC

Les modèles de calcul sont par nature liés aux systèmes complexes: on a compris récemment que dans de nombreux systèmes complexes les aspects liés à la puissance calculatoire jouaient un rôle crucial dans l'imprédictabilité du système, et aussi l'analyse de son éventuel caractère chaotique. Réciproquement, on observe depuis toujours avec une certaine surprise le comportement complexe de l'évolution temporelle de modèles de calcul, quelques fois en exhibant une petite machine dont le comportement semble très étrange, et d'autres fois en s'intéressant au comportement global de classes de machines. Dans ce projet, nous cherchons à comprendre ces observations dans un cadre formel, typiquement issu de l'informatique théorique, mais pas uniquement: les modèles que nous considérons vont des machines de Turing pour modéliser les aspect purement calculatoires, aux pavages qui modélisent les aspects géométriques du calcul, jusqu'aux automates cellulaires dont les propriétés évolutives combinent des aspects temporels et d'autres plus géométriques. Il est nécessaire nous semble-t-il de modéliser proprement la ou les notions d'émergence, notions qui viennent del'observation de phénomènes qui sembles analogues dans des contextes différents. Cette analogie est difficile à définir et encore plus difficile à analyser. Ainsi, notre projet présente deux aspects profondément connectés: l'étude des aspects calculatoires de l'émergence d'une part, et d'un autre coté l'étude dynamique de l'émergence elle-même.