A Note on the Differences of Computably Enumerable Reals

DOI10.1007/978-3-319-50062-1_37MaRDI QIDQ2970983zbMATH OpenOpenAlexFDO

Authors George Barmpalias, Andrew E. M. Lewis

Publication date 4 April 2017

Published in Computability and Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.05192, http://eprints.lse.ac.uk/67121/8/Lewis_Pye_Note%20on%20the%20differences_2016_author%20LSERO.pdf

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Algorithmic randomness and dimension (03D32)

Abstract: We show that given any non-computable left-c.e. real $alpha$ there exists a left-c.e. real $$ such that $$ for all left-c.e. reals and all right-c.e. reals $gamma$. The proof is non-uniform, the dichotomy being whether the given real $alpha$ 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.

Recommendations

• On the differences and sums of strongly computably enumerable real numbers
• Differences of Computably Enumerable Sets
• scientific article; zbMATH DE number 1405572
• Relatively computably enumerable reals
• scientific article; zbMATH DE number 5287432
• Bounded Computable Enumerability and Hierarchy of Computably Enumerable Reals
• On the problem of definability of the computably enumerable degrees in the difference hierarchy
• Presentations of computably enumerable reals.
• Computably Enumerable Reals and Uniformly Presentable Ideals
• On 0'-computable reals

Cites work

• Algorithmic randomness and complexity.
• Computability and Randomness
• Computing halting probabilities from other halting probabilities
• Degrees of d. c. e. reals
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1543065 (Why is no real title available?)
• Randomness and recursive enumerability
• Randomness and universal machines
• Randomness, computability, and density
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• Relative randomness and real closed fields
• Weakly computable real numbers
• Working with strong reducibilities above totally -c.e. and array computable degrees

Cited in

(5)

• A note of best fractions of a computable real number
• Presentations of computably enumerable reals.
• Differences of halting probabilities
• SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS
• Computability of Real Numbers

This page was built for publication: A Note on the Differences of Computably Enumerable Reals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970983)