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
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.
| Item Type | Chapter |
|---|---|
| Copyright holders | © 2017 Springer International Publishing AG |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1007/978-3-319-50062-1_37 |
| Date Deposited | 13 Jul 2016 |
| Acceptance Date | 11 Jul 2016 |
| URI | https://researchonline.lse.ac.uk/id/eprint/67121 |
Explore Further
- http://www.lse.ac.uk/Mathematics/people/Andrew-Lewis-Pye.aspx (Author)
- https://www.scopus.com/pages/publications/85008473036 (Scopus publication)
- http://www.springer.com/series/558 (Official URL)