A note on the differences of computably enumerable reals

Barmpalias, George; and Lewis-Pye, Andrew (2017) A note on the differences of computably enumerable reals In: Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday. Lecture Notes in Computer Science . Springer International (Firm), Cham, Switzerland, pp. 623-632. ISBN 9783319500614
Copy

We show that given any non-computable left-c.e. real α there exists a left-c.e. real β such that α≠β+γ for all left-c.e. reals and all right-c.e. reals γ. The proof is non-uniform, the dichotomy being whether the given real α is Martin-Loef random or not. It follows that given any universal machine U, there is another universal machine V such that the halting probability of U is not a translation of the halting probability of V by a left-c.e. real. We do not know if there is a uniform proof of this fact.


picture_as_pdf
subject
Accepted Version

Download

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads