Jun Liu and Ivan O. Shevchenko’s “Controllability of polynomial systems is undecidable and not recursively enumerable” addresses a foundational question in control theory: can an algorithm determine whether a polynomial control system with rational coefficients is globally controllable? Global controllability means that suitable controls can steer the system from any initial state to any desired final state. The paper revisits a conjecture proposed by Eduardo Sontag in 1988. It asserted that global controllability is undecidable, but that the systems possessing this property nevertheless form a recursively enumerable set. The authors report proving the first claim and disproving the second. The distinction is central. Undecidability means that no algorithm can always terminate and correctly determine whether an arbitrary system in the class is globally controllable. Recursive enumerability is a weaker condition: an algorithm could eventually recognize every controllable system while failing to terminate on some uncontrollable ones. The paper rules out this possibility as well. Thus, there is neither a universal decision procedure nor a universal recognition procedure that eventually confirms every positive instance. The main method is a reduction from a stability problem for polynomial differential equations. For every homogeneous polynomial vector field \(F\) of odd degree with rational coefficients, the authors construct an explicit polynomial control system, \(\Sigma_F\), with exactly one additional state variable. This system is globally controllable if and only if the origin of the autonomous differential equation defined by \(F\) is not globally asymptotically stable. Global asymptotic stability combines stability near the origin with convergence to the origin from every initial condition. The construction therefore translates the failure of this stability property into global controllability. The authors combine this reduction with a recent result establishing that homogeneous polynomial vector fields whose origins are globally asymptotically stable form a recursively enumerable but undecidable set. The complement of such a set cannot also be recursively enumerable, because recognition algorithms for both the set and its complement would yield a decision procedure. By linking controllability to that complement, the reduction establishes both undecidability and non-recursive-enumerability. According to the abstract, both conclusions remain valid for systems consisting of a polynomial drift plus a constant matrix multiplying the control input. The negative results therefore do not depend on allowing arbitrary state-dependent polynomial coupling to the controls. The key quantitative details are structural rather than experimental: the conjecture dates to 1988, the reduction applies to homogeneous vector fields of odd degree, and the constructed control system adds exactly one state variable. The abstract reports no numerical experiments, performance measurements, or explicit bounds on polynomial degrees or numbers of control inputs. Its principal conclusion concerns a fundamental limit on general-purpose algorithms; it does not imply that controllability cannot be established for particular systems or restricted subclasses. This summary is based solely on the supplied title, authors, and abstract of version 1, first submitted on October 19, 2026. The full text is unavailable under the stated access restriction, so the explicit construction, detailed proofs, precise assumptions on controls, and any additional qualifications cannot be assessed.
When No Algorithm Can Recognize Every Controllable System
Can a computer determine whether a dynamical system can be steered from any starting point to any desired destination? For polynomial control systems with rational coefficients, Jun Liu and Ivan O. Shevchenko report a striking answer: no general algorithm can always solve this problem. More surprisingly, there is not even a universal algorithm that eventually confirms every system for which the answer is yes.
Their paper, “Controllability of polynomial systems is undecidable and not recursively enumerable,” addresses a foundational limit in control theory. Its contribution is not a faster computational method, but a demonstration that certain ambitions for general-purpose automation are impossible.
What Global Controllability Means
A control system describes how a state changes over time under both its own dynamics and externally chosen inputs. Global controllability means that suitable inputs can move the system from any initial state to any target state. The word “global” matters: the property must hold throughout the state space, not merely near a particular operating point.
The paper considers systems described by polynomials with rational coefficients. These ingredients admit finite, exact descriptions, making it natural to ask whether a computer could examine each description and determine whether global controllability holds.
The authors’ reported result says that no algorithm can do this correctly for every system in the class while always terminating. This is an impossibility in principle, rather than a claim that existing software is too slow.
Beyond Undecidability
The paper revisits a conjecture dating to 1988. That conjecture proposed that global controllability was undecidable, but that controllable systems nevertheless formed a recursively enumerable set. Liu and Shevchenko report proving the first claim and disproving the second.
Deciding versus recognizing
The distinction between these two computational tasks is crucial:
- A decision procedure must eventually stop on every input and correctly answer either yes or no.
- A recognition procedure need only eventually confirm every positive instance. On negative instances, it may run forever.
Recursive enumerability corresponds to the second, weaker possibility. If controllable systems were recursively enumerable, an algorithm could eventually recognize every controllable system, even without reliably identifying uncontrollable ones.
The reported result rules out that fallback. There is no universal procedure that is guaranteed eventually to confirm every positive instance without incorrectly accepting negative ones. The obstacle therefore goes beyond the absence of a dependable yes-or-no test.
The Bridge from Stability to Control
The proof strategy connects controllability to a different property: global asymptotic stability. For an autonomous differential equation, global asymptotic stability of the origin combines two requirements. Trajectories starting sufficiently close to the origin remain close, and trajectories from every initial condition converge to it.
The authors begin with a homogeneous polynomial vector field of odd degree and rational coefficients. From it, they construct an explicit polynomial control system with exactly one additional state variable.
The central equivalence is that the constructed system is globally controllable precisely when the original vector field’s origin is not globally asymptotically stable. In other words, the construction turns failure of a stability property into success of a controllability property.
This is a reduction: a way to translate one mathematical problem into another while preserving the answer through a specified relationship. If a universal controllability algorithm existed, the translation would let it resolve questions about the original stability problem.
Why Recognition Is Impossible Too
The reduction draws on a recent result establishing that homogeneous polynomial vector fields whose origins are globally asymptotically stable form a recursively enumerable but undecidable set.
A basic computational principle then supplies the decisive step. If both a set and its complement were recursively enumerable, one could run their recognition procedures in parallel. Every input belongs to one side, so one procedure would eventually confirm membership. That would produce a decision algorithm.
Because the stability set is undecidable, its complement cannot also be recursively enumerable. The authors’ construction links precisely that complement to global controllability. Consequently, a universal recognizer for controllable systems would imply a recognizer for a set that cannot have one.
What the Result Does—and Does Not—Mean
According to the abstract, both impossibility conclusions remain valid when the systems consist of a polynomial drift plus a constant matrix multiplying the control input. The result therefore does not depend on allowing arbitrary state-dependent polynomial coupling between states and controls.
These findings do not mean that controllability cannot be proved for individual systems, or that useful algorithms cannot exist for restricted subclasses. They rule out universal methods covering every system in the stated class. Specialized analysis and computational tools can still be valuable.
This article is based solely on the supplied title, authors, and abstract of version 1, first submitted on October 19, 2026. The full text was unavailable under the stated access restriction, so the explicit construction, detailed proofs, precise control assumptions, and further qualifications could not be assessed. Within that scope, the message is clear: global controllability has fundamental limits not only on automated decision-making, but also on automated recognition.
