Singular differential equations can have non-computable unique solutions
Singular Linear Differential-Algebraic Equations with Constant Coefficients Necessarily Admit Non-Computable Solutions
Computational Complexity
Summary
Usually, mathematicians can compute the exact solution to a certain kind of equation known as a linear differential-algebraic equation (LDAE) when it behaves regularly. This paper shows there are exceptions: for some special 'singular' LDAEs with constant coefficients, even when there is only one solution, it can't be computed by any algorithm forever. The authors prove that these solutions are not just hard to find but mathematically impossible to calculate at certain times, despite the inputs being perfectly computable.
What this means in practice
- •For computational mathematicians: Recognize situations where numerical algorithms for singular LDAEs can never fully succeed, guiding the choice of problems for computation.
- •For control system engineers: Identify when singular LDAEs might yield solutions that cannot be exactly computed, informing design decisions in system modeling and analysis.
A theory result. No direct application yet.
Authors
Holger Boche, Volker Pohl, H. Vincent Poor, Frank H. P. Fitzek
Abstract
If a regular linear differential-algebraic equation has a unique solution, this solution is known to be Turing computable. In contrast, this paper shows that singular linear differential-algebraic equations exhibit fundamentally different computability properties. More precisely, we show that for every linear differential-algebraic equation (LDAE) with constant computable coefficients, there exists a computable input function with strong regularity properties such that the LDAE admits a unique solution, yet this solution is not Turing computable. In fact, the solution is non-computable at certain computable times.