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

DOI:
https://doi.org/10.1090/S0002-9939-1993-1134623-8

MathSciNet review:
1134623

Full-text PDF

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 ). 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 satisfying In this paper we characterize the subrings of of finite transcendence degree over satisfying 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 (i.e., archimedean rings).

**[BSS]**L. Blum, M. Shub, and S. Smale,*On a theory of computation and complexity over the real numbers*: -*completeness, recursive functions and universal machines*, Bull. Amer. Math. Soc. (N.S.)**21**(1989), 1-46. MR**974426 (90a:68022)****[B]**R. Byerly,*Computability over subfields of*, in preparation.**[F]**H. Friedman,*Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory*, Logic Colloquium 1969 (R. O. Gandy and C. M. E. Yates, eds.), North-Holland, Amsterdam, 1971, pp. 361-390. MR**0304140 (46:3275)****[Ma]**E. W. Madison,*A note on computable real fields*, J. Symbolic Logic**35**(1970), 239-241. MR**0272619 (42:7500)****[Man]**R. Mansfield,*The irrationals are not recursively enumerable*, Proc. Amer. Math. Soc.**110**(1990), 495-498. MR**1019752 (90m:03082)****[Mi]**C. Michaux,*Ordered rings over which output sets are recursively enumerable*, Proc. Amer. Math. Soc.**112**(1991), 569-575. MR**1041016 (91i:03073)****[vdD]**L. van den Dries,*Alfred Tarski's elimination theory for real closed fields*, J. Symbolic Logic**53**(1988), 7-19. MR**929371 (89h:01040)**

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

Retrieve articles in all journals with MSC: 03D75

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1993-1134623-8

Article copyright:
© Copyright 1993
American Mathematical Society