×

Randomness in computability theory. (English) Zbl 0962.03039

Cholak, Peter A. (ed.) et al., Computability theory and its applications. Current trends and open problems. Proceedings of a 1999 AMS-IMS-SIAM joint summer research conference, Boulder, CO, USA, June 13-17, 1999. Providence, RI: American Mathematical Society (AMS). Contemp. Math. 257, 1-14 (2000).
Summary: We discuss some aspects of algorithmic randomness and state some open problems in this area. The first part is devoted to the question “What is a computably random sequence?” Here we survey some of the approaches to algorithmic randomness and address some questions on these concepts. In the second part we look at the Turing degrees of Martin-Löf random sets. Finally, in the third part we deal with relativized randomness. Here we look at oracles which do not change randomness.
For the entire collection see [Zbl 0945.00017].

MSC:

03D80 Applications of computability and recursion theory
03D28 Other Turing degree structures
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDFBibTeX XMLCite