Algorithmic Randomness and Complexity - Downey, Rodney G.;Hirschfeldt, Denis R.
Bisher 68,99 €**
67,99 €
versandkostenfrei*

inkl. MwSt.
**Früherer Preis
Versandfertig in 2-4 Wochen
34 °P sammeln
    Broschiertes Buch

Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of "algorithmic randomness" and complexity for scientists from diverse fields.

Produktbeschreibung
Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of "algorithmic randomness" and complexity for scientists from diverse fields.
  • Produktdetails
  • Theory and Applications of Computability
  • Verlag: Springer / Springer, Berlin
  • Artikelnr. des Verlages: 978-1-4939-3820-9
  • Softcover reprint of the original 1st ed. 2010
  • Seitenzahl: 884
  • Erscheinungstermin: 23. August 2016
  • Englisch
  • Abmessung: 235mm x 155mm x 46mm
  • Gewicht: 1329g
  • ISBN-13: 9781493938209
  • ISBN-10: 1493938207
  • Artikelnr.: 45670384
Inhaltsangabe
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.
Rezensionen
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)