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
Additional Information
- Ning Zhong
- Affiliation: Department of Mathematical Sciences, University of Cincinnati, Cincinnati, Ohio 45221-0025
- Email: Ning.Zhong@uc.edu
- Received by editor(s): July 11, 2008
- Received by editor(s) in revised form: December 8, 2008
- Published electronically: February 3, 2009
- Communicated by: Julia Knight
- © Copyright 2009 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 137 (2009), 2773-2783
- MSC (2000): Primary 03D80; Secondary 34D45, 68Q17
- DOI: https://doi.org/10.1090/S0002-9939-09-09851-7
- MathSciNet review: 2497492