Article ID Journal Published Year Pages File Type
435336 Theoretical Computer Science 2016 16 Pages PDF
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
,