I recently added the short article “No-randomness-from-nothing for computable randomness” to the 2014 PDF Logic Blog.
There are two important properties that one would like a notion of algorithmic randomness to have. The first is called randomness preservation. It says that if $T:\{0,1\}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$ is a computable measure-preserving map and $X \in \{0,1\}^\mathbb{N}$ is random, then so is $T(X)$. While this property holds for most randomness notions—Kurtz randomness, Schnorr randomness, Martin-Löf randomness, weak $n$-randomness, difference randomness, Demuth randomness, Oberwolfach randomness, and $n$-randomness—it fails for computable randomness. (Nonetheless, I have work in preparation—extending previous work—showing that randomness preservation for computable randomness holds for all “naturally occurring” computable measure-preserving maps, but this is not the purpose of this article.)
The purpose of this article to show that the dual property, no-randomness-from-nothing, holds for computable randomness.
Theorem (No-randomness-from-nothing for computable randomness). Assume $\mu$ is a computable measure and $T:\{0,1\}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$ is an a.e. computable measure-preserving map. If $Y \in \{0,1\}^\mathbb{N}$ is computably random, then there is some $X \in \{0,1\}^\mathbb{N}$ such that $T(X)=Y$.
(The proof can be found in the PDF Logic Blog.)
It is previously known that no-randomness-from-nothing holds for Martin-Löf randomness, weak $n$-randomness ($n\geq2$), and $n$-randomness. This theorem answers a question of Bienvenu and Porter, who asked if it is true for Schnorr and computable randomness. The Schnorr randomness case still remains open.
Open question. Does no-randomness-from-nothing hold for Schnorr randomness?
(Although, once again, I have work in preparation showing that no-randomness-from-nothing for Schnorr randomness holds for all “naturally occurring” computable measure-preserving maps.)