Computational unsolvability of domains of attraction of nonlinear systems

Zhong, Ning

doi:10.1090/S0002-9939-09-09851-7

Computational unsolvability of domains of attraction of nonlinear systems
HTML articles powered by AMS MathViewer

by Ning Zhong PDF

Proc. Amer. Math. Soc. 137 (2009), 2773-2783 Request permission

Abstract:

Let $S$ be the domain of attraction of a computable and asymptotically stable hyperbolic equilibrium point of the non-linear system $\dot {x}=f(x)$. We show that the problem of determining $S$ is computationally unsolvable. We also present an upper bound of the degree of unsolvability of this problem.

References

Oliver Aberth, Computable analysis and differential equations, Intuitionism and Proof Theory (Proc. Conf., Buffalo, N.Y., 1968) North-Holland, Amsterdam, 1970, pp. 47–52. MR 0276087
Oliver Aberth, The failure in computable analysis of a classical existence theorem for differential equations, Proc. Amer. Math. Soc. 30 (1971), 151–156. MR 302982, DOI 10.1090/S0002-9939-1971-0302982-7
Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21 (1989), no. 1, 1–46. MR 974426, DOI 10.1090/S0273-0979-1989-15750-9
M. Braverman and M. Yampolsky, Non-computable Julia sets, J. Amer. Math. Soc. 19 (2006), no. 3, 551–578. MR 2220099, DOI 10.1090/S0894-0347-05-00516-3
Earl A. Coddington and Norman Levinson, Theory of ordinary differential equations, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1955. MR 0069338
Roberto Genesio, Michele Tartaglia, and Antonio Vicino, On the estimation of asymptotic stability regions: state of the art and new proposals, IEEE Trans. Automat. Control 30 (1985), no. 8, 747–755. MR 794208, DOI 10.1109/TAC.1985.1104057
D.S. Graça, N. Zhong and J. Buescu. Computability, noncomputability and undecidability of maximal intervals of IVPs. To appear in Transactions of the AMS.
A. Grzegorczyk, Computable functionals, Fund. Math. 42 (1955), 168–202. MR 86756, DOI 10.4064/fm-42-1-168-202
Morris W. Hirsch and Stephen Smale, Differential equations, dynamical systems, and linear algebra, Pure and Applied Mathematics, Vol. 60, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1974. MR 0486784
Tosio Kato, Perturbation theory for linear operators, Die Grundlehren der mathematischen Wissenschaften, Band 132, Springer-Verlag New York, Inc., New York, 1966. MR 0203473
Ker-I Ko, Complexity theory of real functions, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1991. MR 1137517, DOI 10.1007/978-1-4684-6802-1
Ker-I Ko, Computational complexity of fractals, Proceedings of the 7th and 8th Asian Logic Conferences, Singapore Univ. Press, Singapore, 2003, pp. 252–269. MR 2051982, DOI 10.1142/9789812705815_{0}011
Daniel Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles. II, III, C. R. Acad. Sci. Paris 241 (1955), 13–14, 151–153 (French). MR 72080
S. Mazur, Computable analysis, Rozprawy Mat. 33 (1963), 110. MR 153553
Marian B. Pour-El and J. Ian Richards, Computability in analysis and physics, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989. MR 1005942, DOI 10.1007/978-3-662-21717-7
Marian B. Pour-El and Ning Zhong, The wave equation with computable initial data whose unique solution is nowhere computable, Math. Logic Quart. 43 (1997), no. 4, 499–509. MR 1477618, DOI 10.1002/malq.19970430406
Robert Rettinger and Klaus Weihrauch, The computational complexity of some Julia sets, Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 177–185. MR 2121048, DOI 10.1145/780542.780570
A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc., Vol. 2, No. 42, pp. 230-265, 1936.
Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR 1795407, DOI 10.1007/978-3-642-56999-9
Klaus Weihrauch and Ning Zhong, Is wave propagation computable or can wave computers beat the Turing machine?, Proc. London Math. Soc. (3) 85 (2002), no. 2, 312–332. MR 1912053, DOI 10.1112/S0024611502013643
Klaus Weihrauch and Ning Zhong, An algorithm for computing fundamental solutions, SIAM J. Comput. 35 (2006), no. 6, 1283–1294. MR 2217146, DOI 10.1137/S0097539704446360
Ning Zhong and Klaus Weihrauch, Computability theory of generalized functions, J. ACM 50 (2003), no. 4, 469–505. MR 2146883, DOI 10.1145/792538.792542