You are here

Algorithmic Randomness and Complexity

Rodney G. Downey and Denis R. Hirschfeldt
Publisher: 
Springer
Publication Date: 
2010
Number of Pages: 
855
Format: 
Hardcover
Series: 
Theory and Applications of Computability
Price: 
99.00
ISBN: 
9780387955674
Category: 
Monograph
We do not plan to review this book.

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-Löf 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.