A note on the differences of computably enumerable reals

Barmpalias, G. & Lewis-Pye, A. (2017). A note on the differences of computably enumerable reals. In Day, A., Fellows, M., Greenberg, N., Khoussainov, B., Melnikov, A. & Rosamond, F. (Eds.), Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday (pp. 623-632). Springer International (Firm). https://doi.org/10.1007/978-3-319-50062-1_37
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

Export as

EndNote BibTeX Reference Manager Refer Atom Dublin Core JSON Multiline CSV
Export