Computability and Randomness

2008 To my parents Christel and Otfrid with gratitudePREFACE The complexity and randomness aspects of sets 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. This book is about the two aspects of sets of natural numbers and about their interplay. Sets of natural numbers are identified with infinite sequences of zeros and ones, and simply called sets. Chapters 1 and 6 are mostly about the…