Overview
- Authors were awarded the 2016 Shoenfield Prize by the Association for Symbolic Logic for outstanding expository writing in the field of logic
- Essential resource for researchers and graduate students in theoretical computer science, logic, computability theory, and complexity
- First comprehensive treatment on the subject, written by experts
- Includes supplementary material: sn.pub/extras
Part of the book series: Theory and Applications of Computability (THEOAPPLCOM)
Access this book
Tax calculation will be finalised at checkout
Other ways to access
Table of contents (16 chapters)
-
Background
-
Notions of Randomness
-
Further Topics
Keywords
About this book
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)
Authors and Affiliations
Bibliographic Information
Book Title: Algorithmic Randomness and Complexity
Authors: Rodney G. Downey, Denis R. Hirschfeldt
Series Title: Theory and Applications of Computability
DOI: https://doi.org/10.1007/978-0-387-68441-3
Publisher: Springer New York, NY
eBook Packages: Mathematics and Statistics, Mathematics and Statistics (R0)
Copyright Information: Springer Science+Business Media, LLC 2010
Hardcover ISBN: 978-0-387-95567-4Published: 05 November 2010
Softcover ISBN: 978-1-4939-3820-9Published: 23 August 2016
eBook ISBN: 978-0-387-68441-3Published: 29 October 2010
Series ISSN: 2190-619X
Series E-ISSN: 2190-6203
Edition Number: 1
Number of Pages: XXVIII, 855
Topics: Algorithms, Algorithm Analysis and Problem Complexity, Theory of Computation, Computation by Abstract Devices