Undecidability of the Structure of the Solovay Degrees of C.E. reals

by Rod Downey, Denis R. Hirschfeldt, and Geoff LaForte

Status: published in the Journal of Computer and System Sciences 73 (2007) 769 - 787

Availability: DVI, PostScript, and PDF

Abstract. We show that the elementary theory of the structure of the Solovay degrees of computably enumerable reals is undecidable.