15 mars 2012
Les modèles de calculs actuels de l’informatique sont des modèles digitaux: ils travaillent sur des bits, ou sur des symboles en nombre fini. Il y a de nombreux modèles, mais la thèse de Church-Turing (et ses variantes physique, ou effective) stipule que tous les modèles digitaux, dès qu’ils sont suffisamment puissants, sont équivalents. On peut aussi considérer des modèles analogiques ou avec des aspects analogiques.
À vrai dire, chaque époque a ses systèmes de calculs et ses questions de calculabilité: au 19e siècle, l’essor des communications a mené à se poser des questions sur la possibilité de calculer certains mouvements. Au début du 20e siècle, l’apparition de dispositifs informatiques mécaniques pour résoudre des problèmes d’ingénierie a mené à se poser des questions sur la possibilité de calculer mécaniquement certaines fonctions. Au 21e siècle, l’essor des télécommunications fait que certains systèmes distribués actuels se décrivent et se programment aussi avec des aspects analogiques: par exemple, la grande taille de certains systèmes fait que leur description naturelle devient une description statistique et thermodynamique. Chacun de ces systèmes se programme. Chacun de ces systèmes n’est pas clairement couvert par la calculabilité et la complexité classique moderne, qui parle de modèles comme les machines de Turing. Certains de ces systèmes ont toutefois une théorie très riche, avec des notions par exemple d’universalité, différentes, mais tout aussi utiles que celles de la calculabilité moderne.
L’objectif de cet exposé sera d’introduire quelques un de ces modèles, et de présenter ce que l’on sait sur leur puissance de calculs.
Olivier Bournez (Ecole Polytechnique)
