Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

The removal of $\pi$ from some undecidable problems involving elementary functions


Author: M. Laczkovich
Journal: Proc. Amer. Math. Soc. 131 (2003), 2235-2240
MSC (2000): Primary 03B25, 03D40; Secondary 26A09
Published electronically: October 18, 2002
MathSciNet review: 1963772
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We show that in the ring generated by the integers and the functions $x, \sin x^{n}$ and $\sin(x\cdot \sin x^{n})$ $(n=1,2,\ldots )$ defined on $\mathbf{R}$ it is undecidable whether or not a function has a positive value or has a root. We also prove that the existential theory of the exponential field $\mathbf{C} $ is undecidable.


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

  • 1. B. F. Caviness, On canonical forms and simplification, J. Assoc. Comput. Mach. 17 (1970), 385–396. MR 0281386
  • 2. L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR 0419394
  • 3. Angus J. Macintyre, Exponential algebra, Logic and algebra (Pontignano, 1994) Lecture Notes in Pure and Appl. Math., vol. 180, Dekker, New York, 1996, pp. 191–210. MR 1404940
  • 4. Daniel Richardson, Some undecidable problems involving elementary functions of a real variable, J. Symbolic Logic 33 (1968), 514–520. MR 0239976
  • 5. Paul S. Wang, The undecidability of the existence of zeros of real elementary functions, J. Assoc. Comput. Mach. 21 (1974), 586–589. MR 0363862

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03B25, 03D40, 26A09

Retrieve articles in all journals with MSC (2000): 03B25, 03D40, 26A09


Additional Information

M. Laczkovich
Affiliation: Department of Analysis, Eötvös Loránd University, Budapest, Pázmány Péter sétány 1/C 1117, Hungary
Email: laczko@renyi.hu

DOI: http://dx.doi.org/10.1090/S0002-9939-02-06753-9
Keywords: Undecidable problems, rings of elementary functions
Received by editor(s): February 7, 2002
Received by editor(s) in revised form: February 22, 2002
Published electronically: October 18, 2002
Additional Notes: This research was partially supported by the Hungarian National Foundation for Scientific Research Grant No. T032042
Communicated by: Carl G. Jockusch, Jr.
Article copyright: © Copyright 2002 American Mathematical Society