Interactions of Computability and Randomness
André Nies · Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) · 2011
We survey results relating the computability and randomness aspects of sets of natural numbers. Each aspect corresponds to several mathematical properties. Properties originally defined in very different ways are shown to coincide. For instance, lowness for ML-randomness is equivalent to K-triviality. We include some interactions of randomness with computable analysis. Mathematics Subject Classification (2010). 03D15, 03D32. Keywords. Algorithmic randomness, lowness property, K-triviality, cost function.