Jump to ContentJump to Main Navigation
Computability and Randomness - Oxford Scholarship Online
Users without a subscription are not able to see the full content.

Computability and Randomness

André Nies


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. The book is about these two aspects of sets of natural numbers and about their interplay. For the first aspect, lowness and highness properties of sets are introduced. For ... More

Keywords: lowness properties, highness properties, Kolmogorov complexity, betting strategies, higher computability

Bibliographic Information

Print publication date: 2009 Print ISBN-13: 9780199230761
Published to Oxford Scholarship Online: May 2009 DOI:10.1093/acprof:oso/9780199230761.001.0001


Affiliations are at time of print publication.

André Nies, author
Senior Lecturer, Department of Computer Science, The University of Aukland