Authors:
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)
Buy it now
Buying options
Tax calculation will be finalised at checkout
Other ways to access
This is a preview of subscription content, log in via an institution to check for access.
Table of contents (16 chapters)
-
Front Matter
-
Background
-
Front Matter
-
-
Notions of Randomness
-
Front Matter
-
-
Further Topics
-
Front Matter
-
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
-
School of Mathematics, Statistics &, Operations Research, Victoria University, Wellington, New Zealand
Rodney G. Downey
-
, Department of Mathematics, University of Chicago, Chicago, USA
Denis R. Hirschfeldt
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