Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Computability, noncomputability and undecidability of maximal intervals of IVPs

Authors: D.S. Graça, N. Zhong and J. Buescu
Journal: Trans. Amer. Math. Soc. 361 (2009), 2913-2927
MSC (2000): Primary 65L05, 68Q17; Secondary 03D35
Published electronically: January 22, 2009
MathSciNet review: 2485412
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ (\alpha,\beta)\subseteq \mathbb{R}$ denote the maximal interval of existence of solutions for the initial-value problem

\begin{displaymath} \left\{ \begin{array}[c]{l} \frac{dx}{dt}=f(t,x),\\ x(t_{0})=x_{0}, \end{array}\right. \end{displaymath}

where $ E$ is an open subset of $ \mathbb{R}^{m+1}$, $ f$ is continuous in $ E$ and $ (t_{0},x_{0})\in E$. We show that, under the natural definition of computability from the point of view of applications, there exist initial-value problems with computable $ f$ and $ (t_{0},x_{0})$ whose maximal interval of existence $ (\alpha,\beta)$ is noncomputable. The fact that $ f$ may be taken to be analytic shows that this is not a lack of the regularity phenomenon. Moreover, we get upper bounds for the ``degree of noncomputability'' by showing that $ (\alpha,\beta)$ is r.e. (recursively enumerable) open under very mild hypotheses. We also show that the problem of determining whether the maximal interval is bounded or unbounded is in general undecidable.

References [Enhancements On Off] (What's this?)

  • 1. O. Aberth, Computable analysis and differential equations, Intuitionism and Proof Theory (A. Kino, J. Myhill, and R.E. Vesley, eds.), Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 1970, pp. 47-52. MR 0276087 (43:1835)
  • 2. -, The failure in computable analysis of a classical existence theorem for differential equations, Proc. Amer. Math. Soc. 30 (1971), 151-156. MR 0302982 (46:2124)
  • 3. E. Bishop and D. S. Bridges, Constructive analysis, Springer, 1985. MR 804042 (87d:03172)
  • 4. L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and real computation, Springer, 1998. MR 1479636 (99a:68070)
  • 5. 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. 21 (1989), no. 1, 1-46. MR 974426 (90a:68022)
  • 6. M. Braverman and S. Cook, Computing over the reals: Foundations for scientific computing, Notices Amer. Math. Soc. 53 (2006), no. 3, 318-329. MR 2208383 (2006m:68019)
  • 7. M. Braverman and M. Yampolsky, Non-computable Julia sets, Journal Amer. Math. Soc. 19 (2006), 551-578. MR 2220099 (2007m:37110)
  • 8. E. A. Coddington and N. Levinson, Theory of ordinary differential equations, McGraw-Hill, 1955. MR 0069338 (16:1022b)
  • 9. J. Denef and L. Lipshitz, Decision problems for differential equations, J. Symbolic Logic 54 (1989), no. 3, 941-950. MR 1011182 (91b:03074)
  • 10. A. Grzegorczyk, Computable functionals, Fund. Math. 42 (1955), 168-202. MR 0086756 (19:238b)
  • 11. J. Hauck, Ein Kriterium für die konstruktive Lösbarkeit der Differentialgleichung $ y^{\prime}=f(x,y)$, Z. Math. Logik Grundlag. Math. 31 (1985), no. 4, 357-362. MR 807518 (87b:03136)
  • 12. K.-I Ko, Complexity theory of real functions, Birkhäuser, Boston, MA, 1991. MR 1137517 (93i:03057)
  • 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 241 (1955), 151-153. MR 0072080 (17:225e)
  • 14. S. Lefschetz, Differential equations: Geometric theory, 2nd ed., Interscience, 1963. MR 0153903 (27:3864)
  • 15. S. Mazur, Computable analysis, PWN, 1963. MR 0153553 (27:3517)
  • 16. P. Odifreddi, Classical recursion theory, vol. 1, Elsevier, 1989. MR 982269 (90d:03072)
  • 17. M. B. Pour-El and J. I. Richards, A computable ordinary differential equation which possesses no computable solution, Ann. Math. Logic 17 (1979), 61-90. MR 552416 (81k:03064)
  • 18. -, The wave equation with computable initial data such that its unique solution is not computable, Adv. Math. 39 (1981), 215-239. MR 614161 (83e:03101)
  • 19. -, Computability in analysis and physics, Springer, 1989. MR 1005942 (90k:03062)
  • 20. M. B. Pour-El and N. Zhong, The wave equation with computable initial data whose unique solution is nowhere computable, Math. Log. Quart. 43 (1997), 499-509. MR 1477618 (98m:03097)
  • 21. K. Ruohonen, An effective Cauchy-Peano existence theorem for unique solutions, Internat. J. Found. Comput. Sci. 7 (1996), no. 2, 151-160.
  • 22. M. Sipser, Introduction to the theory of computation, PWS Publishing Company, Boston, MA, 1997.
  • 23. A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. 2 (1936), no. 42, 230-265.
  • 24. K. Weihrauch, Computable analysis: An introduction, Springer-Verlag, 2000. MR 1795407 (2002b:03129)
  • 25. K. Weihrauch and N. Zhong, Is wave propagation computable or can wave computers beat the Turing machine?, Proc. London Math. Soc. 85 (2002), no. 3, 312-332. MR 1912053 (2003i:03064)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 65L05, 68Q17, 03D35

Retrieve articles in all journals with MSC (2000): 65L05, 68Q17, 03D35

Additional Information

D.S. Graça
Affiliation: DM/FCT, Universidade do Algarve, C. Gambelas, 8005-139 Faro, Portugal – and – SQIG, Instituto de Telecomunicações, Instituto Superior Técnico, Torre Norte, Piso 10, Av. Rovisco Pais, 1049-001 Lisboa, Portugal

N. Zhong
Affiliation: Department of Mathematical Sciences, University of Cincinnati, Cincinnati, Ohio 45221-0025

J. Buescu
Affiliation: CAMGSD and Dep. Matemática, Faculdade de Ciências, Ed C6, Piso 2, Campo Grande, 1749-006 Lisboa, Portugal

Received by editor(s): July 6, 2006
Published electronically: January 22, 2009
Additional Notes: The first author thanks M. Campagnolo, O. Bournez, and E. Hainry for helpful discussions. The first author was partially supported by Fundação para a Ciência e a Tecnologia and EU FEDER POCTI/POCI via CLC, grant SFRH/BD/17436/2004, and the project ConTComp POCTI/MAT/45978/2002. Additional support was also provided by the Fundação Calouste Gulbenkian through the Programa Gulbenkian de Estímulo à Investigação.
The second author was partially supported by University of Cincinnati’s Taft Summer Research Fellowship.
The third author was partially supported by Fundação para a Ciência e a Tecnologia and EU FEDER POCTI/POCI via CAMGSD
Article copyright: © Copyright 2009 American Mathematical Society

American Mathematical Society