This is the first comprehensive treatment of this important field, designed to be both a reference tool for experts and a guide for newcomers. It surveys a broad section of work in the area, and presents most of its major results and techniques in depth. Its organization is designed to guide the reader through this large body of work, providing context for its many concepts and theorems, discussing their significance, and highlighting their interactions. It includes a discussion of effective dimension, which allows us to assign concepts like Hausdorff dimension to individual reals, and a focused but detailed introduction to computability theory. It will be of interest to researchers and students in computability theory, algorithmic information theory, and theoretical computer science." Essential resource for all researchers in theoretical computer science, logic, computability theory, and complexity Written by experts First comprehensive treatment on the subject An essential resource for all researchers and graduate students in theoretical computer science, logic, computability theory and complexity INDICE: 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 ofRelative 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.
- ISBN: 978-0-387-95567-4
- Editorial: SPRINGER VERLAG GMBH & Co. KG
- Encuadernacion: Cartoné
- Páginas: 855
- Fecha Publicación: 29/11/2010
- Nº Volúmenes: 1
- Idioma: Inglés