The removal of $\pi$ from some undecidable problems involving elementary functions
HTML articles powered by AMS MathViewer
- by M. Laczkovich PDF
- Proc. Amer. Math. Soc. 131 (2003), 2235-2240 Request permission
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
- B. F. Caviness, On canonical forms and simplification, J. Assoc. Comput. Mach. 17 (1970), 385–396. MR 281386, DOI 10.1145/321574.321591
- L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0419394
- J. C. Oxtoby and S. M. Ulam, On the existence of a measure invariant under a transformation, Ann. of Math. (2) 40 (1939), 560–566. MR 97, DOI 10.2307/1968940
- Daniel Richardson, Some undecidable problems involving elementary functions of a real variable, J. Symbolic Logic 33 (1968), 514–520. MR 239976, DOI 10.2307/2271358
- Paul S. Wang, The undecidability of the existence of zeros of real elementary functions, J. Assoc. Comput. Mach. 21 (1974), 586–589. MR 363862, DOI 10.1145/321850.321856
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
- 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.
- © Copyright 2002 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 131 (2003), 2235-2240
- MSC (2000): Primary 03B25, 03D40; Secondary 26A09
- DOI: https://doi.org/10.1090/S0002-9939-02-06753-9
- MathSciNet review: 1963772