Output Sets, Halting Sets and an Arithmetical Hierarchy for Ordered Subrings of the Real Number Under Blum/Shub/Smale Computation

TitleOutput Sets, Halting Sets and an Arithmetical Hierarchy for Ordered Subrings of the Real Number Under Blum/Shub/Smale Computation
Publication TypeTechnical Report
Year of Publication1994
AuthorsJohn, R. Saint
Other Numbers905
Abstract

The original exposition of Blum/Shub/Smale compuation for subrings and subfields of real numbers (1989) asks how generally output and halting sets coincide. Aspects of this question were subsequently addressed by Michaux, Byerly, and Friedman/Mansfield. This document synthesizes, simplifies, and extends their answers.Distinguishing output sets from halting sets in the reals and subrings of the reals leads to a natural arithmetical hierarchy of non-computable sets. Operators analogous to the Jump operator of classical recursion theory are used to build an arithmetical hierarchy from the empty-set. As expected, the classical arithmetical hierarchy for the natural numbers occurs as a special case. Additional special cases arise in other subrings and subfields of the real numbers.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-035.pdf
Bibliographic Notes

ICSI Technical Report TR-94-035

Abbreviated Authors

R. S. John

ICSI Publication Type

Technical Report