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
DOI:
https://doi.org/10.1090/S0002-9947-09-04929-0
Published electronically:
January 22, 2009
MathSciNet review:
2485412
Full-text PDF Free Access
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 \[ \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.
- 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 https://doi.org/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
- 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
- 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 https://doi.org/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 https://doi.org/10.1090/S0894-0347-05-00516-3
- Earl A. Coddington and Norman Levinson, Theory of ordinary differential equations, McGraw-Hill Book Company, 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 https://doi.org/10.2307/2274755
- A. Grzegorczyk, Computable functionals, Fund. Math. 42 (1955), 168–202. MR 86756, DOI https://doi.org/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 https://doi.org/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
- 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, New York-Lond on, 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 https://doi.org/10.1016/0003-4843%2879%2990021-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 https://doi.org/10.1016/0001-8708%2881%2990001-3
- Marian B. Pour-El and J. Ian Richards, Computability in analysis and physics, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989. MR 1005942
- 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 https://doi.org/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
- 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 https://doi.org/10.1112/S0024611502013643
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
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
Article copyright:
© Copyright 2009
American Mathematical Society