Proceedings of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6826(e) ISSN 0002-9939(p)

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

Author(s): M. Laczkovich
Journal: Proc. Amer. Math. Soc. 131 (2003), 2235-2240.
MSC (2000): Primary 03B25, 03D40; Secondary 26A09
Posted: October 18, 2002
MathSciNet review: 1963772
Retrieve article in: PDF
This article is available free of charge

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:

1.: B. F. Caviness, On canonical forms and simplification, Journal of the Association for computing Machinery 17 (2) (1970), 385-396. MR 43:7104
2.: L. Kuipers and H. Niederreiter, Uniform distribution of sequences. John Wiley & Sons, 1974. MR 54:7415
3.: A. J. Macintyre, Exponential algebra. Logic and Algebra (Pontignano, 1994), 191-210. Lecture Notes in Pure and Applied Mathematics, No. 180. Dekker, 1996. MR 97h:03064
4.: D. Richardson, Some undecidable problems involving elementary functions of a real variable, J. Symbolic Logic 33 (1968), 514-520. MR 39:1330
5.: P. S. Wang, The undecidability of the existence of zeros of real elementary functions, Journal of the Association for computing Machinery 21 (4) (1974), 586-589. MR 51:117

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: 10.1090/S0002-9939-02-06753-9
PII: S 0002-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
Posted: 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.
Copyright of article: Copyright 2002, American Mathematical Society

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|