Syst\`emes aux d\'eriv\'ees constantes par morceaux et leurs propri\'et\'es algorithmiques

On consid\`ere un nombre fini de poly\`edres dans $R^n$. Pour chaque poly\`edre on fixe un vecteur constant. Ainsi on obtient un champ vectoriel constant par morceaux. On \'etudie les propri\'et\'es algorithmiques de l'\'equation diff\'erentielle ordinaire qui correspond \`a ce champ. Le probl\`eme d'accessibilit\'e pour ce genre de syst\`emes (not\'es CPM - constants par morceaux) dans $R^2$ est decidable (Maler--Pnueli). Les r\'esultats principaux de l'expos\'e sont les suivants~: un CPM d\'eterministe dans $R^3$ peut simuler (dans un sens pr\'ecis) n'importe quel automate fini non-d\'eterministe, une machine \`a pile\,; un CPM d\'eterministe dans $R^3$ peut simuler n'importe quelle machine de Turing\,; donc le probl\`eme d'accessibilit\'e pour les CPM dans $R^3$ est non-d\'ecidable\,; et ce n'est pas tout --- un CPM peut faire un nombre infini de ``pas'' dans un temps fini, voil\`a pourquoi les CPM peuvent faire beaucoup plus que simuler les machines de Turing\dots Les r\'esultats pr\'esent\'es ont \'et\'e obtenus en coop\'eration avec O.Maler (VERIMAG)