Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

Ordered subrings of the reals in which output sets are recursively enumerable


Author: Robert E. Byerly
Journal: Proc. Amer. Math. Soc. 118 (1993), 597-601
MSC: Primary 03D75
MathSciNet review: 1134623
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In On a theory of computation and complexity over the real numbers ..., Bull. Amer. Math. Soc. 21 (1989), 1-46, Blum, Shub, and Smale investigated computability over the reals and over ordered rings in general. They showed that over the reals, output sets of machines are recursively enumerable (i.e., halting sets of machines). It is asked in the aforementioned paper which ordered rings have this property (which we abbreviate $ O = R.E.$). In Ordered rings over which output sets are recursively enumerable, Proc. Amer. Math. Soc. 112 (1991), 569-575, Michaux characterized the members of a certain class of ordered rings of infinite transcendence degree over $ \mathbb{Q}$ satisfying $ O = R.E.$ In this paper we characterize the subrings of $ \mathbb{R}$ of finite transcendence degree over $ \mathbb{Q}$ satisfying $ O = R.E.$ as those rings recursive in the Dedekind cuts of members of a transcendence base. With Michaux's result, this answers the question for subrings of $ \mathbb{R}$ (i.e., archimedean rings).


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03D75

Retrieve articles in all journals with MSC: 03D75


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9939-1993-1134623-8
PII: S 0002-9939(1993)1134623-8
Article copyright: © Copyright 1993 American Mathematical Society