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
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 |
| Keywords | 1000 Talents Program for Young Scholars, President’s International Fellowship Initiative No. 2010Y2GB03, 2014CB340302 |
| Departments | Mathematics |
| DOI | 10.1007/978-3-319-50062-1_37 |
| Date Deposited | 13 Jul 2016 16:24 |
| Acceptance Date | 2016-07-11 |
| URI | https://researchonline.lse.ac.uk/id/eprint/67121 |