Ordered rings over which output sets are recursively enumerable sets

Michaux, Christian

doi:10.1090/S0002-9939-1991-1041016-9

Ordered rings over which output sets are recursively enumerable sets
HTML articles powered by AMS MathViewer

by Christian Michaux PDF

Proc. Amer. Math. Soc. 112 (1991), 569-575 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

The Gödel incompleteness theorem and decidability over a ring

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

Model theory

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