Computability and Randomness
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. The book covers topics such as lowness and highness properties, Kolmogorov complexity, betting strategies and higher computability. Both the basics and recent research results are desribed, providing 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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
A Turing machinereads andwrites symbols from a finite alphabetwhich includes thesymbols 0 and1onthese tapes The input tapes are readonly whilet...
if P halts on inputs x
Other editions - View all
binary bounded request set c.e. open c.e. set c.e. traceable Cantor space characterization clopen clopen sets computable approximation computable enumeration computably traceable construction Corollary cost function d.n.c. function defined Definition descriptive complexity dominated sets eachi effective Exercise Fact finite foreach function f given hence implies incomputable infinite initial segment inthe isnot jump traceable Ktrivial set leftc.e Lemma length Low Basis Theorem Low(MLR lowness property martingale MartinLöf randomness minimal pair MLrandom set MLtest nonempty null class obtain ofthe open set oracle machine order function prefixfree machine procedure promptly simple proof of Theorem proofof Proposition randomness notions real number Recursion Theorem reduction relative relativeto relativized requirements Schnorr random sequence simple set Solovay stage strategy strings suchthat superlow supermartingale Suppose thereis thereisa theset truthtable Turing complete Turing degrees Turing functional weakly 2random