2018/06/15 by Bienvenu, Laurent, Csima, Barbara F., Harrison-Trainor, Matthew
#FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1806.05936
The rate of randomness (or dimension) of a string σ is the ratio C(σ)/|σ| where C(σ) is the Kolmogorov complexity of σ. While it is known that a single computable transformation cannot increase the rate of randomness of all sequences, Fortnow, Hitchcock, Pavan, Vinodchandran, and Wang showed that for any 0