Controllability of polynomial systems is undecidable and not recursively enumerable

L’article de Jun Liu et Ivan O. Shevchenko, intitulé « Controllability of polynomial systems is undecidable and not recursively enumerable », examine les limites des méthodes algorithmiques permettant de déterminer la contrôlabilité globale des systèmes de commande polynomiaux à coefficients rationnels. Déposé sur arXiv le 19 octobre 2026 dans sa première version, il répond à une conjecture formulée par Eduardo Sontag en 1988. Celle-ci comportait deux affirmations : la contrôlabilité globale serait indécidable, mais les systèmes contrôlables formeraient néanmoins un ensemble récursivement énumérable. Les auteurs annoncent démontrer la première et réfuter la seconde. La contrôlabilité globale désigne la possibilité de conduire un système de tout état initial à tout état final au moyen d’une commande admissible. Son indécidabilité signifie qu’aucun algorithme général ne peut déterminer correctement, en un temps fini pour chaque système polynomial donné, si cette propriété est satisfaite. La question de l’énumérabilité récursive est plus subtile : à défaut de décider tous les cas, pourrait-on reconnaître tous les systèmes contrôlables par une procédure qui terminerait pour chacun d’eux, mais pourrait ne jamais terminer pour les systèmes non contrôlables ? Le résultat annoncé exclut également cette possibilité. La démonstration repose sur une réduction reliant la contrôlabilité à la stabilité d’un système différentiel sans commande. À partir de tout champ de vecteurs polynomial homogène de degré impair, à coefficients rationnels, les auteurs construisent explicitement un système de commande polynomial comportant une seule variable d’état supplémentaire. Cette construction établit une équivalence décisive : le système obtenu est globalement contrôlable si et seulement si l’origine du système différentiel initial n’est pas globalement asymptotiquement stable. Elle transforme ainsi une question de non-stabilité globale en une question de contrôlabilité globale. Pour en tirer les conséquences algorithmiques, les auteurs s’appuient sur un résultat récent, cité dans le résumé : les champs polynomiaux homogènes dont l’origine est globalement asymptotiquement stable forment un ensemble récursivement énumérable, mais indécidable. Le complément d’un tel ensemble ne peut pas être lui-même récursivement énumérable. En effet, si les deux ensembles disposaient d’une procédure de reconnaissance, l’exécution parallèle de ces procédures permettrait de décider chaque cas. La réduction transfère cette impossibilité aux systèmes polynomiaux globalement contrôlables, établissant à la fois l’indécidabilité du problème et la non-énumérabilité récursive de ses instances positives. La portée du résultat dépasse les systèmes polynomiaux dont la dépendance à la commande est générale. Les auteurs annoncent les mêmes conclusions pour des systèmes dont la dynamique est la somme d’une dérive polynomiale et d’un terme de commande défini par une matrice constante. Les obstacles algorithmiques persistent donc dans cette classe plus restreinte. Ils concernent toutefois l’existence d’une méthode universelle et n’excluent pas des critères efficaces pour certaines sous-classes ou certains systèmes particuliers. Cette synthèse repose exclusivement sur le titre, les noms des auteurs et le résumé fournis, le texte intégral n’étant pas accessible dans le cadre indiqué. Elle ne permet donc pas de préciser la construction, les hypothèses techniques relatives aux commandes, les démonstrations ou les éventuels exemples. Les résultats présentés sont théoriques : le résumé ne rapporte ni expériences numériques ni mesures de performance.

Contrôlabilité des systèmes polynomiaux : une limite fondamentale des algorithmes

Peut-on toujours déterminer, par un calcul, si un système dynamique peut être conduit de n’importe quel état initial à n’importe quel état final ? Cette question touche au cœur de la théorie de la commande. Dans leur article « Controllability of polynomial systems is undecidable and not recursively enumerable », Jun Liu et Ivan O. Shevchenko annoncent une réponse négative pour les systèmes de commande polynomiaux à coefficients rationnels. Leur résultat va même plus loin : aucune procédure générale ne peut reconnaître tous les systèmes globalement contrôlables en garantissant de terminer sur chacun d’eux.

Déposé sur arXiv le 19 octobre 2026 dans sa première version, ce travail s’attaque à une conjecture formulée en 1988. Selon le résumé fourni, il en confirme une partie et en réfute une autre. Voici ce que ces conclusions signifient, comment elles s’articulent et pourquoi elles comptent.

Que signifie « contrôler » un système ?

Un système de commande décrit l’évolution d’un état sous l’effet de sa dynamique propre et d’actions extérieures. Dans un système polynomial, les équations qui gouvernent cette évolution sont polynomiales. Les coefficients rationnels permettent de représenter exactement les données du problème par une description finie.

La contrôlabilité globale est une exigence forte : quels que soient l’état de départ et l’état d’arrivée, il doit exister une commande admissible permettant de passer du premier au second. Il ne suffit donc pas de pouvoir déplacer légèrement le système ou d’atteindre certaines régions de son espace d’états.

La question algorithmique consiste à demander si une méthode unique pourrait examiner tout système de cette classe et répondre correctement, en un temps fini, à la question : est-il globalement contrôlable ? Les auteurs annoncent que cette méthode universelle n’existe pas.

Deux impossibilités, de force différente

L’indécidabilité : impossible de trancher tous les cas

Un problème est indécidable lorsqu’aucun algorithme ne peut donner une réponse correcte et terminer pour toutes ses instances. Cela ne signifie pas que chaque système est impossible à analyser. Cela signifie qu’aucune procédure générale ne couvre tous les systèmes polynomiaux concernés avec une garantie de succès.

La non-énumérabilité récursive : impossible de reconnaître tous les cas positifs

On pourrait espérer une garantie plus modeste : une procédure qui terminerait avec une réponse positive pour chaque système contrôlable, quitte à fonctionner indéfiniment sur certains systèmes non contrôlables. C’est cette possibilité que traduit l’énumérabilité récursive de l’ensemble des instances positives.

Le résultat annoncé exclut aussi cette solution. Il n’existe donc pas de procédure universelle de reconnaissance qui soit assurée de finir pour tous les systèmes globalement contrôlables. La conjecture de 1988 associait l’indécidabilité à cette possibilité de reconnaissance partielle : le travail confirme la première affirmation, mais réfute la seconde.

Le pont entre stabilité et contrôlabilité

La démonstration repose sur une réduction : une transformation explicite qui relie deux problèmes mathématiques. Le point de départ est un système différentiel sans commande, décrit par un champ de vecteurs polynomial homogène de degré impair, à coefficients rationnels.

À partir de ce champ, les auteurs construisent un système de commande polynomial en ajoutant une seule variable d’état. La propriété essentielle de cette construction est une équivalence : le nouveau système est globalement contrôlable si et seulement si l’origine du système initial n’est pas globalement asymptotiquement stable.

La stabilité asymptotique globale décrit, schématiquement, une origine stable vers laquelle convergent les trajectoires depuis tout état initial. La construction transforme donc une question de non-stabilité globale en une question de contrôlabilité globale. Ce lien permet de transférer une impossibilité algorithmique d’un domaine à l’autre.

Pourquoi cette réduction suffit-elle ?

Les auteurs s’appuient sur un résultat récent cité dans le résumé : dans la classe considérée, l’ensemble des champs dont l’origine est globalement asymptotiquement stable est récursivement énumérable, mais indécidable.

Le raisonnement se déroule alors en trois étapes :

• Les cas globalement asymptotiquement stables possèdent une procédure de reconnaissance, sans qu’il existe de méthode décidant tous les cas.
• Les cas qui ne présentent pas cette stabilité ne peuvent pas, eux aussi, posséder une procédure générale de reconnaissance. Sinon, lancer les deux procédures en parallèle permettrait de décider chaque cas.
• La réduction transforme précisément ces cas de non-stabilité en systèmes globalement contrôlables. Une reconnaissance universelle de ces derniers rendrait donc possible une reconnaissance déjà exclue.

La non-énumérabilité récursive des systèmes contrôlables implique également leur indécidabilité : tout ensemble décidable serait nécessairement reconnaissable.

Une limite générale, pas un abandon des méthodes pratiques

La portée annoncée ne se limite pas aux systèmes présentant une dépendance générale à la commande. Les mêmes conclusions valent pour une classe plus restreinte, où la dynamique est la somme d’une dérive polynomiale et d’un terme de commande défini par une matrice constante.

Ces résultats n’interdisent ni les critères efficaces pour certaines sous-classes, ni l’analyse de systèmes particuliers. Ils fixent plutôt une frontière : aucune méthode algorithmique universelle ne peut offrir les garanties décrites pour toute la classe étudiée.

Cette présentation repose exclusivement sur les informations bibliographiques et le résumé fournis. Sans accès au texte intégral, elle ne précise ni la construction exacte, ni les hypothèses techniques sur les commandes, ni les démonstrations détaillées. Le résultat annoncé est théorique ; le résumé ne rapporte aucune expérience numérique ni mesure de performance.