## Computability, noncomputability and undecidability of maximal intervals of IVPs

HTML articles powered by AMS MathViewer

- by D.S. Graça, N. Zhong and J. Buescu PDF
- Trans. Amer. Math. Soc.
**361**(2009), 2913-2927 Request permission

## Abstract:

Let $(\alpha ,\beta )\subseteq \mathbb {R}$ denote the maximal interval of existence of solutions for the initial-value problem \[ \left \{ \begin {array} [c]{l}\frac {dx}{dt}=f(t,x), x(t_{0})=x_{0}, \end {array} \right . \] 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

- 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 - Errett Bishop and Douglas Bridges,
*Constructive analysis*, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 279, Springer-Verlag, Berlin, 1985. MR**804042**, DOI 10.1007/978-3-642-61667-9 - Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale,
*Complexity and real computation*, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR**1479636**, DOI 10.1007/978-1-4612-0701-6 - 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 - Mark Braverman and Stephen Cook,
*Computing over the reals: foundations for scientific computing*, Notices Amer. Math. Soc.**53**(2006), no. 3, 318–329. MR**2208383** - 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** - J. Denef and L. Lipshitz,
*Decision problems for differential equations*, J. Symbolic Logic**54**(1989), no. 3, 941–950. MR**1011182**, DOI 10.2307/2274755 - A. Grzegorczyk,
*Computable functionals*, Fund. Math.**42**(1955), 168–202. MR**86756**, DOI 10.4064/fm-42-1-168-202 - Jürgen Hauck,
*Ein Kriterium für die konstruktive Lösbarkeit der Differentialgleichung $y’=f(x,y)$*, Z. Math. Logik Grundlag. Math.**31**(1985), no. 4, 357–362 (German). MR**807518**, DOI 10.1002/malq.19850312106 - 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 - 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** - Solomon Lefschetz,
*Differential equations: Geometric theory*, 2nd ed., Pure and Applied Mathematics, Vol. VI, Interscience Publishers (a division of John Wiley & Sons, Inc.), New York-London, 1963. MR**0153903** - S. Mazur,
*Computable analysis*, Rozprawy Mat.**33**(1963), 110. MR**153553** - Piergiorgio Odifreddi,
*Classical recursion theory*, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland Publishing Co., Amsterdam, 1989. The theory of functions and sets of natural numbers; With a foreword by G. E. Sacks. MR**982269** - Marian Boykan Pour-El and Ian Richards,
*A computable ordinary differential equation which possesses no computable solution*, Ann. Math. Logic**17**(1979), no. 1-2, 61–90. MR**552416**, DOI 10.1016/0003-4843(79)90021-4 - Marian Boykan Pour-El and Ian Richards,
*The wave equation with computable initial data such that its unique solution is not computable*, Adv. in Math.**39**(1981), no. 3, 215–239. MR**614161**, DOI 10.1016/0001-8708(81)90001-3 - 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 - K. Ruohonen,
*An effective Cauchy-Peano existence theorem for unique solutions*, Internat. J. Found. Comput. Sci.**7**(1996), no. 2, 151–160. - M. Sipser,
*Introduction to the theory of computation*, PWS Publishing Company, Boston, MA, 1997. - A. M. Turing,
*On computable numbers, with an application to the Entscheidungsproblem*, Proc. London Math. Soc.**2**(1936), no. 42, 230–265. - 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

## 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
- Email: dgraca@ualg.pt
**N. Zhong**- Affiliation: Department of Mathematical Sciences, University of Cincinnati, Cincinnati, Ohio 45221-0025
- Email: ning.zhong@uc.edu
**J. Buescu**- Affiliation: CAMGSD and Dep. Matemática, Faculdade de Ciências, Ed C6, Piso 2, Campo Grande, 1749-006 Lisboa, Portugal
- Email: jbuescu@ptmat.fc.ul.pt
- 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 - © Copyright 2009 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**361**(2009), 2913-2927 - MSC (2000): Primary 65L05, 68Q17; Secondary 03D35
- DOI: https://doi.org/10.1090/S0002-9947-09-04929-0
- MathSciNet review: 2485412