Ordered rings over which output sets are recursively enumerable sets
HTML articles powered by AMS MathViewer
- by Christian Michaux
- Proc. Amer. Math. Soc. 112 (1991), 569-575
- DOI: https://doi.org/10.1090/S0002-9939-1991-1041016-9
- PDF | Request permission
Corrigendum: Proc. Amer. Math. Soc. 117 (1993), 583.
Abstract:
In a recent paper [BSS], L. Blum, M. Shub, and S. Smale developed a theory of computation over the reals and over commutative ordered rings; in $\S 9$ of [BSS] they showed that over the reals (and over any real closed field) the class of recursively enumerable sets and the class of output sets are the same; it is a question (Problem 9.1 in [BSS]) to characterize ordered rings with this property (abbreviated by O = R.E. here). In this paper we prove essentially that in the class of (linearly) ordered rings of infinite transcendence degree over $\mathbb {Q}$, that are dense (for the order) in their real closures, only real closed fields have property O = R.E.References
- L. Blum and S. Smale, The Gödel incompleteness theorem and decidability over a ring, 1989.
- 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 C. C. Chang and H. J. Keisler, Model theory, North-Holland, Amsterdam, 1973.
- Angus Macintyre, Kenneth McKenna, and Lou van den Dries, Elimination of quantifiers in algebraic structures, Adv. in Math. 47 (1983), no. 1, 74–87. MR 689765, DOI 10.1016/0001-8708(83)90055-5
- Michael O. Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341–360. MR 113807, DOI 10.1090/S0002-9947-1960-0113807-4
- Gerald E. Sacks, Saturated model theory, Mathematics Lecture Note Series, W. A. Benjamin, Inc., Reading, Mass., 1972. MR 0398817
- Lou van den Dries, Alfred Tarski’s elimination theory for real closed fields, J. Symbolic Logic 53 (1988), no. 1, 7–19. MR 929371, DOI 10.2307/2274424
Bibliographic Information
- © Copyright 1991 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 112 (1991), 569-575
- MSC: Primary 03C57; Secondary 03D10, 03D75
- DOI: https://doi.org/10.1090/S0002-9939-1991-1041016-9
- MathSciNet review: 1041016