Computability and randomness

By André Nies. 2009

634 citations recorded by the source corpus.

The interplay between computability and randomness has been an active area of research in recent years, reflected by ample funding in the USA, numerous workshops, and publications on the subject. The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the complexity aspect. However, computability theoretic tools can also be used to introduce mathematical counterparts for the intuitive notion of randomness of a set. Recent research shows that, conversely, concepts and methods originating from randomness enrich computability theory. Covering the basics as well as recent research results, this book provides a very readable introduction to the exciting interface of computability and randomness for graduates and researchers in computability theory, theoretical computer science, and measure theory.

View Paper: https://www.semanticscholar.org/paper/8a8970b398dcd7e2cd37ff7357dcfca31a01579c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Jan Reimann
2. Joseph S. Miller
3. Theodore A. Slaman

Citations in the corpus

• Extracting information is hard: A Turing degree of non-integral effective Hausdorff dimension (2011, background): “An introduction to algorithmic randomness can be found in the upcoming monographs of Downey and Hirschfeldt [4] and Nies [17] or the excellent survey paper of Downey, Hirschfeldt, Nies and Terwijn [6].”
• Medvedev degrees of two-dimensional subshifts of finite type (2012, unknown): “Two recent references are [15, 30].”
• Measures and Their Random Reals (2008, background): “It was independently obtained by Downey, Hirschfeldt, Miller, and Nies [2].”