Ordered rings over which output sets are recursively enumerable sets

Author:
Christian Michaux

Journal:
Proc. Amer. Math. Soc. **112** (1991), 569-575

MSC:
Primary 03C57; Secondary 03D10, 03D75

Corrigendum:
Proc. Amer. Math. Soc. **117** (1993), null.

MathSciNet review:
1041016

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 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 , that are dense (for the order) in their real closures, only real closed fields have property O = R.E.

**[BS]**L. Blum and S. Smale,*The Gödel incompleteness theorem and decidability over a ring*, 1989.**[BSS]**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**, 10.1090/S0273-0979-1989-15750-9**[CK]**C. C. Chang and H. J. Keisler,*Model theory*, North-Holland, Amsterdam, 1973.**[MMV]**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**, 10.1016/0001-8708(83)90055-5**[Ra]**Michael O. Rabin,*Computable algebra, general theory and theory of computable fields.*, Trans. Amer. Math. Soc.**95**(1960), 341–360. MR**0113807**, 10.1090/S0002-9947-1960-0113807-4**[Sa]**Gerald E. Sacks,*Saturated model theory*, W. A. Benjamin, Inc., Reading, Mass., 1972. Mathematics Lecture Note Series. MR**0398817****[vdD]**Lou van den Dries,*Alfred Tarski’s elimination theory for real closed fields*, J. Symbolic Logic**53**(1988), no. 1, 7–19. MR**929371**, 10.2307/2274424

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
03C57,
03D10,
03D75

Retrieve articles in all journals with MSC: 03C57, 03D10, 03D75

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9939-1991-1041016-9

Article copyright:
© Copyright 1991
American Mathematical Society