Algorithmic Randomness And Complexity by Rodney G. DowneyAlgorithmic Randomness And Complexity by Rodney G. Downey

Algorithmic Randomness And Complexity

byRodney G. Downey, Denis R. Hirschfeldt

Hardcover | November 5, 2010

Pricing and Purchase Info

$134.27 online 
$151.95 list price save 11%
Earn 671 plum® points

Prices and offers may vary in store


In stock online

Ships free on orders over $25

Not available in stores


This book is concerned with the theory of computability and complexity over the real numbers. This theory was initiated by Turing, Grzegorczyk, Lacombe, Banach and Mazur and has seen rapid growth in recent years. Computability and complexity theory are two central areas of research in theoretical computer science. Until recently, most work in these areas concentrated on problems over discrete structures, but there has been enormous growth of computability theory and complexity theory over the real numbers and other continuous structures, especially incorporating concepts of "randomness." One reason for this growth is that more and more computation problems over the real numbers are being dealt with by computer scientists--in computational geometry and in the modeling of dynamical and hybrid systems. Scientists working on these questions come from such diverse fields as theoretical computer science, domain theory, logic, constructive mathematics, computer arithmetic, numerical mathematics, and analysis. An essential resource for all researchers in theoretical computer science, logic, computability theory and complexity.
Title:Algorithmic Randomness And ComplexityFormat:HardcoverDimensions:855 pagesPublished:November 5, 2010Publisher:Springer-Verlag/Sci-Tech/TradeLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:0387955674

ISBN - 13:9780387955674


Table of Contents

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.

Editorial Reviews

From the reviews:"Develops the prerequisites to algorithmic randomness: computability theory and Kolmogorov complexity. . Studying these . one should be able to proceed in the area with confidence. A draft of the book under review has been circulating for years and the reviewer found it to be the best source when attempting to conduct research in the area . . It is advantageous for the future of the area of algorithmic randomness that these two books were published at the cusp of a period of great activity." (Bjørn Kjos-Hanssen, Mathematical Reviews, Issue 2012 g)"A thorough and systematic study of algorithmic randomness, this long-awaited work is an irreplaceable source of well-presented classic and new results for advanced undergraduate and graduate students, as well as researchers in the field and related areas. The book joins a select number of books in this category." (Hector Zenil, ACM Computing Reviews, October, 2011)