Output Sets, Halting Sets and an Arithmetical Hierarchy for Ordered Subrings of the Real Number Under Blum/Shub/Smale Computation
Title | Output Sets, Halting Sets and an Arithmetical Hierarchy for Ordered Subrings of the Real Number Under Blum/Shub/Smale Computation |
Publication Type | Technical Report |
Year of Publication | 1994 |
Authors | John, R. Saint |
Other Numbers | 905 |
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. |
URL | http://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 |