Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435336 | Theoretical Computer Science | 2016 | 16 Pages |
Abstract
A result of Shen says that if F:2N→2NF:2N→2N is an almost-everywhere computable, measure-preserving transformation, and y∈2Ny∈2N is Martin-Löf random, then there is a Martin-Löf random x∈2Nx∈2N such that F(x)=yF(x)=y. Answering a question of Bienvenu and Porter, we show that this property holds for computable randomness, but not Schnorr randomness. These results, combined with other known results, imply that the set of Martin-Löf randoms is the largest subset of 2N2N satisfying this property and also satisfying randomness conservation: if F:2N→2NF:2N→2N is an almost-everywhere computable, measure-preserving map, and if x∈2Nx∈2N is random, then F(x)F(x) is random.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jason Rute,