Switch to: References

Citations of:

Randomness and the linear degrees of computability

Andrew Em Lewis & George Barmpalias

Annals of Pure and Applied Logic 145 (3):252-257 (2007)

Add citations

You must login to add citations.

(1 other version)Algorithmic Randomness and Measures of Complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.details We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on reducibilities that measure the initial segment complexity of reals and the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability. Download Export citation Bookmark 1 citation
A uniform version of non-low2-ness.Yun Fan - 2017 - Annals of Pure and Applied Logic 168 (3):738-748.details Download Export citation Bookmark
Maximal pairs of c.e. reals in the computably Lipschitz degrees.Yun Fan & Liang Yu - 2011 - Annals of Pure and Applied Logic 162 (5):357-366.details Computably Lipschitz reducibility , was suggested as a measure of relative randomness. We say α≤clβ if α is Turing reducible to β with oracle use on x bounded by x+c. In this paper, we prove that for any non-computable real, there exists a c.e. real so that no c.e. real can cl-compute both of them. So every non-computable c.e. real is the half of a cl-maximal pair of c.e. reals. Download Export citation Bookmark 1 citation

1