|
Computational unsolvability of domains of attraction of nonlinear systems
Author(s):
Ning
Zhong
Journal:
Proc. Amer. Math. Soc.
137
(2009),
2773-2783.
MSC (2000):
Primary 03D80;
Secondary 34D45, 68Q17
Posted:
February 3, 2009
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
Let  be the domain of attraction of a computable and asymptotically stable hyperbolic equilibrium point of the non-linear system  . We show that the problem of determining  is computationally unsolvable. We also present an upper bound of the degree of unsolvability of this problem.
References:
-
- 1.
- O. Aberth.
Computable analysis and differential equations.
Intuitionism and Proof Theory, edited by A. Kino, J. Myhill and R.E. Vesley, Studies in Logic and the Foundations of Mathematics, pp. 47-52, North-Holland, Amsterdam, 1970. MR 0276087 (43:1835) - 2.
- O. Aberth.
The failure in computable analysis of a classical existence theorem for differential equations.
Proc. Amer. Math. Soc., Vol. 30, pp. 151-156, 1971. MR 0302982 (46:2124) - 3.
- L. Blum, M. Shub and S. Smale.
On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines.
Bull. Amer. Math. Soc., Vol. 21, No. 1, pp. 1-46, 1989. MR 974426 (90a:68022) - 4.
- M. Braverman and M. Yampolsky.
Non-computable Julia sets.
J. Amer. Math. Soc., Vol. 19, No. 3, pp. 551-578, 2006. MR 2220099 (2007m:37110) - 5.
- E. Coddington and N. Levinson.
Theory of Ordinary Differential Equations.
International Series in Pure and Applied Mathematics, McGraw-Hill Book Company, New York-Toronto-London, 1955. MR 0069338 (16:1022b) - 6.
- R. Genesio, M. Tartaglia, and A. Vicino.
On the estimation of asymptotic stability regions: State of the art and new proposals.
IEEE Transactions on Automatic Control, Vol. AC-30, No. 8, pp. 747-755, August 1985. MR 794208 (86g:93046) - 7.
- 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. - 8.
- A. Grzegorczyk.
Computable functionals.
Fund. Math., Vol. 42, pp. 168-202, 1955. MR 0086756 (19:238b) - 9.
- M. Hirsch and S. Smale.
Differential equations, dynamical systems, and linear algebra.
Pure and Applied Mathematics, Vol. 60, Academic Press, New York-London, 1974. MR 0486784 (58:6484) - 10.
- T. Kato.
Perturbation theory for linear operators.
Die Grundlehren der mathmatischen Wissenschaften in Einzeldarstellungen, Band 132, Springer-Verlag, New York-Berlin, 1966. MR 0203473 (34:3324) - 11.
- K. Ko.
Complexity Theory of Real Functions.
Progress in Theoretical Computer Science. Birkhäuser, Boston, 1991. MR 1137517 (93i:03057) - 12.
- K. Ko.
Computational complexity of fractals.
Proceedings of the 7th and 8th Asian Logic Conferences, pp. 252-269, Singapore Univ. Press, Singapore, 2003. MR 2051982 (2005a:03123) - 13.
- D. Lacombe.
Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles. III.
Comptes Rendus de l'Académie des Sciences Paris, Vol. 241, pp. 151-153, 1955. MR 0072080 (17:225e) - 14.
- S. Mazur.
Computable Analysis.
Rozprawy Mat., Vol. 33, PWN, 1963. MR 0153553 (27:3517) - 15.
- M. B. Pour-El and J. I. Richards.
Computability in Analysis and Physics.
Springer, Berlin, 1989. MR 1005942 (90k:03062) - 16.
- M. B. Pour-El and N. Zhong.
The wave equation with computable initial data whose unique solution is nowhere computable.
Math. Logic Quarterly, Vol. 43, No. 4, pp. 499-509, 1997. MR 1477618 (98m:03097) - 17.
- R. Rettinger and K. Weihrauch.
The computational complexity of some Julia sets.
Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 177-185, ACM, New York, 2003. MR 2121048 (2005j:68060) - 18.
- A. M. Turing.
On computable numbers, with an application to the Entscheidungsproblem.
Proc. London Math. Soc., Vol. 2, No. 42, pp. 230-265, 1936. - 19.
- K. Weihrauch.
Computable Analysis.
Springer, Berlin, 2000. MR 1795407 (2002b:03129) - 20.
- K. Weihrauch and N. Zhong.
Is wave propagation computable or can wave computers beat the Turing machine?
Proc. London Math. Soc., Vol. 85, No. 3, pp. 312-332, 2002. MR 1912053 (2003i:03064) - 21.
- K. Weihrauch and N. Zhong.
An algorithm for computing fundamental solutions.
SIAM Journal on Computing, Vol. 35, No. 6, pp. 1283-1294, 2006. MR 2217146 (2007f:03104) - 22.
- N. Zhong and K. Weihrauch.
Computability theory of generalized functions.
Journal of ACM, Vol. 50, Issue 4, pp. 469-505, 2003. MR 2146883 (2006d:03111)
Similar Articles:
Retrieve articles in Proceedings of the American Mathematical Society
with MSC
(2000):
03D80,
34D45, 68Q17
Retrieve articles in all Journals with MSC
(2000):
03D80,
34D45, 68Q17
Additional Information:
Ning
Zhong
Affiliation:
Department of Mathematical Sciences, University of Cincinnati, Cincinnati, Ohio 45221-0025
Email:
Ning.Zhong@uc.edu
DOI:
10.1090/S0002-9939-09-09851-7
PII:
S 0002-9939(09)09851-7
Keywords:
Recursive open/closed subsets of $\mathbb {R}^n$,
r.e. open/closed subsets of $\mathbb {R}^n$,
computable functions,
continuous dynamical systems,
domain of attraction of an asymptotically stable equilibrium point.
Received by editor(s):
July 11, 2008,
Received by editor(s) in revised form:
December 8, 2008
Posted:
February 3, 2009
Communicated by:
Julia Knight
Copyright of article:
Copyright
2009,
American Mathematical Society
|
Comments: webmaster@ams.org