Algorithmic Randomness and Complexity
Preface. Acknowledgments. Introduction. I. Background. Preliminaries. Computability Theory. Kolmogorov Complexity of Finite Strings. Relating Plain and Prefix Free Complexity. Effective Reals. II. Randomness of Sets. Martin Lof Randomness. Other Notions of Effective Randomness. Algorithmic Randomness and Turing Reducibility. III. Relative Randomness. Measures of Relative Randomness. The Quantity of K and Other Degrees. Randomness Theoretic Weakness. Lowness for Other Randomness Notions. Effective Hausdorff Dimension. IV. Further Topics. Omega as an Operator. Complexity of C.E. Sets. References. Index.
Theory and Applications of Computability