On the characterization of recursively enumerable sets as pseudo-Diophantine
HTML articles powered by AMS MathViewer
- by Kostas Skandalis PDF
- Proc. Amer. Math. Soc. 123 (1995), 555-558 Request permission
Abstract:
In 1989 L. Blum, M. Shub, and S. Smale stated a problem whether the recursively enumerable sets can be characterized as pseudo-diophantine definable (Bull. Amer. Math. Soc. (N.S.) 21 (1989), 1-46, Problem 9.2). An example shows that such a characterization is impossible. Nevertheless, a some-what different characterization holds for the recursively enumerable sets over reals.References
- 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
- Kostas Skandalis, Programmable real numbers and functions, Fund. Inform. 7 (1984), no. 1, 27–56. MR 745536
Additional Information
- © Copyright 1995 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 123 (1995), 555-558
- MSC: Primary 03D65
- DOI: https://doi.org/10.1090/S0002-9939-1995-1216824-5
- MathSciNet review: 1216824