Au cours du vingtième siècle, les logiciens ont fait du calcul un objet théorique, cherchant à en fixer les limites (quels problèmes sont calculables?) et la difficulté (à quelle classe de complexité appartient un problème?). Au cours des dernières décennies, de nombreux auteurs se sont interrogés sur la possibilité de conférer un sens physique à ces résultats mathématiques : en quoi les limites posées par les logiciens sont-elles pertinentes pour tout système physique effectuant un calcul? Je tâcherai de montrer la difficulté de cette question, et de voir comment bien la poser.
CEA/SPEC/LARSIM