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

Byerly, Robert E.

doi:10.1090/S0002-9939-1993-1134623-8

Ordered subrings of the reals in which output sets are recursively enumerable
HTML articles powered by AMS MathViewer

by Robert E. Byerly PDF

Proc. Amer. Math. Soc. 118 (1993), 597-601 Request permission

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

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

Computability over subfields of

Harvey Friedman, Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969) North-Holland, Amsterdam, 1971, pp. 361–389. MR 0304140
E. W. Madison, A note on computable real fields, J. Symbolic Logic 35 (1970), 239–241. MR 272619, DOI 10.2307/2270515
Richard Mansfield, The irrationals are not recursively enumerable, Proc. Amer. Math. Soc. 110 (1990), no. 2, 495–497. MR 1019752, DOI 10.1090/S0002-9939-1990-1019752-9
Christian Michaux, Ordered rings over which output sets are recursively enumerable sets, Proc. Amer. Math. Soc. 112 (1991), no. 2, 569–575. MR 1041016, DOI 10.1090/S0002-9939-1991-1041016-9
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